Специалисты по информатике годами искали задачи определённого типа, решить которые был бы способен только квантовый компьютер, но не классический компьютер, пусть даже из будущих поколений. И вот они нашли одну из них.
На ранних этапах изучения квантовых компьютеров специалисты по информатике задали вопрос, ответ на который, по их мнению, должен был открыть какую-то глубокую истину о возможностях этих футуристических машин. 25 лет спустя ответ на него был найден. В работе, опубликованной в мае 2018, специалисты по информатике Рэн Рэз и Авишай Тал предложили убедительное доказательство того, что вычислительные возможности квантовых компьютеров превосходят всё, чего в принципе могут достичь классические компьютеры.
Рэз, профессор Принстонского университета и Вайзмановского научного института, а также Тал, постдок Стэнфордского университета, определили особый тип вычислительных задач. Они доказали, с одной оговоркой, что квантовые компьютеры могли бы эффективно решить задачу, а традиционные компьютеры завязли бы навечно, пытаясь это сделать. Специалисты по информатике искали такую задачу с 1993 года, когда впервые определили класс задач BQP, включающий в себя все задачи, которые способен решить квантовый компьютер.
С тех пор они надеялись противопоставить BQP класс задач, известный как PH, включающий все задачи, выполнимые на любом классическом компьютере, даже невероятно продвинутом, разработанном какой-нибудь цивилизацией будущего. Возможность такого противопоставления зависела от отыскания задачи, которая принадлежала бы к классу BQP, но не к классу PH. И теперь Рэз и Тал сделали это.
Этот результат не делает квантовые компьютеры лучше классических с практической точки зрения. Во-первых, специалисты по теоретической информатике уже знают, что квантовые компьютеры способны решать любые задачи, на которые способны классические. А инженеры с трудом решают задачу создания полезной квантовой машины. Но работа Рэза и Тала демонстрирует различие категорий, в которых находятся квантовые и классические компьютеры – и то, что даже в мире, в котором классические компьютеры превысили пределы любых мечтаний, квантовые компьютеры всё равно смогут их опередить.
Квантовые классы
Базовая задача теоретической информатики – разделить задачи на классы сложности. Класс сложности содержит все задачи, которые можно решить, располагая определённым ресурсом, таким, как время или память.
Учёные, к примеру, обнаружили эффективный алгоритм, проверяющий, является ли число простым. Однако они не смогли найти эффективный алгоритм для поиска простых множителей больших чисел. Следовательно, они считают (хотя и не смогли этого доказать), что две эти задачи принадлежат к разным классам сложности.
Два знаменитых класса сложности – это P и NP. P – это все задачи, которые способен быстро решить классический компьютер. (Задача «является ли число простым?» принадлежит к P). К NP принадлежат все задачи, которые классический компьютер не обязательно решает быстро, но правильность имеющегося решения любой из которых он может быстро проверить. («Каковы простые множители числа?» принадлежит к NP). Учёные считают, что классы P и NP различаются, но задача доказать это различие является сложнейшей и главнейшей из открытых задач в этой области.
PH содержит NP, который содержит P. Является ли BQP классом, отдельным от PH?
В 1993 году специалисты по информатике Итан Бернштейн и Умеш Вазирани определили новый класс сложности, который они назвали BQP, или «квантово-полиномиальное время с ограничением вероятности ошибок». Они определили класс как содержащий все задачи по принятию решений – задачи с ответом «да» или «нет» – которые квантовые компьютеры способны эффективно решать. Примерно в то же время они доказали, что квантовые компьютеры способны решить все задачи, на которые способны классические. То есть, BQP содержит все задачи, содержащиеся в P.
Ещё один пример отдельных классов задач. Задача коммивояжёра спрашивает, существует ли путь, проходящий через определённые города, более короткий, чем заданное расстояние. Такая задача находится в NP. Более сложная задача спрашивает, является ли это расстояние наикратчайшим путём через эти города. Такая задача находится в PH.
Однако они не смогли определить, содержит ли BQP задачи, которых нет в другом важном классе задач, известном как PH или «полиномиальная иерархия». PH – это обобщение NP. Он содержит все задачи, которые можно получить, начав с задачи из NP, и усложняя её, добавляя уточняющие утверждения вроде «существует ли» и «для всех». Классические компьютеры пока не могут решить большую часть задач из PH, но этот класс можно считать классом задач, которые классические компьютеры могли бы решить, если бы оказалось, что P эквивалентно NP. Иначе говоря, чтобы сравнить BQP и PH, надо определить, есть ли у квантовых компьютеров преимущество перед классическими, которое останется, даже если классические компьютеры внезапно научатся решать гораздо больше задач, чем они могут решить сегодня.
«PH – один из наиболее простых существующих классов сложности», — сказал Скотт Ааронсон, специалист по информатике из Техасского университета в Остине. «Поэтому мы вроде как хотим знать место квантовых вычислений в мире классической сложности».
Лучший способ разделить два класса сложности – найти задачу, доказуемо входящую в один из них, и не входящую в другой. Однако из-за сочетания фундаментальных и технических препятствий, такую задачу было найти очень трудно.
Чтобы найти задачу, принадлежащую к BQP, но не к PH, нужно определить нечто, к чему «классический компьютер по определению не смог бы даже эффективно проверить ответ, не говоря уже о том, чтобы найти его, — сказал Ааронсон. – Это исключает множество задач, с которыми мы работаем в информатике».
Спросите оракула
Задача. Допустим, у нас есть два генератора случайных чисел, каждый из которых выдаёт последовательность цифр. Вопрос компьютеру: являются ли две этих последовательности полностью независимыми друг от друга, или они как-то незаметно связаны (например, получена ли одна последовательность преобразованием Фурье другой)? Ааронсон представил эту задачу «фурреляции» в 2009 и доказал, что она принадлежит к BQP. Остался второй, более сложный шаг – доказать, что фурреляция не входит в PH.
Рэн Рэз
В определённом смысле, именно это и удалось сделать Рэзу и Талу. Их работа разделяет BQP и PH при помощи т.н. "оракула" или «чёрного ящика». Это распространённый в информатике результат, к которому прибегают исследователи, когда то, что они хотят доказать, никак им не даётся.
Самый лучший способ разделить классы сложности BQP и PH – измерить вычислительное время, требуемое на решение задач из каждого класса. Но в информатике нет «глубокого понимания реального вычислительного времени или возможности его измерить», — сказал Хенри Юн, специалист по информатике из Торонтского университета.
Вместо этого в информатике измеряют нечто другое, что, как считается, даст понимание вычислительного времени, которое нельзя измерить напрямую. Учёные вычисляют количество обращений компьютера к «оракулу», чтобы дать ответ на вопрос. Оракул вроде как даёт подсказки. Мы не знаем, как он их получает, но знаем, что они надёжны.
Если ваша задача – узнать, есть ли тайная связь между двумя генераторами случайных чисел, оракулу можно задавать вопросы вроде «каким будет шестое число у каждого генератора?» Затем нужно сравнить вычислительную мощность на основе количества подсказок, необходимых каждому компьютеру для решения задачи. Компьютер, которому нужно больше подсказок, работает медленнее.
«В каком-то смысле мы понимаем такую модель гораздо лучше. Она больше говорит об информации, чем о вычислениях», — сказал Тал.
Авишай Тал
Новая работа Рэза и Тала доказывает, что для решения проблемы фурреляции квантовому компьютеру потребуется гораздо меньше подсказок, чем классическому. Более того, квантовому компьютеру нужна всего одна подсказка, при том, что в PH нет алгоритма решения такой задачи даже с неограниченным количеством подсказок. «Это значит, что существует крайне эффективный квантовый алгоритм, решающий такую задачу, — сказал Рэз. – Но если рассматривать только классические алгоритмы, то, даже если дойти до самых верхних классов классических алгоритмов, они с ней не справятся». Это доказывает, что с оракулом фурреляция относится к задачам, принадлежащим к BQP, но не к PH.
Рэз и Тал почти дошли до этого результата около четырёх лет назад, но не смогли сделать один шаг в будущем доказательстве. А потом, всего за месяц до публикации, Тал услышал о новой работе по генераторам псевдослучайных чисел, и понял, что технологии из той статьи как раз дают то, что им с Рэзом нужно было для того, чтобы закончить их собственную. «Это был недостающий фрагмент», — сказал Тал.
Новости о разделении классов BQP и PH распространились быстро. «Мир квантовой сложности гудит», — писал Лэнс Фортнау, специалист по информатике из Технологического университета Джорджии на следующий день после публикации работы.
Работа даёт железную уверенность в том, что квантовые компьютеры существуют в отдельном вычислительном мире от классических (по крайней мере, по определению с оракулом). Даже в мире, где P эквивалентно NP – там, где решить задачу коммивояжёра так же просто, как найти наиболее подходящую строчку в электронной таблице, – доказательство Рэза и Тала демонстрирует наличие задач, решить которые способен только квантовый компьютер.
«Даже если бы P был эквивалентен NP, даже с таким сильным предположением, — сказал Фортнау, — квантовые компьютеры всё равно будет не догнать».
Комментарии (48)
ni-co
30.08.2018 15:34Какое число людей поняло прочитанное? Дай Бог памяти, на Поп_механике научно популярным статьям присваивается уровень сложности. Пора Вам перенять их опыт.
flx0
30.08.2018 15:57Тут не в уровне сложности проблема, а в том, что в статье (как это всегда бывает у SLY_G) просто не содержится никакой информации. Например, не дается ни определения «фурреляции», ни границ ее сложности, ни того, на кой черт для ее вычисления вообще нужен оракул. За этим вам придется лезть в оригинальные статьи. Определения даются здесь: arxiv.org/abs/1411.5729
Arlekcangp
31.08.2018 22:26Ну это как обычно — если статья сложная начинают кричать «что ты тут себе вообразил? никто ничего не понял. Тут не доктора наук собрались». А если простая, то: «что разлил на 20 страниц воды? Хватило бы и двух абзацев. И вообще новость 'неочем' »
Это неминуемо и нормально. Все люди разные. Хотите больше информации — читайте первоисточник. Главное, что он указан и статья не сделана в форме «Ученые открыли, что квантовые компьютеры угрожают человечеству». Там ниже в коментарии есть ссылка на объяснгения на языке оригинала. Неплохо бы конечно и ее перевести но понятно что нельзя все засунуть в одну статью.
Arris
31.08.2018 07:30Пора просто переводить втупую статьи, в которых переводчик/редактор ничего не понимает. И начать переводить те, в теме которых переводчик понимает хоть что-то (а лучше всё).
Это как бы совершенно очевидная вещь, но она упорно игнорируется поколением современных «переводчиков» от гугл транслейт.
P.S. Я тоже почти ничего не понял в статье, хотя читал внимательно. Ну да, классы задач. Ну, новый класс задач. Но это все самыми общими словами.
Это в общем не статья и даже не анонс. Это заметка ниачом.Arris
31.08.2018 17:00Upd: не хватает слова «перестать». Должно быть так:
Пора просто перестать переводить втупую статьи
phenik
31.08.2018 14:38Забавно, некоторые возмущается, нет объяснения в статье того, или этого, не замечая, что это просто перевод научно-популярной статьи. В ней, что исходно есть, то и есть. Можно апеллировать к качеству перевода, но переводчик не обязан суда ничего добавлять.
Так же забавны возмущения, что настолько просто все изложено, что ничего не понятно) Просто удивительны такие феномены, не могут понять в простом изложении, подайте им в виде оригинальной статьи, часто со специализированной математикой, кот. действительно понимают может несколько человек в мире)
Все же тут не специализированный математический форум, и важно быть в курсе новостей связанных с компьютерными технологиями и связанными областями. А тонкости, если возник проф. интерес, всегда можно посмотреть в источниках. Ссылки обычно приводятся в темах.Arris
31.08.2018 17:09+1Понимаете, все что сказано в статье, можно было уместить в один абзац.
А переливание из пустого в порожнее очень общими словами о каких-то научных вещах — что выдается за «научно-популярное» — это совершенно не то, чего ожидаешь от статьи на хабре.
Особенно от редактора хабра. Ничего личного, просто от редактора хабра ждешь более ответственного подхода к формированию контента, к выбору материала для перевода или к самому качеству перевода.
Sychuan
01.09.2018 22:28А переливание из пустого в порожнее очень общими словами о каких-то научных вещах
Хабр это сообщество. Вы можете взять оригинальную научную статью перевести ее и порадовать этим всех. Лично меня такие популярные статьи устривают, хотя я и читаю их обычно на оригинальном сайте.
Shkaff
30.08.2018 15:47Для интересующихся, Скотт Ааронсон (о нем в посте) недавно написал интересный пост про BQP vs PH, где детальнее рассказал, что там к чему. Ну и просто интересная история про то, как идеи развиваются в науке.
vaniacer
30.08.2018 15:52Эм, сначала изобрели «такие» компьютеры и только потом изобрели «то» для чего изобрели «такие» компьютеры. Я правильно понял?)
VBKesha
30.08.2018 15:58Не до конца изобрели такие компьютеры, но уже стали задумываться для чего же они нужны.
technomancer
30.08.2018 17:20Если дома нет ни одного гвоздя, гораздо сложнее уговорить жабу семейного бюджета на покупку молотка.
Andrusha
30.08.2018 17:57Как известно, компьютер (обычный) позволяет решать проблемы, которых до появления компьютера не существовало, так что тут ничего нового :)
8street
31.08.2018 11:43Но если глобальнее мыслить, нежели в рамках одной конкретной программы, все же польза от компьютеров есть.
Andrusha
31.08.2018 11:55Я в курсе, просто процитировал бородатую шутку. На самом деле, компьютеры, разумеется, упрощают жизнь при правильном применении и усложняют при неправильном (пример — многострадальная Почта России, где всё отделение может встать из-за «зависшей программы» и отсутствия сисадмина на месте).
Hardcoin
30.08.2018 16:57Задача коммивояжёра спрашивает, существует ли путь, проходящий через определённые города, более короткий, чем заданное расстояние. Такая задача находится в NP. Более сложная задача спрашивает, является ли это расстояние наикратчайшим путём через эти города. Такая задача находится в PH.
Что-то не так с переводом? Если путь существует, то расстояние не кратчайшее. Если не существует — то кратчайшее. Это эквивалентные вопросы.
Shkaff
30.08.2018 17:15Кажется, что все нормально: по сути, NP просит найти любой путь короче некоторого расстояния. PH спрашивает, является ли найденный путь кратчайшим.
ОригиналThe “traveling salesman problem” asks whether there’s a path through some number of cities that’s shorter than some given distance. It’s in NP. A more complex problem asks if the shortest path through those cities is exactly that distance. That problem is in PH.Hardcoin
30.08.2018 19:18Найденный? Не данный? Ну если NP — найти любой, короче данного, а PH — найти самый короткий — то да, разные задачи. Но в оригинале тоже не ясно — "exactly that distance" — that — это та, которая "given" или та, которая "shorter".
В любом случае, спасибо за такой вариант прочтения.
Shkaff
30.08.2018 20:47На самом деле, мне кажется, тут пример про коммивояжера — это именно пример задачи в PH, а не ее полное описание. PH — это обобщение NP, где может быть больше одного условия, и может быть связь между условиями (напр. найти только те пути, которые меньше данного расстояния и проходят через город N три раза). Нахождение кратчайшего расстояния — пример такого дополнительно условия.
ОригиналPH is a generalization of NP. This means it contains all problems you get if you start with a problem in NP and make it more complex by layering qualifying statements like “there exists” and “for all.”
vics001
30.08.2018 18:57-1По сути дела, это больше теоретическое достижение, чем практическое, которое, к тому же кажется чем-то очевидным. Практическая проблема, что квантовому алгоритму можно дать одну подсказку или 1000, разница будет в том, что он найдет решение с большей или с меньшей вероятностью.
С теоретической точки зрения, было бы даже интереснее получить решение задачи «исчисления предикатов». Общая задача состоит в том, что если у теорема верна (т.е. ее отрицание противоречит аксиомам), то у нее существует конечный вывод. К сожалению, почти очевидно, что разумного «алгоритма» не существует, дерева исчисления растет слишком быстро. В то же время очевидно, что квантовый компьютер может перебирать по всему пространству сразу и, возможно, он может дать ответ за конечное время. Опять же обычный компьютер не сможет проверить это, если не знает самого вывода. Эта задача будет общей для большого количества задач, так как практически все записывается в предикатах.Shkaff
30.08.2018 19:08+1Кажется, что практической пользы совсем нет: эти форелляции требуют оракула, а мы даже не представляем, как оракул мог бы реализовываться в реальности.
Кстати, а откуда вам кажется очевидным это достижение?phenik
31.08.2018 14:14мы даже не представляем, как оракул мог бы реализовываться в реальности.
Это не может быть измерение, или некий опыт в общем случае? Если речь о ГСЧ, о которых речь в статье, и требуется подсказка «каким будет шестое число у каждого генератора?», то можно прочесть сгенерированное значение и передать в процедуру сравнения, кот. устанавливает зависимость/независимость генераторов. Исхожу из более общих соображений, как действует человек, когда возникают проблемы с доказательством достоверности теоретических построений — решается постановкой эксперимента.
********
С квантовыми алгоритмами определись, получается отдельный класс. А как насчет класса сложности задач, который может решить встроенный «компьютер» человека — мозг? Можно действовать по аналогии, найти задачу, кот. мозг, даже коллективные мозги, не могут решить. Далеко ходить не надо, такая задача имеется — квантовая гравитация, точнее создание общепринятой, многократно независимо подтвержденной и практически применимой теории. Скоро уже, как век над ней бьются лучшие умы человечества, а решения пока не видно, не хватает мощности мозгов, выдаются многочисленные промежуточные результаты. Ждем подсказок «оракулов» — решающих экспериментов и прямых наблюдений)Shkaff
31.08.2018 15:02Насколько я понимаю, оракул «знает» решение задачи, и дает подсказки нашему компьютеру. Реализовать его, видимо, нельзя в принципе — т.к. он по определению «мощнее» нашего компьютера. Мне кажется, это чисто теоретическая конструкция, введенная как критерий сравнения алгоритмов. Поэтому алгоритмы, для которых необходим оракул, не получится реализовать на практике. Это чисто математика.
Ааронсон об этом же пишет:
Тутa journalist already emailed to ask me about the practical implications of the BQP vs. PH breakthrough—for example, for the ~70-qubit quantum computers that Google and others hope to build in the near future—let me take the opportunity to say that, as far as I can see, there aren’t any. This is partly because Forrelation is an oracle problem, one that we don’t really know how to instantiate explicitly (in the sense, for example, that factoring and discrete logarithm instantiate Shor’s period-finding algorithm). And it’s partly because, even if you did want to run the quantum algorithm for Forrelation (or for Raz and Tal’s noisy Forrelation) on a near-term quantum computer, you could easily do that sans the knowledge that the problem sits outside the polynomial hierarchy.phenik
31.08.2018 18:11Насколько я понимаю, оракул «знает» решение задачи
Знаю про такое определение. Но все же странно, как использовать выводы этих теорем на практике, когда речь дойдет о действительном сравнении тех же реализаций ГСЧ. Похоже классическим способом в классе PH), простым сбором статистики, и сравнением результатов.
Не думаю, что ваше рассуждение имеет отношение к классам сложности выше NP. Подозреваю, что эта задача вполне себе лежит в классе Р, т.е. вполне может быть решена классическим компьютером за конечное время.
Это вы о результате в виде готовой теории?) Я о процессе построения. Это другой уровень, аналога кот. в самых сложных алгоритмах пока нет. Все классы алгоритмов вычислительной сложности лишь некоторый аспект некоей интеллектуальной сложности деятельности мозга. Аспект абстрагированный, и реализованный с помощью технических средств. Абстрагирование имеет отношение к построению любых теоретических конструкций. Но абстрагирование имеет свои ограничения, кот. ограничивают и классы решаемых задач, по крайней мере, могут сильно затруднить их решение. Квантовая гравитация относится к этому классу.Shkaff
31.08.2018 18:29Но все же странно, как использовать выводы этих теорем на практике, когда речь дойдет о действительном сравнении тех же реализаций ГСЧ.
Ну а никак не использовать:) Эти алгоритмы неприменимы на практике. Тем не менее, сам факт их существования важен для разработки новых, уже рабочих, алгоритмов.
Я о процессе построения. Это другой уровень, аналога кот. в самых сложных алгоритмах пока нет.
Во-первых, как я понимаю, процесс построения не имеет отношения к классам сложности. Если вы к тому, что сам процесс тоже является задачей, и должен относиться к какому-то классу, то он относится, думаю, как максимум к NP — компьютер может проверить, что этот алгоритм выполняет задачу, если мы ему дадим готовый алгоритм.
Во-вторых, я не очень понял, в чем разница между «абстрактным» мышлением и компьютером. Я могу дать задачу своему компьютеру построить теоретическую модель или сделать симуляцию ровно так же, как я это делаю со своим мозгом. Мозг работает сильно параллельно, компьютеру далеко до этого, но суть в общем та же.
Сейчас есть нейронные сетки, которые строят эксперименты в квантовой оптике, оптимальность которых очевидна на практике, но совершенно недоступна нашему пониманию. Не очень вижу разницу между такой сетью и студентом, если вход и выход одинаков.phenik
01.09.2018 08:13Ну а никак не использовать:)
Похоже на то) Единственное замечание, что ''оракул", или «черный ящик» знает решение задачи, но ведь реальная реализация ГСЧ, например, аппаратная реализация, использующая некоторый физич. эффект для генерации чисел, является фактически таким «черным ящиком», кот. знает решение, то есть он подходит под определение «оракула» в этих теоремах.
Сейчас есть нейронные сетки, которые строят эксперименты в квантовой оптике, оптимальность которых очевидна на практике, но совершенно недоступна нашему пониманию. Не очень вижу разницу между такой сетью и студентом..
Можете ссылку привести, было бы любопытно глянуть. Если интересно, посмотрите эту дискуссию с пользователем, кот. пытался используя теоремы Гёделя опровергнуть возможность создания ИИ, позволяющего создавать формальные системы, на уровне с человеком.Shkaff
01.09.2018 10:40Можете ссылку привести, было бы любопытно глянуть.
Например вот или вот. Вот про эту статью как раз автор говорила, что им выдает оптимальный алгоритм, логику за которым проследить не получается (а аналитического решения нет).
Спасибо за ссылку, я почитаю на досуге:)
CaptainFlint
01.09.2018 12:55Насколько я понял, под оракулом в статье подразумевается не общий термин, а конкретная сущность из теории квантовых вычислений. Там оракулом зовётся квантовая функция, реализующая вычисление некой исходной классической функции (обычно, являющейся ключевой для решения задачи).
Shkaff
01.09.2018 15:51Судя по статье Ааронсона и вики, это черный ящик, к которому может обратиться компьютер с вопросом о задаче, и оракул даст всегда правильный ответ за один шаг:
For example, if the problem is a decision problem for a set A of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with «yes» or «no» stating whether that number is an element of A.
CaptainFlint
01.09.2018 19:16+1Я имел в виду, что термин «оракул» можно трактовать обобщённо, как некую абстрактную функцию, выдающую ответы, а можно в контексте квантового алгоритма, где оракулом называется функция-«отвечатель», являющаяся частью этого алгоритма, вызывающаяся в нужный момент нужным образом.
Hardcoin
30.08.2018 19:23+1если у теорема верна (т.е. ее отрицание противоречит аксиомам),
"Т.е." у вас сомнительное. Есть верные теоремы, про которые мы никогда не сможем сказать, что они верные (и методом от противного — тоже, а значит не можем сказать, что отрицание противоречит аксиомам).
vics001
31.08.2018 11:22Это не теорема. Это утверждение, которое не противоречит аксиомам, следовательно оно может быть аксиомой, но и его отрицание может быть аксиомой.
0xd34df00d
01.09.2018 01:23Ну, вообще говоря, это не совсем так.
Во-первых, стоит явно говорить, что существование таких теорем зависит от вашей теории. Теория групп, например, очевидно неполна, потому что есть принципиально разные группы, и полная теория была бы не очень интересной практически.
Теория всюду плотных множеств без первого и последнего с равенством и порядком, в свою очередь, полна (более того, все её, скажем, счётные модели изоморфны, и именно этим можно показать её полноту по критерию Лося, например). Теория алгебраически замкнутых полей характеристики 0 полна.
А, во-вторых, вот какая-нибудь арифметика Пеано, да, тоже неполна. Но это не значит, что в ней есть верные теоремы, про которые мы там что-то можем или не можем сказать (тем более, «никогда») — они просто из этой теории не выводятся, так что понятие верности для них не определено ни синтаксически (в смысле значка ?), ни семантически (есть модели, где они истинны, и есть — где ложны). Иными словами, это лишь значит, что и Г, ?, и Г, ¬? непротиворечивы. Возьмете теорию Г, ?, будет верная теорема. Возьмете Г, ¬?, будет неверная.Hardcoin
01.09.2018 11:57Спасибо за уточнение. Перечитал исходный коммент, там про исчисление предикатов, оно полно. Так что найти доказательство (или опровержение) любой формулы, видимо, можно, свое возражение снимаю.
0xd34df00d
01.09.2018 21:20Оно полно немножко в другом смысле: любая общезначимая формула логики первого порядка выводима в ИП. Если формула не общезначима, и её отрицание тоже не общезначимо, то найти её доказательство (синтаксический вывод) или опровержение (синтаксический вывод отрицания этой формулы) у вас тоже не получится.
Да и в конце концов, если у вас есть некоторая теория Г, то верность ? в этой теории означает выводимость ? из (конечного числа) предпосылок из Г, и можно показать, что это эквивалентно выводимости формулы вида (?? >… > ?n > ?) в ИП, где слева от последней импликации стоят используемые в выводе из Г формулы этой теории. Если бы любая формула в ИП была выводима (или выводимо её отрицание), то поэтому любая теория была бы полна (по крайней мере, любая теория со счётным числом аксиом, про несчётные уже надо мозг включать).
inferrna
30.08.2018 19:21-1Берём классический компьютер, запускаем на нём симуляцию квантового.
@
Работает чуть помедленнее, зато требует всего одну подсказку.
@
Шах и мат, академики.Hardcoin
30.08.2018 19:32+1Если я верно понял, "чуть по-медленнее" — это экспоненциально медленнее. То есть суть не в невозможности (подобрать любой RSA-шифр тоже возможно), а в этой экспоненте.
Megakazbek
30.08.2018 20:08+1Есть нюанс. В статье говорится о преимуществе квантового компьютера над «boolean circuit», т.е. цифровым компьютером, но ничего не говорится об аналоговых компьютерах, не использующих квантовые эффекты. А ведь для некоторых квантовых алгоритмов придумали реализации и в виде классической аналоговой системы, имеющие такое же преимущество в скорости над цифровыми компьютерами.
Alex_ME
30.08.2018 22:31+1Какая-то SEO-шная статья. 2/3 пересказывают одно и то же разными словами, почти никакой конкретики.
Erraendil
31.08.2018 04:55Кажется, Либо в статье опечатка, либо я совсем запутался:
Самый лучший способ разделить классы сложности BQP и ЗР – измерить вычислительное время,
3P = NP?
p_fox
31.08.2018 09:19Я так и не увидел ответ на главный вопрос: Дум на нем уже запустили или еще нет?
Oxoron
31.08.2018 10:38На квантовом компьютере Crysis на максималках будет летать?
За исключением некоторого подмножества задач, которые квантовая модель вычислений способна ускорить, остальные могут быть решены лишь эмуляцией классического компьютера. Что, как вы понимаете, очень медленно. Crysis, скорее всего, будет лагать.
stanislavskijvlad
31.08.2018 12:30Это как Crysis. Игра была, а железо, которое потянет его топовую графику – нет.
mphys
Ух, наконец можно будет стабильно играть на 144 Hz во все новинки…