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

раз, мы узнаем x2 и нанесем лишь небольшой ущерб. Поскольку небольшой ущерб плюс небольшой ущерб будет по-прежнему небольшой ущерб, мы можем затем найти x3, и т. п. Таким образом, мы можем восстановить все биты оригинальной строки, использовав меньше кубитов, чем предполагает показанная Холево оценка. На основе всего этого можно сказать, что такой протокол невозможен.

Почему подобные вещи нас заботят? Ну, может, и не заботят, но я могу сказать, как все это попало в поле моего зрения. Далее мы не будем говорить о квантовых доказательствах, а переключимся на тесно связанную с ними концепцию под названием квантовый совет. Привлечем класс BQP/qpoly — множество задач, эффективно решаемых квантовым компьютером при наличии полиномиального по размеру состояния квантового совета. В чем разница между советом и доказательством? Как уже говорилось в главе 7, совет зависит только от длины входной строки n, но абсолютно достоин доверия, тогда как доказательство зависит от реального входа, но нуждается в проверке.

Таким образом, преимущество совета состоит в том, что вы можете ему доверять, а недостаток — в том, что совет может оказаться менее полезным, чем мы предполагали, поскольку не подгоняется к конкретной реализации задачи, которую вы пытаетесь решить. Поэтому мы можем догадываться, что квантовым компьютерам, возможно, трудно решать NP-полные задачи, но только в том случае, если этому квантовому компьютеру приходится начинать с некоторого нулевого начального состояния. Возможно, существуют кое-какие очень необычные состояния, возникшие в ходе Большого взрыва и все это время просидевшие в какой-нибудь туманности (и каким-то образом не декогерировавшие). Если мы сядем на космический корабль и отыщем эти состояния, они, очевидно, не смогут предвидеть, какую конкретную реализацию SAT мы захотим решить, но они как бы предвидят, что мы захотим решить какую-то ее реализацию. Может ли существовать то самое обобщенное состояние |ψn〉 для решения SAT-задачи, такое, что для любой булевой формулы P размера n мы могли бы, проведя с |ψn〉 некоторые квантовые вычисления, выяснить, удовлетворима ли P? На самом деле мы здесь задаемся вопросом: правда ли NP ⊂ BQP/qpoly?

Что мы можем сказать о мощности BQP/qpoly? Можно адаптировать результат Ватруса в отношении квантовых доказательств к данному квантовому совету. Возвращаясь к задаче о невхождении в группу: если бы Большой взрыв предвидел, вхождение в какую подгруппу нас заинтересует, но не то, какой именно элемент мы будем проверять на вхождение в эту подгруппу, то он мог бы снабдить нас состоянием |H〉, представляющим собой суперпозицию по всем элементам H; после этого мы могли бы проверить на вхождение в H любой элемент, какой захотели бы. Отсюда видно, что по крайней мере какая-то версия задачи о невхождении в группу входит в BQP/qpoly.

Я не упоминал об этом раньше, но мы можем доказать[112], что QMA ⊆ PP, так что, очевидно, существует некий предел мощности QMA. Можно заметить, что в худшем случае вам придется всего лишь перебрать все возможные квантовые доказательства (все возможные состояния из n кубитов) и посмотреть, найдется ли среди них такое состояние, которое наша машина примет. Можно добиться и лучшего результата; именно отсюда возникает оценка PP.

А что с BQP/qpoly? Можете ли вы найти какую-нибудь верхнюю оценку для мощности этого класса? То есть можете ли вы найти какой-то способ обосновать, чего он не может делать?

Знаем ли мы хотя бы, что BQP/qpoly не равен ALL — множеству вообще всех языков (включая невычислимые)? Пусть нам дана экспоненциально длинная классическая строка совета. Несложно убедиться, что в этом случае мы могли бы решить вообще любую задачу. Почему? Потому что пусть f:{0, 1}n → {0, 1} — булева функция, которую мы хотим вычислить. Тогда мы просто объявляем совет полной таблицей истинности для этой функции, и нам достаточно будет найти в этой таблице подходящую строку, чтобы решить любую задачу размера n, какую нам заблагорассудится. Задачу остановки, вообще все что угодно.

В качестве другого примера рассмотрим знаменитую константу Ω, определенную Грегори Хайтином[113]. Неформально Ω есть вероятность того, что «случайно сгенерированная компьютерная программа» остановится, получив на вход пустую строку на некотором фиксированном универсальном по Тьюрингу программном языке. (Технически, чтобы эта вероятность была хорошо определена, программный язык должен быть «самоограничивающим»; это означает, что невозможно создать рабочую программу, добавляя новые биты в конец уже существующей рабочей программы.) Биты двоичной записи Ω можно сравнить едва ли не с божьей премудростью: в них, как сказали бы, максимально эффективным способом зашифрованы ответы на громадное число математических вопросов (гипотеза Гольдбаха, гипотеза Римана и т. п.). Было бы потрясно получить такую штуку в качестве «совета»! (Хотя обратите внимание: с практической точки зрения извлечение из совета интересной информации — о верности или ошибочности гипотезы Гольдбаха и т. п. — потребовало бы невероятного объема вычислений и почти наверняка оказалось бы совершенно непрактичным. На практике, вероятно, вы бы не смогли отличить Ω от простой случайной строки. Но все же: вот глупость!)

Интуитивно сложно себе представить, что BQP/qpoly = ALL, потому что полиномиальное число кубитов совсем не то же самое, что экспоненциальное длинная строка классических битов. Вопрос в том, насколько это «море» экспоненциального количества классических битов, необходимых для описания квантового состояния, определяет то, что мы получим?

Пожалуй, я перейду к главному и расскажу вам, как много лет назад на одном семинаре Гарри Бурман задал мне этот вопрос; мне было очевидно, что BQP/qpoly — это не все, и он попросил меня доказать это. И постепенно я понял, что все, что можно сделать с полиномиального размера квантовым советом, можно сделать и с полиномиального размера классическим советом, если, конечно, вы можете выполнить измерение и затем осуществлять выбор по результатам измерения. Иначе говоря, я доказал[114], что BQP/qpoly ⊆ PostBQP/poly. (Позже, в 2010 г., мы с Эндрю Друкером[115] улучшили этот результат, показав, что на самом деле BQP/qpoly ⊆ QMA/poly, что в определенном смысле дает нам «оптимальную» верхнюю оценку для BQP/poly в терминах класса с классическим советом, при допущении, что BQP/qpoly не является попросту равным BQP/poly. Но пока хватит об этом.) Сухой остаток в том, что все, что вы можете узнать из квантового совета, вы можете узнать и из классического совета сравнимого размера, при условии, что вы готовы тратить экспоненциально больше вычислительных усилий на извлечение информации, которую пытается сообщить совет.

Опять же достаточно будет двух минут, чтобы привести не слишком строгое доказательство того, что BQP/qpoly ⊆ PSPACE/poly. Мне нравится, как Грег Куперберг