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

давайте посмотрим, почему. Имея некоторое BPP-вычисление, первое, что мы делаем, — это усиливаем вычисление до экспоненциально малой ошибки. Иными словами, мы повторяем вычисление, скажем, n² раз, а затем выводим ответ, полученный в большинстве случаев, так что вероятность сделать ошибку падает с 1/3 до примерно 2-n². (Если вы пытаетесь доказать что-то относительно BPP, усиление до экспоненциально малой ошибки почти всегда представляет собой удачный первый шаг!)

Далее. Сколько существует входных строк длины n? Верно: 2n. И для каждой входной строки лишь 2-n² доля случайных строк приводит нас к ошибке. Согласно границе объединения (как мы помним, это самый полезный факт во всей теоретической информатике), из этого следует, что не более 2n-n² доли случайных строк вообще могут привести нас к ошибке на входных строках длины n. Поскольку 2n-n²< 1, это означает, что существует некая случайная строка, назовем ее r, которая никогда не вызывает ошибки на входных строках длины n. Так что фиксируем такую r, скармливаем ее в качестве совета машине типа P/poly — и дело сделано!

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

1. Даже если P ≠ NP, вас может заинтересовать, могут ли NP-полные задачи решаться за вероятностное полиномиальное время. Иными словами, входит ли NP в BPP? Понятно, что мы уже можем сказать кое-что конкретное по этому поводу. Если NP ⊆ BPP, то, разумеется, NP ⊂ P/poly (поскольку BPP ⊂ P/poly). Но это означает, что PH схлопывается по теореме Карпа — Липтона. Так что если вы верите, что полиномиальная иерархия бесконечна, то вы верите также, что NP-полные задачи не имеют эффективного решения рандомизированными алгоритмами.

2. Если неоднородность может моделировать случайность, то не может ли она также моделировать квантовость? Иными словами, верно ли, что BQP ⊂ P/poly? Вообще-то мы не знаем, но считается, что скорее всего да. Доказательство Адлемана (что BPP входит в P/poly) полностью рассыплется, конечно, если заменить BPP на BQP. Но это ставит интересный вопрос: а почему оно рассыплется? В чем принципиальная разница между квантовой теорией и классической теорией вероятностей, заставляющая это доказательство работать в одном случае, но не в другом? Я оставлю этот вопрос вам в качестве упражнения.

Ну хорошо, перейдем теперь к глубокой связи. Помните задачу проверки на простоту, о которой речь шла ранее в этой главе? С годами эта задача сползала все ниже и ниже по иерархии сложности, как обезьянка с ветки на ветку:

• Очевидно, что проверка на простоту входит в co-NP.

• В 1975 г. Пратт показал, что она входит в NP.

• В 1977 г. Соловей, Штрассен и Рабин показали, что она входит в co-RP.

• В 1992 г. Адлеман и Хуанг показали, что она входит в ZPP.

• В 2002 г. Аграваль, Кайал и Саксена показали, что она входит в P.

Общий проект по превращению рандомизированных алгоритмов в детерминированные называется дерандомизацией (согласитесь, подобное слово может понравиться только специалисту по теоретической информатике). История задачи проверки на простоту — поистине впечатляющий пример успеха этого проекта. Но с успехом приходит и очевидный вопрос: любой ли рандомизированный алгоритм можно дерандомизировать? Иными словами, верно ли, что P равно BPP?

Опять же мы не знаем ответа на этот вопрос. Обычно, если мы не знаем, равны ли два класса сложности, «по умолчанию» они предполагаются различными. Так было и с P и BPP — зловещая музыка — до последнего времени. Однако в последние полтора десятка лет всё новые появляющиеся свидетельства убедили почти всех нас в том, что P = BPP. Мы не можем здесь сколько-нибудь глубоко разобрать эти свидетельства. Но позвольте мне процитировать одну теорему, просто чтобы показать вам, на что это похоже.

Теорема (Импальяццо — Вигдерсон, 1997)[39]. Пусть существует задача, решаемая за экспоненциальное время и не решаемая за субэкспоненциальное время даже при помощи строки совета субэкспоненциального размера. Тогда P = BPP.

Обратите внимание, как эта теорема связывает дерандомизацию с неоднородностью и, в частности, с доказыванием того, что определенные задачи трудны для неоднородных алгоритмов. Предположение, безусловно, представляется правдоподобным. С нашей сегодняшней точки зрения вывод (что P = BPP) также представляется правдоподобным. И все же впечатление таково, что они не имеют никакого отношения друг к другу. Так что про эту теорему можно было бы сказать: «Если ослы умеют кричать по-ослиному, то свиньи умеют хрюкать».

Откуда берется эта связь между случайностью и неоднородностью? Она исходит из теории генераторов псевдослучайных последовательностей. Мы познакомимся с псевдослучайными генераторами гораздо подробнее в следующей главе, когда будем говорить о криптографии. Но в основе своей псевдослучайный генератор — это всего лишь функция, принимающая на вход короткую строку (называемую зерном) и выдающая на выходе длинную строку таким образом, что если зерно случайно, то выходная строка выглядит случайной. Очевидно, выход не может быть случайным, поскольку в нем недостаточно энтропии: если зерно имеет длину k бит, то возможных выходных строк может быть лишь 2k, независимо от их длины. Однако мы хотим лишь, чтобы никакой алгоритм полиномиального времени не мог успешно отличить выход псевдослучайного генератора от «настоящей» случайности. Разумеется, нам также хотелось бы, чтобы функция, превращающая зерно в выходную последовательность, была вычислима за полиномиальное время.

Уже в 1982 г. Энди Яо понял, что если бы можно было создать «достаточно хороший» псевдослучайный генератор, то можно было бы и доказать, что P = BPP. Почему? Ну предположим, что для любого целого k у вас имеется способ растянуть O(log n) — битное зерно в n-битную выходную псевдослучайную последовательность за полиномиальное время таким способом, что никакой алгоритм, выполняющийся за время nk, не мог бы успешно отличить ее от истинно случайной последовательности. И предположим, у вас есть BPP-машина, работающая за время nk. В таком случае вы можете просто сделать цикл по всем возможным зернам (которых существует лишь полиномиальное количество), скормить соответствующие выходные данные BPP-машине, а затем выдать в качестве результата ответ, составивший большинство. Вероятность того, что BPP-машина принимает, получив на вход псевдослучайную строку, должна быть примерно равна вероятности того, что она принимает, получив на вход по-настоящему случайную строку, поскольку иначе машина легко отличит случайные строки от псевдослучайных, вопреки нашему предположению!

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