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

Просуммируем сказанное. Мы хотели получить эффективный алгоритм, который проверял бы программу, целиком состоящую из операций сложения, вычитания и умножения, и определял бы, получится ли в результате вычислений 0. Я дал вам такой алгоритм, но он нуждается в случайности в двух местах: во-первых, при выборе некоторого случайного числа и, во-вторых, при проверке этого случайного числа на простоту. Оказалось, что второе применение случайности не принципиально, поскольку у нас теперь есть детерминированный полиномиальный по времени алгоритм проверки на простоту. Но как быть с первым использованием случайности? Может быть, в нем тоже нет нужды? Так вот, по состоянию на 2013 г. никто этого еще не знает! Но орудия главных теоретических калибров уже долбят эту проблему, и ситуация легко может измениться. Справьтесь о том, как развивается эта ситуация, в материалах вашей местной конференции по теоретической информатике.

Отлично, пора нам определить кое-какие классы сложности. (Да, если подумать, когда не пора это делать?)

Когда мы говорим о вероятностных вычислениях, скорее всего, речь идет об одном из следующих четырех классов сложности, которые Джон Гилл[34] определил в работе, опубликованной в 1977 г.

• PP (Probabilistic Polynomial-Time, вероятностный за полиномиальное время). Ну да, видимо, даже сам Гилл признавал, что это сокращение не самое удачное. Оно ведь произносится… нет, у нас серьезная книга, и я не допущу юмора на уровне седьмого класса. В сущности, PP — это класс всех проблем разрешимости, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью большей 1/2, если ответ «да», либо меньшей 1/2, если ответ «нет». Иными словами, мы представляем себе специфическую машину Тьюринга M, получающую не только n-битную входную строку x, но и неограниченный источник случайных битов. Если x — это «да-строка», то по крайней мере половину случайных битовых данных M должна принимать; тогда как если x является «нет-строкой», то по крайней мере половину случайных битовых данных M должна отвергать. Более того, M должна останавливаться после некоторого числа шагов (число это обязано быть полиномиальным по n).

Вот стандартный пример PP-задачи: если дана булева формула Φ с n переменными, то дает ли по крайней мере половина из 2n возможных комбинаций входных переменных результат «истина»? (Кстати говоря, в точности как поиск ответа на вопрос, существует ли удовлетворительная входная комбинация, относится к числу NP-полных задач, так и здесь можно показать, что задача с голосованием является PP-полной, то есть любая другая PP-задача эффективно сводится к ней.)

Хорошо, почему же тогда PP не стыкуется с нашим интуитивным представлением о задачах, решаемых рандомизированными алгоритмами?

Верно: потому что мы хотим избежать ситуаций типа «флоридского пересчета»[35]! Там, где речь идет о PP, алгоритм волен принимать с вероятностью 1/2 + 2—n, если ответ «да», и вероятностью 1/2 — 2—n, если ответ «нет». Но как простому смертному различить эти два случая в реальности? Если n равняется, скажем, 5000, то нам придется накапливать статистику за период времени, превышающий возраст Вселенной!

Кроме того, PP — чрезвычайно большой класс, к примеру, он определенно включает в себя NP-полные задачи. Почему? Ну, если дана булева формула φ с n переменными, вы можете сделать так: с вероятностью 1/2 — 2–2n принять не глядя, а в противном случае выбрать случайное размещение и принять его в том и только том случае, если оно удовлетворяет φ. Тогда полная вероятность принятия у вас получится больше 1/2, если по крайней мере одно выполнимое размещение для Φ существует, и меньше 1/2, если такого размещения не существует.

По факту специалисты по теории вычислительной сложности считают, что PP строго больше NP, хотя, как обычно, доказать этого мы не можем.

Приведенные выше соображения заставили Гилла определить более «разумный» вариант PP, вот такой.

• BPP (Bounded-Error Probabilistic Polynomial-Time, вероятностный за полиномиальное время с ограниченной ошибкой). Это класс проблем разрешимости, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью большей 2/3, если ответ «да», или меньшей 1/3, если ответ «нет». Иными словами, при любых входных данных такой алгоритм может ошибаться с вероятностью не более 1/3.

В отношении 1/3 важно исключительно то, что это какая-то положительная константа, меньшая 1/2. Любая такая константа подошла бы не хуже. Почему? Ну, предположим, нам задан BPP-алгоритм, который ошибается с вероятностью 1/3. При желании мы можем без труда модифицировать этот алгоритм так, чтобы он ошибался с вероятностью не более, скажем, 2–100. Как?

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

На самом деле мы не просто могли бы заменить 1/3 любой другой константой, меньшей 1/2; мы могли бы даже заменить ее на 1/2 — 1/p(n), где p — произвольный полином.

Так что же такое BPP? Если хотите, это класс всех задач, которые возможно решить при помощи компьютера во Вселенной, где правит классическая физика.

• RP (Randomized Polynomial-Time, рандомизированный, полиномиального времени). Как я уже говорил, вероятность ошибки алгоритма BPP можно без труда уменьшить до такой степени, что она будет меньше вероятности попадания астероида в ваш компьютер. И этого достаточно для большинства приложений: скажем, для отслеживания доз облучения в больнице, для шифрования многомиллиардных банковских операций или для управления пусками ядерных ракет. Но как насчет доказывания теорем? В некоторых приложениях рисковать просто нельзя.

Вот тут-то мы и приходим к RP — к классу задач, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью более 1/2, если ответ «да», или с вероятностью нуль, если ответ «нет». Сформулируем иначе: если алгоритм принимает хотя бы раз, то вы можете быть абсолютно уверены, что ответ «да». Если алгоритм отвергает варианты один за другим, то вы можете очень уверенно предполагать (но не гарантировать), что ответ «нет».

У RP есть очевидное «дополнение», называемое co-RP. Это просто класс задач, для которых существует рандомизированный алгоритм за полиномиальное время, который принимает с вероятностью 1, если ответ «да», или с вероятностью менее 1/2, если ответ «нет».

• ZPP (Zero-Error Probabilistic Polynomial-Time, вероятностный, полиномиального времени, с нулевой ошибкой). Этот класс может быть определен как пересечение RP и co-RP — класс