Квантовые вычисления со времен Демокрита - Скотт Ааронсон

более чем 90 % условий. Таким образом, для заданной входной строки нужно только отличить случай, при котором она удовлетворяет всем условиям, от случая, при котором она удовлетворяет не более чем 90 % из них, — а это можно сделать путем проверки нескольких десятков случайных условий, совершенно независимо от длины доказательства.

Сложность моделирования теорий со скрытыми параметрами

В предыдущей главе мы говорили о траектории скрытого параметра частицы в теории скрытых параметров, но в чем состоит сложность нахождения такого пути? Определенно, эта задача по крайней мере столь же трудна, как квантовые вычисления, поскольку даже для того, чтобы получить значение скрытого параметра в один произвольный момент времени, потребовалось бы в общем случае полномасштабное квантовое вычисление. Наверное, нахождение целой траектории — еще более сложная задача?

Можно задать этот вопрос и по-другому. Предположим, что в момент смерти вся ваша жизнь мгновенно пролетает перед вашими глазами, и предположим, что после этого можно вычислить за полиномиальное время всю вашу жизненную историю. Что при этом можно вычислить? Считая, конечно, что теория скрытых параметров верна и что еще до смерти вы каким-то образом умудрились поместить собственный мозг в несколько нетривиальных суперпозиций.

Чтобы исследовать этот вопрос, мы можем ввести новый класс сложности — DQP, динамический квантовый полиномиального времени. Формальное определение этого класса немного запутанно (подробности см. в моей статье[102]). Однако интуитивно DQP — это класс задач, эффективно решаемых на «модели», где вы должны сделать выборки для всей траектории скрытого параметра в рамках какой-либо теории скрытых параметров, удовлетворяющей «разумным» предположениям.

А теперь вспомним про класс SZK — класс задач, имеющих протокол доказательства со статистически нулевым разглашением. Основным результатом моей статьи было то, что SZK ⊆ DQP. Иными словами, если бы мы только могли измерить всю траекторию скрытого параметра, то мы могли бы использовать квантовый компьютер для решения любой SZK-задачи, включая неизоморфность графов и многие другие, для которых пока неизвестны эффективные квантовые алгоритмы!

Чтобы объяснить, почему так, мне придется рассказать вам, что в 1997 г. Сахаи и Вадхан открыли чрезвычайно милую «полную задачу с априорными ограничениями» для SZK. Задача эта выглядит так:

Если даны два вероятностных распределения D1 и D2, допускающих эффективную выборку, то близки они или далеки в смысле статистического расстояния (если априорно известно, что либо то, либо другое верно)?

Это означает, что, думая о SZK, нам можно забыть о доказательствах с нулевым разглашением и просто считать, что у нас есть два вероятностных распределения и мы хотим знать, близки они или далеки?

Но позвольте внести еще больше конкретики. Скажем, что у вас есть функция f: {1, 2, …, N} → {1, 2, …, N} и вы хотите решить, является f взаимно однозначной или же ее значения повторяются, при условии, что один из этих вариантов верен. Эта задача — известная как задача столкновения — не до конца отражает сложность всех SZK-задач, но достаточно близка к этому для наших целей.

Итак, сколько запросов к f вам потребуется, чтобы решить задачу столкновения? Если воспользоваться классическим вероятностным алгоритмом, то несложно убедиться, то √N запросов будет необходимо и достаточно. Как и в знаменитом «парадоксе именинников» (где достаточно собрать в комнате 23 человека, и шансы на то, что по крайней мере у двух человек в комнате совпадут дни рождения, превысят 50 %), вы получаете улучшение в корень квадратный раз по сравнению с очевидной границей, поскольку нам важно число пар, для которых такое столкновение возможно. Но, к несчастью, если N экспоненциально велико, как в тех ситуациях, которые мы обсуждаем, то √N по-прежнему все запрещает: квадратный корень из экспоненты — тоже экспонента.

Может быть, помогут квантовые алгоритмы? В 1997 г. Брассар, Хёйер и Тапп показали[103], как совместить экономию в √N от парадокса именинников с никак не связанной с ними экономией в √N от алгоритма Гровера, чтобы получить квантовый алгоритм, способный решить задачу столкновения за (звучит как шутка) ~N1/3 запросов. Так что, да, квантовые компьютеры действительно дают по крайней мере небольшое преимущество при решении этой задачи. Но неужели это максимум того, что можно сделать? Или может существовать лучший квантовый алгоритм, способный решить задачу столкновения за, скажем, log(N) запросов, а может, и меньше?

В 2002 г. я доказал первую нетривиальную нижнюю оценку[104] сложности квантового запроса в задаче столкновения; мне удалось показать, что любому квантовому алгоритму потребуется по крайней мере ~N1/5 запросов. Позже Ши Яоюнь[105] улучшил этот результат до ~N1/3, показав таким образом, что алгоритм Брассара, Хёйера и Таппа в самом деле оптимален.

С другой стороны — вернемся к нашей теме — предположим, что можно было бы увидеть траекторию скрытого параметра целиком. Тогда, утверждаю я, можно было бы решить задачу столкновения при помощи всего лишь постоянного числа запросов (независимого от N)! Как? На первом шаге — подготовить состояние

Далее измеряем второй регистр (который после этого нам не понадобится) и думаем только о результирующем состоянии первого. Если f взаимно однозначна, то в первом регистре вы получите классическое состояние вида |i〉 для некоторого случайного i. С другой стороны, если f дает повторяющиеся результаты, то мы получим состояние вида

где i и j — две величины, такие, что f(i) = f(j). Если бы можно было провести еще одно измерение и различить эти состояния! Но увы, измеряя, вы разрушаете квантовую когеренцию, и оба типа состояния кажутся вам совершенно одинаковыми.

Ага, но не забывайте, что мы собирались увидеть всю траекторию скрытого параметра! Вот как мы этого добьемся. Взяв за основу состояние

для начала применим к каждому кубиту вентиль Адамара. Это даст нам «похлебку» из экспоненциального множества базисных векторов, но если мы затем применим вентиль Адамара к каждому кубиту второй раз, мы вернемся обратно к первоначальному состоянию Далее, идея в том, что когда мы пропускаем все через вентиль Адамара, частица «забывает», была ли она на i или на j. (Это можно доказать при некоторых слабых допущениях относительно теории скрытых параметров.) Затем, когда мы посмотрим на историю нашей частицы, мы узнаем кое-что о том, имело ее состояние вид |i〉 или Ведь в первом случае частица всегда будет возвращаться к i,