Хорошо, так как же класс BQP соотносится с теми классами сложности, что мы уже видели?

Первое. Я утверждаю, что BPP ⊆ BQP; иными словами, все, что вы можете сделать при помощи классического вероятностного компьютера, вы можете сделать и при помощи квантового компьютера. Почему?

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

Можем ли мы получить какую-либо верхнюю оценку для BQP в терминах классических классов сложности?

Конечно, можем! Во-первых, совсем несложно убедиться, что BQP ⊆ EXP: все, что можно вычислить за квантовое полиномиальное время, можно вычислить также за классическое экспоненциальное время. Или, сформулируем иначе, квантовые компьютеры могут обеспечить нам не более чем экспоненциальное преимущество над классическими. Почему так?

Верно: потому что если разрешить экспоненциальное замедление, то классический компьютер сможет попросту проимитировать все изменения вектора состояния!

Оказывается, однако, что можно получить результат и получше. Вспомните класс PP, включающий задачи вроде следующих.

• Дана сумма экспоненциального количества действительных чисел, каждое из которых можно оценить за полиномиальное время. Определить, положительной или отрицательной будет эта сумма (при условии, что она и правда положительна или отрицательна).

• Дана булева формула n переменных. Определить, дает ли по крайней мере половина из 2ⁿ возможных входных значений переменных результат «истина».

• Дана рандомизированная машина Тьюринга полиномиального времени. Определить, принимает ли она с вероятностью ≥ 1/2?

Иными словами, в PP-задаче речь идет о том, чтобы просуммировать экспоненциальное число слагаемых, а затем определить, больше эта сумма некоторого порогового значения или меньше. Разумеется, PP входит в PSPACE, который, в свою очередь, входит в EXP.

Бернштейн и Вазирани в своей оригинальной работе по квантовой сложности показали, что BQP ⊆ PSPACE. Вскоре после этого Адлеман, Де Маррэ и Хуанг[72] улучшили этот результат, показав, что BQP ⊆ PP. (Это был также первый результат в теории сложности, доказанный мной. Если бы я знал, что Адлеман и др. доказали это годом ранее, я, может, никогда и не занялся бы этим делом! Иногда, знаете ли, лучше иметь узкий академический кругозор.)

Итак, почему BQP укладывается в PP? С точки зрения теоретической информатики доказательство может занять, скажем, полстраницы. С точки зрения физики, доказательство сводится к трем словам:

Фейнмановский интеграл по траектории!!!

Скажем, вы хотите вычислить вероятность того, что квантовый компьютер принимает. Очевидный способ сделать это — перемножить кучу унитарных матриц размера 2ⁿ × 2ⁿ, затем взять сумму квадратов абсолютных величин амплитуд, соответствующих принимающим базисным состояниям (то есть базисным состояниям, для которых выходной кубит равен |1〉). В 1940-е гг. Фейнман заметил, что есть способ и получше — способ куда более эффективный по затратам памяти (или бумаги), хотя по-прежнему экспоненциальный по затратам времени.

Способ получше состоит в том, чтобы перебрать в цикле все принимающие базисные состояния и для каждого из них перебрать все вычислительные траектории, способные внести вклад в амплитуду для этого базисного состояния. Пусть, к примеру, α_x — конечная амплитуда базисного состояния |x〉. Тогда мы можем записать

где каждый член α_x,i соответствует одному листку на экспоненциально большом «дереве возможностей» и потому вычислим за классическое полиномиальное время. Как правило, α_x,i — комплексные числа с совершенно разными фазами, склонные деструктивно интерферировать и исключать друг друга; тогда α_x будет небольшим остатком этого процесса. Причина, по которой квантовые вычисления представляются более мощным инструментом, чем классические вычисления, заключается именно в том, что на первый взгляд трудно оценить тот небольшой остаток на основании случайной выборки. Случайные выборки прекрасно работают, скажем, в ходе типичных американских выборов, но оценка αx больше напоминает выборы 2000 года с их неопределенным результатом.

Далее, пусть S — множество всех принимающих базисных состояний. Тогда мы можем записать вероятность того, что наш квантовый компьютер принимает, как

где * обозначает комплексное сопряжение. Но это всего лишь сумма экспоненциального числа слагаемых, каждое из которых вычислимо в P. Поэтому мы можем решить в PP, правда ли, что p_accept ≤ 1/3, или же p_accept ≥ 2/3.

С моей точки зрения, Ричард Фейнман получил Нобелевскую премию по физике в основном за то, что показал: BQP содержится в PP.

Конечно, по-настоящему всех заводит немного другой вопрос: правда ли, что BPP ≠ BQP, то есть действительно ли квантовые вычисления — более мощный инструмент, чем классические. Сегодня у нас есть свидетельства в пользу того, что это действительно так; самое заметное из них — алгоритм Шора для разложения на простые множители и дискретного логарифмирования. Я уверен, что вы слышали об этом алгоритме, поскольку это одно из крупнейших научных достижений конца XX века и основная причина того, что мы с вами вообще говорим об этих вещах. Если вы еще не видели его, то в сети можно найти с полмиллиона упоминаний на эту тему[73].

Стоит подчеркнуть, что еще до алгоритма Шора компьютерщики собрали немало формальных свидетельств того, что квантовые компьютеры мощнее классических. По существу, именно эти свидетельства вымостили дорогу к алгоритму Шора.

Очень серьезным свидетельством стал алгоритм Саймона[74]. Предположим, у нас есть функция f:{0, 1}ⁿ → {0, 1}ⁿ, к которой у нас нет доступа и с которой мы можем работать только как с «черным ящиком», то есть подавать что-то на вход и смотреть, что получится на выходе. Нам обещано, что существует «секретная маска на исключающем или» s ∈ {0, 1}ⁿ, такая, что для всех несовпадающих пар (x, y) имеем f(x) = f(y) в том и только том случае, если x ⊕ y = s. (Здесь знаком ⊕ обозначается операция побитового исключающего или.) Наша цель — распознать s. Вопрос в том, сколько раз нам придется послать запрос на f, чтобы сделать это с высокой вероятностью?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наконец в 2009 г. я предложил другую задачу-кандидата[77], получившую известность под названием «проверка коэффициентов Фурье»; по идее, она должна дать не просто разделение BQP и PH по оракулу, но и (в отличие от рекурсивной выборки Фурье) разделение экспоненциальное. Увы, доказательство этого разделения, судя по всему, требует кое-каких новых достижений в классической теории сложности, а именно в определении нижних оценок схем постоянной глубины, пока нам неизвестных. Однако не исключено, что в результате работы над проверкой коэффициентов Фурье задачу рекурсивной выборки Фурье удастся наконец превзойти, и она сохранит лишь историческое значение.