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

С моей точки зрения, такой «алгоритм» работать не будет, даже если все его условия выполняются. (Приятно, что даже в таких безумных вещах, как путешествия во времени, мы можем со всей определенностью исключить некоторые идеи!) Мне известны по крайней мере две причины, по которым он не работает.

Студент: Вселенная может прекратить существование за время, которое ваш компьютер потратит на поиск ответа.

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

Студент: А нельзя дать компьютеру час на вычисления, затем вернуться во времени на час назад, снова час посчитать, снова вернуться назад — и так до тех пор, пока расчет не будет завершен?

Скотт: Ага! Вы приближаетесь к моему второму аргументу. Это чуть менее наивная идея, она тоже не работает, но более интересным способом.

Студент: Эта наивная идея связана с итерациями по пространству решений, которое может оказаться несчетно большим.

Скотт: Ну да, но будем считать, что мы говорим об NP-полной задаче, так что пространство решений конечно. Если бы мы могли просто решать NP-полные задачи, мы были бы счастливы.

Подумаем еще немного о предложении, где вы считаете в течение часа, затем возвращаетесь на час назад, считаете еще час, вновь возвращаетесь на час назад, и т. п. Проблема с этим предложением в том, что в нем очень легкомысленно говорится о возвращении назад во времени. Вы рассматриваете время как спираль, как какую-то доску, на которой можно писать и стирать написанное, вновь писать и вновь стирать, но ведь на самом деле вы возвращаетесь не в какое-то новое время, вы возвращаетесь в то самое время, с которого начинали. Как только вы поймете, о чем идет речь, и признаете это, вас сразу начнет беспокоить так называемый парадокс дедушки (тот самый, в котором вы попадаете в прошлое и убиваете своего дедушку). К примеру, что, если ваш вычислительный процесс принимает в качестве входа бит b из будущего и производит в качестве выходного сигнала бит ¬b, который затем возвращается в прошлое и становится входным сигналом? Теперь, когда вы используете ¬b в качестве входа, вы получаете ¬¬b = b в качестве выхода, и так далее. Это и есть парадокс дедушки в вычислительной форме. Мы должны предложить некоторое описание того, что происходит в подобной ситуации. Если мы вообще говорим о замкнутых времени-подобных траекториях, то мы говорим о чем-то, в чем такого рода поведение возможно, и мы нуждаемся в какой-то теории о том, что получится в результате.

Мою собственную любимую теорию предложил Дэвид Дойч[178] в 1991 г. Его предложение состояло в том, что, если вы просто обратитесь к квантовой механике, проблема будет решена. На самом деле квантовая механика здесь — излишне мощное оружие; применять его — всего равно что стрелять из пушки по воробьям. Нисколько не хуже работает здесь классическая вероятностная теория. В последнем случае мы имеете некоторое распределение вероятностей (p1, …, pn) над возможными состояниями вашего компьютера. Тогда вычисления, имеющие место в пределах замкнутой времениподобной траектории, можно смоделировать как марковскую цепь, которая преобразует это распределение в другое. Какие условия мы должны поставить, чтобы избежать парадокса дедушки? Верно, условие совпадения выходного и входного вероятностных распределений. Мы также налагаем требование, которое Дойч называет причинно-следственной непротиворечивостью (causal consistency): вычисления в пределах замкнутой времениподобной траектории должны отображать входное распределение вероятностей на себя. В детерминистической физике мы знаем, что такая непротиворечивость не всегда может быть достигнута, — это просто другой способ сформулировать парадокс дедушки. Но как только мы переходим к вероятностным теориям — ну, это базовый факт, что любая марковская цепь имеет по крайней мере одно стационарное распределение. В данном случае парадокса дедушки уникальное решение состоит в том, что вы рождаетесь с вероятностью 1/2, и если рождаетесь, то возвращаетесь назад в прошлое и убиваете своего дедушку. Таким образом, вероятность того, что вы вернетесь назад во времени и убьете дедушку, равна 1/2; следовательно, вы рождаетесь с вероятностью 1/2. Все согласовано; ничто ничему не противоречит; никакого парадокса нет.

Что мне нравится насчет решения Дойча, так это то, что оно сразу же предлагает вычислительную модель. Во-первых, мы должны выбрать полиномиального размера схему C:{0, 1}n → {0, 1}n. Затем природа выбирает распределение вероятностей D над строками длины n, такими, что C(D) = D, и дает нам реализацию y из D. (Если для отображения существует более одной неподвижной точки D, то мы проявим консерватизм и будем считать, что природа делает свой выбор в наихудшем варианте.) Наконец, мы можем провести обычное полиномиальное по времени вычисление над реализацией y. Назовем класс сложности, возникающий на основе этой модели: PCTC.

Студент: Разве мы не должны говорить о BPPCTC, поскольку P не имеет доступа ни к какой случайности, тогда как с замкнутыми времениподобными траекториями мы должны иметь распределение?

Скотт: Это тонкий вопрос: даже при распределении с неподвижной точкой мы можем потребовать, чтобы CTC-компьютер выдавал детерминистический результат (так, чтобы случайность, по существу, использовалась только для того, чтобы избежать парадокса дедушки, и больше ни для чего). С другой стороны, если вы ослабите это требование и разрешите ответу иметь некоторую вероятность ошибки, оказывается, что класс сложности вы получите тот же самый. То есть можно показать, что PCTC = BPPCTC = PSPACE.

Что можно сказать об этом классе сложности? Мое первое утверждение состоит в том, что NP ⊆ PCTC; то есть CTC-компьютеры могут решать NP-полные задачи за полиномиальное время. Понимаете, почему? Или, конкретнее, предположим, что у нас есть булева формула φ с n переменными, и мы хотим знать, существует ли удовлетворяющий набор переменных. Что должна делать наша схема C?

Студент: Если входной сигнал — это удовлетворяющий набор, мы можем кинуть его на выход?

Скотт: Хорошо. А что, если входной сигнал — не есть удовлетворяющий набор?

Студент: Перейти к следующему варианту?

Скотт: Верно! И возвращаемся снова к началу, если добрались уже до последнего