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

сослаться.

Во всяком случае, в терминах классов сложности то, что мы видели выше, означает, что P#P ⊆ IP: в интерактивном протоколе Мерлин может убедить Артура в решении любой задачи из #P и, соответственно, также любой задачи из P#P (поскольку Артур может просто использовать Мерлина вместо #P-оракула). По теореме Тоды это, в свою очередь, означает, что IP содержит PH.

После этого появилась «теорема LFKN», множество людей приняло участие в дискуссии посредством электронной почты, и через месяц Шамир установил, что IP = PSPACE, то есть что IP действительно имеет максимально возможный размер[136]. Я не стану разбирать здесь результат Шамира, но это означает, что если бы на Землю прибыл сверхразумный пришелец, то он сумел бы доказать нам, имеют ли белые или черные в шахматах выигрышную стратегию, или же результат зависит от удачи. Разумеется, он мог бы сыграть с нами и выиграть, но в этом случае мы узнали бы только, что он лучше нас играет в шахматы. Но он мог бы доказать нам, кто из игроков имеет выигрышную стратегию, сведя шахматы к суммированию многочленов над большими конечными полями. (Техническое замечание: это работает только для шахмат с некоторым разумным ограничением на число ходов, таким как «правило пятидесяти ходов», используемое в турнирах.)

Для меня лично это уже достаточно контринтуитивно. Как я уже сказал, это позволяет нам получить хоть какое-то — очень слабое — представление о методиках, которые нам необходимо было бы использовать для доказательства нерелятивизирующих результатов, таких как P ≠ NP. Многие, кажется, думают, что ключевой момент здесь — каким-то образом преобразовать эти задачи из булевых в алгебраические. Вопрос в том, как это сделать. Но я могу показать вам, как эти методики уже позволяют нам получать кое-какие новые нижние оценки. Шутка сказать, даже нижние оценки для некоторых квантовых схем.

Первое утверждение: если мы вообразим, что существуют полиномиального размера схемы подсчета числа удовлетворяющих реализаций булевой формулы и что существует также способ доказать кому-то, чему равно число решений. Понимаете, почему это должно следовать из результата интерактивного доказательства? Ну, обратите внимание: чтобы убедить проверяющего относительно числа подходящих реализаций булевой формулы, доказатель сам по себе не должен иметь большую вычислительную мощность, чем требуется для подсчета числа реализаций. В конце концов, самому доказателю просто приходится все время вычислять эти экспоненциально большие суммы! Иными словами, доказатель для #P может быть реализован в #P. Если бы у вас был #P-оракул, то вы тоже могли бы сыграть роль доказателя. Исходя из этого факта, Лунд с соавторами указали, что если #P ⊂ P/poly, то есть если существует некоторая схема полиномиального по n размера для подсчета числа решений формулы размера n, то P#P = MA. Потому что в MA Мерлин может дать Артуру полиномиальную по размеру схему для решения #P-задач, а затем Артуру достаточно будет просто проверить, что эта схема работает. Для этого Артур просто прогоняет описанный выше интерактивный протокол, в котором играет роли одновременно доказателя и проверяющего, и использует саму схему для моделирования доказателя. Это пример так называемых самопроверяющихся программ. Вам не нужно доверять предполагаемой схеме в подсчете числа решений формулы, поскольку вы можете поставить ее на место доказателя в интерактивном протоколе.

Теперь мы можем доказать, что класс PP, который состоит из задач, решаемых вероятностно за полиномиальное время с неограниченной ошибкой, не имеет схем линейного размера. Этим результатом мы первоначально обязаны Винодчандрану[137]. Почему так? Ну, здесь возможны два случая. Если PP не имеет схем даже полиномиального размера, то все понятно. С другой стороны, если PP все же имеет схемы полиномиального размера, то такие же схемы имеет и P#P, по той простой причине (которую вам, возможно, доставит удовольствие доказать), что P#P = PPP. Далее, P#P = MA по теореме LFKN, так что P#P = MA = PP, поскольку PP зажат между MA и P#P. Но можно доказать (и мы вскоре это сделаем), что P#P не имеет схем линейного размера, при помощи прямой диагонализации. Таким образом, PP тоже не имеет схем линейного размера.

На самом деле вывод даже сильнее: для любого фиксированного k можно найти язык L класса P#P или даже PP, такой, что L невозможно решить схемой размера O (nk). Это совсем не то же самое, что сказать, что в PP имеется единственный язык, не имеющий схем полиномиального размера. Истинность второго утверждения показать невообразимо труднее! Если вы дадите мне свою (полиномиальную) оценку, то я найду PP-задачу, которая окажется не под силу схемам, ограниченным вашей оценкой, но эта задача тем не менее может оказаться решаемой схемами с другой полиномиальной оценкой, побольше. Чтобы выйти за пределы этой новой полиномиальной оценки, мне придется построить новую задачу, и так далее до бесконечности.

А теперь вернемся назад и дополним недостающий шаг в наших рассуждениях. Мы хотим показать для некоторого фиксированного k, что P#P не решаем схемами размера nk. Сколько существует возможных схем размера nk? Где-то около

. Тогда мы можем, посмотрев на поведение всех схем размера nk, определить булеву функцию f. Упорядочим возможные входные строки размера n как x1, …, x2n. Если по крайней мере половина этих схем принимает x1, приравняем f(x1) = 0, а если по крайней мере половина схем отвергает x1, приравняем f(x1) = 1. Это устраняет по крайней мере половину схем размера nk (то есть вызывает ошибку при вычислении f по крайней мере при одной входной строке). Далее, из тех схем, что выдают «верный ответ» для x1, проверим, принимает ли большинство из них x2 или отвергает. Если большинство принимает, приравниваем f(x2) = 0. Если большинство отвергает, приравниваем f(x2) = 1. Это опять же устраняет по крайней мере половину оставшихся схем. Продолжаем этот дарвиновский отбор дальше, и каждый раз, определяя новое значение функции, мы устраняем по крайней мере половину оставшихся схем размера nk. После шагов окажется, что мы устранили все схемы размера nk. Более того, процесс построения f включает полиномиальное число счетных задач, каждую из которых мы можем решить в P#P. Так что конечный результат — задача из P#P, не имеющая, однако, по построению схем размера nk (для любого фиксированного