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

что существует «секретная маска на исключающем или» s ∈ {0, 1}n, такая, что для всех несовпадающих пар (x, y) имеем f(x) = f(y) в том и только том случае, если x ⊕ y = s. (Здесь знаком ⊕ обозначается операция побитового исключающего или.) Наша цель — распознать s. Вопрос в том, сколько раз нам придется послать запрос на f, чтобы сделать это с высокой вероятностью?

В классическом варианте легко определить, что для этого необходимо и достаточно ~2n/2 запросов. Как только мы наткнемся на противоречие (пару x ≠ y, такую, что f(x) = f(y)), мы поймем, что s = x ⊕ y, и задача будет решена. Но до тех пор, пока мы не обнаружим противоречие, функция будет нам казаться случайной. В частности, если мы отправим ей T запросов, то вероятность наткнуться на противоречие составит не более ~T2/2n в силу неравенства Буля. Следовательно, для нахождения s с высокой вероятностью нам потребуется T ≈ 2n/2 запросов.

С другой стороны, Саймон привел квантовый алгоритм, способный найти s, сделав всего ~n запросов. Его основная идея состоит в том, чтобы посылать на f запросы в виде суперпозиции, а потому готовить квантовые состояния вида

для случайных пар (x, y), таких, что x ⊕ y = s. Затем мы используем так называемое квантовое преобразование Фурье, чтобы извлечь из этих состояний информацию про s. Использование преобразования Фурье для извлечения «информации о скрытой периодичности» послужило непосредственным толчком для создания алгоритма Шора, который делает нечто подобное по абелевой группе ZN вместо Zn2. Как теперь хорошо известно, доклад Саймона был отвергнут в первый раз, когда он подал его для участия в конференции, — судя по всему, Шор оказался одним из немногих, кто сумел понять смысл написанного.

Опять же я не буду разбирать алгоритм Саймона в подробностях; подробности при желании можете посмотреть здесь[75].

Подведем итог. У нас есть задача — задача Саймона, которую квантовые компьютеры смогут решить экспоненциально быстрее, чем классические, и это доказано. Следует признать, правда, что задача получилась довольно надуманная, поскольку в деле вычисления функции f с определенной глобальной симметрией она опирается на мифический «черный ящик». Из-за присутствия в формулировке черного ящика задача Саймона не может доказать, что BPP ≠ BQP. Доказывает она лишь существование некоторого оракула, по отношению к которому BPP ≠ BQP. Вот что я имел в виду, когда говорил о формальных доказательствах того, что квантовые компьютеры мощнее классических.

Оказывается, задача Саймона не была первой задачей, выявившей различие между BPP и BQP по оракулу. Как Шор берет начало от Саймона, так Саймон берет начало от Бернштейна — Вазирани. В давние темные века, а конкретно в 1993 г., Берштейн и Вазирани придумали задачу с черным ящиком, получившую название рекурсивной выборки Фурье. Они сумели доказать, что любому классическому алгоритму для решения этой задачи необходимо по крайней мере ~nlog n запросов, тогда как существует квантовый алгоритм ее решения, которому достаточно всего лишь n запросов.

К несчастью, даже для формулирования задачи рекурсивной выборки Фурье потребовалось бы более длинное отступление, чем представляется разумным. (Если вы считаете, что задача Саймона искусственна, вы ничего еще в жизни не видели!) Но основная идея состоит в следующем. Предположим, у нас имеется доступ посредством черного ящика к некоторой булевой функции f:{0, 1}n → {0, 1}. Нам обещано, что существует «секретная строка» s ∈ {0, 1}n, такая, что f(x) = s x для всех x (где знак • обозначает внутреннее произведение по модулю 2). Наша цель — определить s с использованием как можно меньшего числа запросов к f.

Иными словами, нам известно, что f(x) — это всего лишь исключающее или от некоторого подмножества входных битов; наша цель — найти, от какого именно подмножества.

В классическом варианте очевидно, что необходимо и достаточно послать n запросов к f: мы пытаемся узнать n бит, а каждый запрос может раскрыть лишь один бит! Но Бернштейн и Вазирани заметили, что в квантовом варианте можно выяснить s при помощи одного-единственного запроса. Для этого нужно просто подготовить состояние

а затем применить вентиль Адамара ко всем n кубитам разом. Несложно убедиться, что результат будет равен |s〉.

Бернштейн и Вазирани начали с описанной выше задачи, известной как выборка Фурье, и применили к ней рекурсивный алгоритм. Иными словами, они построили задачу нахождения выборки Фурье, в которой, чтобы узнать один из битов f(x), вам нужно решить другую задачу на нахождение выборки Фурье, а для того чтобы определить один из битов в этой задаче, нужно решить третью, и т. п. Затем они показали, что если рекурсия осуществляется на глубину в d уровней, то любому рандомизированному алгоритму для решения этой задачи на рекурсивную выборку Фурье придется сделать по крайней мере ~nd запросов. В то же время существует квантовый алгоритм, решающий эту задачу всего за 2d запросов.

Почему 2d запросов, спросите вы, а не 1d = 1? Потому что на каждом уровне рекурсии квантовому алгоритму требуется провести обратное вычисление и избавиться от мусора, чтобы получить эффект интерференции, — и это постоянно добавляет лишний множитель 2. Примерно так:

Кстати, один из моих результатов[76] показывает, что такого рода рекурсивные обратные вычисления — неизбежная черта любого квантового алгоритма рекурсивной выборки Фурье.

Итак, мы получили разницу между nd и 2d; приравняв d = log n, получим nlog n запросов на классическом компьютере и 2log n = n на квантовом. Конечно, полученная нами разница — это не экспоненциальное число против полиномиального, а всего лишь «квазиполиномиальное» против полиномиального. Тем не менее этого достаточно, чтобы доказать расхождение между BPP и BQP по оракулу.

Вы можете поинтересоваться: теперь, когда у нас есть алгоритмы Саймона и Шора, которые реально дают экспоненциальную разницу между квантовым и классическим, зачем заморачиваться возней с этим рекурсивным археологическим реликтом? Дело в том, что одна из самых масштабных задач квантовых вычислений связана с отношениями между BQP и полиномиальной иерархией PH, определенной в главе 6. А именно: входит ли BQP в PH? Конечно, это представляется маловероятным, но, как ставили вопрос Бернштейн и Вазирани еще в 1993 г., можем ли мы на самом деле найти оракул, по отношению к