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

в 95 % случаев вместо 85 %. Тогда можно исследовать, как эти нелокальности влияют на другие аспекты. К примеру, Брассар с соавторами[193] (опираясь на более ранний результат Вима ван Дама[194]) показали, что наличие достаточно хорошего нелокального устройства (если ошибка достаточно мала) делает сложность коммуникации тривиальной (к примеру, все проблемы коммуникации могут быть решены при помощи одного-единственного бита).

Фундаментальная проблема здесь в том, что нарушение предела Цирельсона действительно можно себе представить, то есть можно представить, что существуют нелокальные корреляции более сильные, чем позволяет квантовая механика, но констатация этого факта не дает нам модели вычисления. Я имею в виду, каковы у нас разрешенные операции? Какое пространство возможных состояний порождает возможность существования нелокальных устройств? Если бы у нас были ответы на эти вопросы, мы могли бы начать думать о вычислительной сложности в этих гипотетических мирах.

Студент: Как вам кажется, не проясняется ли слегка ситуация с классами сложности? А то появляются новые, их становится все больше…

Скотт: Для меня это как спросить у химика, не проясняется ли слегка ситуация с периодической таблицей. Может быть, азот объединится с гелием? В нашем случае даже немного лучше, чем у химиков, мы все же можем надеяться на слияние некоторых классов. Так, мы надеемся и рассчитываем, что P, RP, ZPP и BPP сольются в один класс. Мы надеемся и рассчитываем, что сольются NP, AM и MA, а IP и PSPACE уже слились. Так что да, слияния происходят, но мы также знаем наверняка, что существуют классы, которые не сольются ни при каких обстоятельствах. Так, P отличается от EXP, и из этого сразу следует, что либо P отличается от PSPACE, либо PSPACE отличается от EXP, либо то и другое одновременно. Так что не все может слиться, и это не должно никого удивлять.

Может быть, теория вычислительной сложности пошла не туда, когда стала давать всему названия в виде случайных на первый взгляд сочетаний заглавных букв. Я понимаю, что для непосвященных такие названия выглядят как шифрованные обозначения или юмор «для своих». На самом же деле мы просто говорим о разных концепциях вычислений. Время, объем памяти, рандомность, квантовость, присутствие доказателя. Число классов сложности соответствует числу разных вычислительных концепций. Так что разнообразие зоопарка сложности — всего лишь естественное отражение разнообразия мира вычислений.

Студент: Как вы считаете, BPP сольется с P?

Скотт: О да. Наверняка. У нас есть даже не одна, а несколько достаточно правдоподобных гипотез по поводу нижней оценки схем, о которых известно, что если они верны, то P = BPP. Ведь кое-кто уже в 1980-е гг. понимал, что P должен быть равен BPP. Еще тогда Яо указал, что если бы у нас были достаточно хорошие криптографические генераторы псевдослучайных чисел, то с их помощью можно было бы дерандомизировать любой вероятностный алгоритм; следовательно, P = BPP. В 1990-е гг. работа продолжилась, и тот же вывод делался из все более слабых допущений.

Помимо этого, есть и «эмпирический» вариант. Два из самых впечатляющих результатов последнего десятилетия в области теории сложности — это тест на простоту Аграваля — Кайала — Саксены (AKS), который показывает, что проверка на простоту относится к P, и теорема Рейнгольда о том, что просмотр ненаправленного графа относится к детерминистическому LOGSPACE. Так что идея взять конкретный рандомизированный алгоритм и дерандомизировать его, как мы видим, принесла значительный успех. Она как бы внушает уверенность в том, что если бы мы были достаточно умны или достаточно знали, то справились бы таким же образом и с остальными BPP-задачами. Кроме того, можно взглянуть на конкретный случай, такой как дерандомизация полиномиальной проверки на тождественность. Возможно, это будет хорошей иллюстрацией к сказанному.

Вопрос такой: если дан некоторый многочлен, к примеру x² — y² — (x + y) (x — y), то равен ли он тождественно нулю? В данном случае ответ: да. Но в задаче может фигурировать очень сложный многочлен с переменными в очень высоких степенях, и в таком случае неочевидно, как можно его проверить, даже при помощи компьютера. Если попытаться полностью развернуть выражение, можно получить экспоненциальное число слагаемых.

Однако нам известен быстрый рандомизированный алгоритм для этой задачи, а именно: просто подставляем в выражение какие-то случайные величины (над некоторым случайным конечным полем) и смотрим, соблюдается тождество или нет. Вопрос в том, можно ли этот алгоритм дерандомизировать. То есть существует ли эффективный детерминистический алгоритм для проверки тождественного равенства многочлена нулю? Если немного побиться головой об эту задачу, то довольно быстро заберешься в дебри очень глубоких вопросов алгебраической геометрии. К примеру, можете ли вы предложить небольшой список чисел, таких, что для любого многочлена p(x), описанного небольшой арифметической формулой, достаточно подставить все числа из этого списка, и если p(x) = 0 для каждого из них, то он равен нулю всюду? Вроде бы так должно быть, поскольку все, что вам, по идее, нужно сделать, это выбрать для проверки некоторое «обобщенное» множество чисел, намного превышающее размер формулы для p. К примеру, если выяснится, что p(1) = 0, p(2) = 0, …, p(k) = 0, то либо p тождественно равен нулю, либо он нацело делится на многочлены (x — 1) … (x — k). Но существует ли ненулевое произведение (x — 1) … (x — k), которое можно представить арифметической формулой много меньшего размера, чем k? Это принципиальный вопрос. Если вы можете доказать, что такого многочлена не существует, то вы открываете путь к дерандомизации проверки на тождественность многочлена нулю (а это серьезный шаг к доказательству P = BPP).

Студент: Как вы считаете, не предложат ли три индийских математика элементарное доказательство?

Скотт: Я считаю, что для этого потребуется по крайней мере четыре индийских математика! Мы уже знаем, что если удастся доказать достаточно хорошую нижнюю оценку схемы, то удастся доказать и P = BPP. Но Импальяццо и Кабанец получили результат и в другом направлении: если хотите что-то дерандомизировать, то вам придется доказывать нижние оценки схем. Для меня это объясняет отчасти, почему до сих пор никому не удалось доказать, что P = BPP. Все потому, что мы не знаем, как доказывать нижние оценки схем. Эти две задачи почти — хотя и не совсем — идентичны.

Студент: Следует ли из P = BPP, что NP = MA?

Скотт: Почти. Если вы дерандомизируете PromiseBPP, то дерандомизируете и MA. Никто не знает, как