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

Решение, предложенное Чарльзом Беннеттом в 1980-е гг., состоит в развычислении. Вот как это работает.

1. Запускаете подпрограмму.

2. Копируете кубит, выданный подпрограммой в качестве ответа, в отдельное место.

3. Прогоняете всю подпрограмму задом наперед, стирая таким образом все, кроме кубита-ответа. (Если эта подпрограмма имеет какую-то вероятность ошибки, то этап стирания пройдет неидеально; тем не менее все сработает достаточно хорошо.)

Если вы побываете у меня дома, то увидите, что это не та методика, которой я обыкновенно пользуюсь. Но если вы — квантовый компьютер, то прибрать за собой мусор — неплохая идея.

Отношения с классическими классами сложности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Очень серьезным свидетельством стал алгоритм Саймона[74]. Предположим, у нас есть функция f:{0, 1}n → {0, 1}n, к которой у нас нет доступа и с которой мы можем работать только как с «черным ящиком», то есть подавать что-то на вход и смотреть, что получится на выходе. Нам обещано,