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

отчасти нас запутывает. Грубая аналогия: правда, что Обама — президент США, и правда также, что если бы Ромни выиграл выборы, то он был бы президентом. Но мы не можем просто не глядя подставить первое из этих уравнений во второе, ведь тогда нам придется заключить, что если бы Ромни выиграл выборы, то он был бы Обамой.

Таким образом, смысл релятивизации в том, что любой метод решения задачи «P или NP» или большинства других главных задач теории сложности просто обязан оказаться чувствительным к присутствию этих оракулов. Звучит не особенно впечатляюще, пока не сообразишь, что почти все знакомые нам методики доказательства не чувствительны к присутствию оракулов. Очень трудно отыскать методику, которая ощущала бы их присутствие, и поэтому — лично для меня — так интересны интерактивные доказательства. Они — ясный и недвусмысленный пример нерелятивизирующего способа, который я могу вам показать. Иными словами, мы можем доказать, что истинно нечто, что не было бы истинно, если бы вы просто снабдили все оракулом. Это можно рассматривать как первый шаг в неизвестность или как свет в конце тоннеля. По результатам интерактивного доказательства мы можем хотя бы очень приближенно судить о том, на что будут похожи доказательства разделения — когда-нибудь, если нам удастся их придумать. Методы интерактивного доказательства кажутся слишком слабыми, чтобы доказывать с их помощью что-нибудь вроде P ≠ NP, иначе вы бы непременно об этом услышали. Однако мы уже можем использовать эти методики для получения кое-каких нерелятивизирующих результатов разделения. Я покажу вам несколько примеров.

Как насчет P и BPP? Все сходятся во мнении, что P и BPP на самом деле равны. От Импальяццо и Вигдерсона[130] мы знаем, что если бы удалось доказать существование задачи, решаемой за время 2n, для чего требуются схемы размером 2cn при некотором c > 0, то можно было бы построить очень хороший псевдослучайный генератор — такой, что его нельзя было бы отличить от случайного при помощи какой бы то ни было схемы фиксированного полиномиального размера. А если у вас есть такой генератор, его можно использовать для дерандомизации любого вероятностного алгоритма, полиномиального по времени. Можно скормить этому алгоритму данные, идущие с выхода псевдослучайного генератора, и алгоритм не сможет отличить его от по-настоящему случайной строки. Из этого следует, что вероятностный алгоритм может быть смоделирован с детерминистских позиций. Таким образом мы, кажется, в самом деле видим разницу между классической и квантовой случайностью. Представляется, что классическую случайность и правда можно эффективно смоделировать при помощи детерминистического алгоритма, тогда как квантовую «случайность» — нельзя. В данном случае интуиция подсказывает, что с классическим рандомизированным алгоритмом всегда можно просто «исключить случайность», то есть рассматривать алгоритм как детерминистический, а случайные биты как часть входного сигнала. С другой стороны, если нам хочется сымитировать квантовый алгоритм, то что может означать выражение «исключить квантовость»?

Итак, давайте посмотрим этот конкретный пример нерелятивизирующей методики. У нас есть булева формула (примерно такая, какие используются в SAT) от n переменных, удовлетворить которую невозможно. Нам хотелось бы получить доказательство ее неудовлетворимости. То есть мы бы хотели убедиться в том, что не существует никакого набора из n переменных, при которых наша формула даст результат «истина». Прежде мы это видели как пример co-NP-полной задачи. Проблема в том, что у нас недостаточно времени, чтобы перебрать все возможные варианты и убедиться, что все они не работают. В 1980-е годы был задан следующий вопрос: «Что, если у нас есть сверхразумный инопланетянин, который прилетает на Землю и может взаимодействовать с нами?» Мы не доверяем этому инопланетянину и его технологиям, но мы бы хотели, чтобы он доказал нам неудовлетворимость формулы таким способом, чтобы нам не нужно было проявлять доверие. Возможно ли это?

В теории вычислительной сложности, когда мы представления не имеем, как ответить на вопрос, мы часто довольствуемся тем, что находим «оракул», который делает ответ однозначным: да или нет. Пусть, к примеру, мы хотим удостовериться в том, что если нам дана булева схема, вычисляющая некоторую функцию f, то не существует полиномиального по времени алгоритма, который принимает в качестве входа описание схемы и надежно находит в f некую конкретную закономерность или регулярность. (Обратите внимание: значительная часть современной криптографии базируется на общепринятых представлениях такого рода!) Проблема в том, что обычно нет никакой надежды доказать подобную гипотезу, не доказав в качестве первого шага P ≠ NP! С другой стороны, очень часто мы можем доказать более слабое утверждение: что никакой полиномиальный по времени алгоритм не может обнаружить закономерность или регулярность, о которой идет речь, если он имеет доступ к f только как к черному ящику. То есть мы можем доказать, что если алгоритм может узнать об f, только выбирая x, а затем узнавая у волшебной подпрограммы значение f(x), то ему потребуется обратиться к этой подпрограмме экспоненциальное число раз.

Вероятно, этот процесс аналогичен тому, что делают физики при вычислениях в рамках теории возмущений. Вы делаете это, потому что можете это делать и еще потому, что это по крайней мере позволяет проверить нашу реальную задачу на непротиворечивость. (Если даже вариант с черным ящиком окажется неверным, то у вашей «настоящей» гипотезы возникнут большие проблемы!)

Именно это проделали в конце 1980-х гг. Фортноу и Сипсер[131]. Хорошо, сказали они, предположим, у вас имеется экспоненциально длинная строка и какой-то пришелец хочет убедить вас в том, что эта экспоненциально длинная строка состоит из одних нулей. То есть в ней вообще нет ни одной единицы. Сможет ли доказатель это сделать? Представим, что из этого могло бы получиться.

Доказатель может сказать:

• В этой строке одни нули.

• Нет, я тебе не верю. Убеди меня.

• Ну вот, смотри, в этой позиции нуль. В этой тоже нуль. Так что в этой…

Ну хорошо, осталось проверить всего лишь 210 000 бит, и тут пришелец говорит:

• Поверь мне, там все нули.

Доказатель мало что может сделать. Фортноу и Сипсер, по существу, формально доказали этот очевидный интуитивный вывод. Возьмите любой протокол обмена сообщениями между вам и доказателем, который заканчивается вашим «да», если вас удалось убедить, или «нет», если вы находите все доводы недостаточно убедительными. Тогда мы могли бы выбрать из строки один случайный бит, тайком поменять его на 1 — и общение почти наверняка пойдет точно так же, как раньше. Вы по-прежнему скажете, что в строке одни нули.

Как всегда, мы можем определить новый класс сложности IP, отнеся