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

Нам нужно просто пробежаться по всем возможным наборам и остановиться, как только попадется подходящий. Считая, что удовлетворяющее размещение существует, получим, что единственные стационарные распределения будут сосредоточены именно на удовлетворяющих размещениях. Так что, делая выборку из стационарного распределения, мы, безусловно, увидим такое размещение. (Если удовлетворяющих наборов нет, то стационарное распределение равномерно.)

Мы считаем, что природа дает нам стационарное распределение бесплатно. Раз уж мы постулируем существование замкнутой времениподобной траектории, ее эволюция просто должна быть непротиворечива с причинно-следственной точки зрения, чтобы избежать проявлений парадокса дедушки. Но это означает, что природе, чтобы сделать ее непротиворечивой, придется решить трудную вычислительную задачу! Это ключевая идея, которой мы пользуемся.

С этим алгоритмом решения NP-полных задач связано и то, что Дойч называет «парадоксом создания знания». Этот парадокс лучше всего иллюстрирует фильм «Звездный путь IV». Экипаж «Энтерпрайза» отправился в прошлое, в наше время (в данном случае в 1986 г.), чтобы найти там горбатого кита и переправить его в двадцать третий век. Но для того, чтобы построить резервуар для кита, им нужен плексиглас особого типа, который еще не был изобретен. В отчаянии они обращаются в компанию, которая должна в будущем изобрести этот плексиглас, и сообщают инженерам компании молекулярную формулу нужного им вещества. А после этого начинают гадать: а как же на самом деле компании удалось разработать этот плексиглас? Хм-ммм…

Обратите внимание: парадокс создания знания неразрывно связан с путешествиями во времени, но принципиально отличается от парадокса дедушки, поскольку здесь нет настоящей логической непоследовательности. Это всего лишь парадокс вычислительной сложности: каким-то образом эта трудная вычислительная задача получила решение, но где именно на ее решение были затрачены усилия? В фильме пресловутый плексиглас появляется на свет и находит применение, хотя никто и никогда не тратит время на его разработку!

Замечу в скобках, что в теме путешествий во времени мне больше всего нравится, как все дружно повторяют: «Будьте осторожны, ни на что не наступайте, иначе вы можете изменить будущее!», «Позаботьтесь о том, чтобы тот парень ушел с той девушкой, как и должен был!» и т. п. Глупости! Наступать можно на что угодно. Даже просто потревожив молекулы воздуха, вы уже все изменили.

Ну хорошо, мы можем эффективно решать NP-полные задачи при помощи путешествий во времени. Но можем ли мы добиться еще чего-нибудь? Какова реальная вычислительная мощность замкнутых времениподобных траекторий? Я утверждаю, что PCTC, бесспорно, входит в PSPACE. Понимаете, почему?

Так, у нас имеется экспоненциально большое множество возможных входных строк x ∈ {0, 1}n схемы C, и наша основная цель — найти вход x, который со временем совершит полный круг (то есть такой, что C(x) = x, или C(C(x)) = x, или…). Для этого случая нам нужно найти стационарное распределение. Но поиск такого x, очевидно, представляет собой задачу из PSPACE. К примеру, мы можем последовательно просчитать по всем возможным начальным состояниям x и для каждого применить C вплоть до 2n раз и посмотреть, получится ли на каком-то шаге вновь x. Разумеется, это тоже задача из PSPACE.

Мое следующее заявление — что PCTC равен PSPACE. То есть компьютеры в замкнутых времениподобных траекториях могут решать не только NP-полные задачи, но и вообще все задачи в PSPACE. Почему?

Ну, пусть M0, M1, … будут последовательные конфигурации машины M из PSPACE. Кроме того, пусть Macc будет конфигурация M типа «остановиться и принять», а Mrej — конфигурация типа «остановиться и отвергнуть». Наша цель — выяснить, в которую из этих конфигураций придет машина. Обратите внимание: для записи каждой из этих конфигураций требуется полиномиальное число бит. Далее, мы можем определить полиномиального размера схему C, которая принимает на вход некоторую конфигурацию M плюс некоторый вспомогательный бит b. Эта схема работает следующим образом:

C(〈Mi, b〉) = 〈Mi+1, b〉

C(〈Macc, b〉) = 〈M0, 1〉

C(〈Mrej, b〉) = 〈M0, 0〉.

Таким образом, для каждой конфигурации, которая не является принимающей или отвергающей, C делает переход в следующее состояние, оставляя вспомогательный бит прежним. Если она достигает принимающей конфигурации, то возвращается к началу и устанавливает вспомогательный бит в единицу. Аналогично если она достигает отвергающей конфигурации, то возвращается к началу и устанавливает вспомогательный бит в 0.

Далее, если подумать о том, что происходит, то получается, что у нас имеется два параллельных вычислительных процесса: в одном бит ответа установлен равным 0, в другом — равным 1. Если истинный ответ равен 0, то отвергающее вычисление будет повторяться в цикле, тогда как принимающее вычисление приведет внутрь петли цикла. Аналогичным образом если истинный ответ равен 1, все будет наоборот: зациклится принимающее вычисление. Следовательно, единственным стационарным распределением будет равномерное распределение по этапам вычисления сb, которому присвоено значение верного ответа. Тогда мы можем прочитать выборку и посмотреть на b, чтобы выяснить, принимает PSPACE-машина или отвергает.

Таким образом, мы можем строго характеризовать класс PCTC как равный PSPACE. Одна из позиций, с которых удобно рассматривать эту ситуацию, состоит в том, что замкнутая времениподобная траектория делает время и пространство как вычислительные ресурсы эквивалентными. Оглядываясь назад, можно заключить, что нам, вероятно, следовало ожидать этого с самого начала, но вообще-то это по-прежнему нужно показать!

Далее, перед нами встает очевидный вопрос: что, если внутри CTC у нас действует квантовый компьютер? Очевидно, нам нужно знать ответ. Как это работает? У нас есть полиномиального размера квантовая схема вместо классической и мы говорим, что у нас есть два набора кубитов: «кубиты замкнутой времениподобной траектории» и «уважающие хронологию кубиты». Мы можем провести кое-какие квантовые вычисления с теми и другими, но нас, откровенно говоря, интересуют только CTC-кубиты.

В этот момент мне необходимо ввести концепцию, с которой мы в этой книге еще не встречались, — концепцию супероператора. Супероператор — это наиболее общий тип операции, разрешенной в квантовой механике; он включает в себя и унитарные преобразования, и измерения как особые случаи. Вообще говоря, любой супероператор можно считать просто гигантским унитарным преобразованием, в котором задействованы как система, над которой мы работаем, так и вторая, «вспомогательная» система (которая в некоторых случаях будет вести себя так, как будто «измеряет» первую систему). По этой причине супероператоры вовсе не меняют правил квантовой механики: это просто удобный способ представить действие на систему A унитарного преобразования, в котором может быть задействована также некоторая другая система B (которая нас на данный момент не интересует). Грубо говоря, супероператоры относятся к