В предыдущей главе мы говорили о свободе воли, сверхразумных предсказателях и о том, как доктор Зло на своей лунной базе планирует уничтожить Землю. А теперь я бы хотел поговорить на более приземленную тему: о путешествиях во времени. Первым делом я должен повторить вслед за Карлом Саганом: мы все путешествуем во времени — со скоростью одна секунда в секунду! Ха-ха! Двигаясь дальше, мы должны различать путешествия в отдаленное будущее и путешествия в прошлое. Они очень разные.

Путешествие в отдаленное будущее намного проще второго варианта. Известно несколько способов совершить такое путешествие:

• заморозить себя и оттаять позже;

• полетать с релятивистской скоростью;

• приблизиться к горизонту событий какой-нибудь черной дыры.

Это приводит на память одно из любимых моих предложений на тему решения NP-полных задач за полиномиальное время: можно запустить на компьютере программу решения NP-полной задачи, сесть на космический корабль и полетать на нем с околосветовой скоростью, а затем вернуться на Землю и получить готовое решение. Если бы эта идея сработала, она позволила бы нам решить далеко не только NP. Она также позволила бы нам решать PSPACE-полные и EXP-полные задачи, а может быть, вообще все вычислительные задачи, в зависимости от того, какое ускорение времени вы считаете возможным. Но какие проблемы возникают с таким подходом?

Студент: Земля тоже стареет.

Скотт: Ну да, так что все ваши друзья будут давно мертвы, когда вы вернетесь. Какое здесь может быть решение?

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

Скотт: Ну, по крайней мере взять с собой всех своих друзей!

Предположим, что вы готовы смириться с неудобствами и вернуться на Землю через экспоненциальное число лет. Возникнут ли у вас при этом еще какие-нибудь проблемы? Самая большая проблема заключается в том, сколько энергии требуется на разгон до релятивистских скоростей. Отбросив время, затраченное на разгон и торможение, получим, что если вы путешествуете на скорости, составляющей долю v от скорости света, в течение собственного времени t, то в системе отсчета, связанной с вашим компьютером, пройдет время

Из этого следует, что если вы хотите, чтобы t' было экспоненциально больше, чем t, то v непременно должно быть экспоненциально близко к единице. С этим уже могут возникнуть фундаментальные трудности, связанные с квантовой гравитацией, но пока мы не будем обращать на это внимания. Более очевидная проблема здесь другая: на разгон до скорости v вам потребуется экспоненциальное количество энергии. Представьте себе топливный бак своего корабля или другой источник энергии для него. Он должен быть экспоненциально большим! И просто из соображений локальности: а как топливо из дальних частей бака будет влиять на характеристики корабля и на вас самих? Я здесь использую тот факт, что пространство-время имеет постоянное число измерений. (Вообще-то я, кроме того, пользуюсь пределом Шварцшильда, ограничивающим количество энергии, которую можно хранить в конечном объеме пространства: содержимое вашего топливного бака никак не может быть плотнее черной дыры!)

Поговорим о более интересной разновидности путешествий во времени: о движении вспять. Если вы читали научную фантастику, вы, вероятно, слышали о понятии замкнутых времениподобных траекториях (closed timelike curve, CTC): это области пространства-времени, в которых локально всегда все выглядит так, будто время движется равномерно вперед, а законы физики строго выполняются, но глобально обнаруживается, что время там имеет топологию петли и что, если зайти достаточно далеко в будущее, вновь встретишься с настоящим. Так что это, по существу, всего лишь более цветистый и более эйнштейновский, что ли, способ сказать «путешествие во времени в прошлое».

Но могут ли замкнутые времениподобные траектории реально существовать в природе? Вопрос этот уже очень давно изучают физики всего мира в свободное от работы время. В самом начале Гёдель и другие обнаружили, что классическая общая теория относительности допускает такие решения. Однако все известные решения такого рода содержат элементы, которые можно обвинить в «нефизичности». К примеру, в некоторых решениях имеются так называемые кротовые норы, но для того, чтобы держать их открытыми, требуется «экзотическое вещество» с отрицательной массой[177]. До сих пор все предложенные решения требуют либо нестандартных космологических подходов, либо таких разновидностей вещества или энергии, которые еще только предстоит пронаблюдать в эксперименте. Но это лишь классическая общая теория относительности. Если мы добавляем в картину квантовую механику, вопрос становится еще более сложным. Общая теория относительности — теория не просто о каких-то полях в пространстве-времени, но о самом пространстве-времени, и раз вы его квантуете, то следует ожидать флуктуаций в причинно-следственной структуре пространства-времени. Вопрос звучит так: почему бы этим флуктуациям не породить замкнутые времени-подобные траектории?

Кстати говоря, здесь есть также интересный метавопрос: почему физикам так трудно дается разработка квантовой теории гравитации? Формальный ответ, который обычно приходится слышать, состоит в том, что, в отличие, скажем, от уравнений Максвелла, общая теория относительности не допускает перенормировки. Но мне кажется, есть и более простой ответ, куда более понятный неспециалисту вроде меня. Подлинная суть вопроса заключается в том, что общая теория относительности — это теория самого пространства-времени, так что квантовой теории гравитации придется иметь дело с суперпозициями по пространству-времени и флуктуациями пространства-времени. Один из вопросов, ответы на которые следует ожидать от такой теории, — это вопрос существования замкнутых времени-подобных траекторий. Таким образом, квантовая теория гравитации представляется CTC-трудной в том смысле, что найти ее по крайней мере столь же трудно, как определить, возможны ли в реальности замкнутые времениподобные траектории! И даже мне очевидно, что такой вопрос не может быть тривиальным. Даже если CTC невозможны, их невозможность, вероятно, не удастся доказать без каких-то новых прорывных открытий и достижений. Разумеется, это всего лишь один конкретный пример общей большой проблемы: никто не представляет себе сколько-нибудь отчетливо, что значит рассматривать само пространство-время с квантово-механических позиций.

В той области, где я начинал, не полагается задаваться вопросом о том, существует ли некоторый физический объект; полагается считать, что он существует, и разбираться в том, какие вычисления с ним можно провести. Поэтому начиная с настоящего момента мы будем считать, что замкнутые времениподобные траектории существуют. Какие последствия это вызвало бы в теории вычислительной сложности? Как ни удивительно, на этот вопрос можно дать ясный и конкретный ответ.

Итак, как бы вы использовали замкнутые времениподобные траектории для ускорения вычислений? Во-первых, рассмотрим наивную идею: все просчитать, а затем переслать полученный результат назад во времени, в момент до начала вычислений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

C(〈M_acc, b〉) = 〈M₀, 1〉

C(〈M_rej, b〉) = 〈M₀, 0〉.

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

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

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

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

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

Математически супероператор есть функция S, отображающая смешанное состояние (к примеру, матрицу плотности) ρ на другое смешанное состояние S (ρ). Будем считать для простоты, что ρ и S (ρ) живут в одном и том же числе измерений, хотя даже это правило строго вводить не обязательно. Далее, по правилам супероператор должен иметь вид

где

есть единичная матрица.

Упражнения для неленивого читателя. Докажите, что супероператоры всегда отображают допустимые смешанные состояния (то есть эрмитовы положительные полуопределенные матрицы с рангом 1) на другие допустимые смешанные состояния. Приведите пример супероператора, который (в отличие от унитарного преобразования) может отобразить чистое состояние на смешанное. Чтобы было посложнее, докажите, что любое унитарное преобразование, в котором, возможно, задействована какая-то вспомогательная система, порождает некоторый супероператор и, наоборот, что любой супероператор может быть реализован как унитарное преобразование с возможным участием какой-то вспомогательной системы.

Таким образом, возвращаясь к теме замкнутых времениподобных траекторий, если мы начинаем с глобального унитарного преобразования как кубитов типа CTC, так и кубитов, уважающих причинность, а затем «исключаем» (или игнорируем) хронологически верные кубиты, то у нас остается некоторый выведенный путем индукции супероператор S, который действует на CTC-кубиты. Тогда Природа в противовес ему найдет смешанное состояние ρ, представляющее собой неподвижную точку преобразования S, то есть такую, что S(ρ) = ρ. Не всегда возможно найти чистое состояние ρ = |ψ〉〈ψ| с такой характеристикой, но согласно обычной линейной алгебре (детали проработаны у Дойча) такое смешанное состояние всегда существует.

Упражнение для неленивого читателя. Докажите это.

Итак, ρ есть состояние непосредственно над CTC-кубитами. Единственная реальная причина для существования остальных кубитов — то, что без них супероператор всегда был бы унитарным, а в этом случае максимально смешанное состояние I всегда было бы неподвижной точкой. Это сделало бы модель тривиальной.

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

EXPSPACE наверняка подойдет. Можете ли вы дать более точную верхнюю оценку?

Итак, нам дан n-кубитный супероператор (заданный явно в виде схемы), и мы хотим найти в нем неподвижную точку. По существу, это задача из линейной алгебры. Мы знаем, что вычисления линейной алгебры можно проделать за время, полиномиальное в размерности гильбертова пространства, которая в данном случае равна 2ⁿ. Это подразумевает, что мы можем имитировать BQP_CTC в EXP. Так что мы теперь знаем, что BQP_CTC располагается где-то между PSPACE и EXP. В моем обзорном докладе об NP-полных задачах и физической реальности[179] уточнение положения этого класса было названо главной нерешенной формальной задачей!

Около 2008 г. мы с Джоном Ватрусом сумели эту проблему решить[180]. Мы доказали, что BQP_CTC = P_CTC = PSPACE. Иными словами, если бы замкнутые времениподобные траектории существовали на самом деле, то квантовые компьютеры были бы не мощнее классических.

Студент: Знаем ли мы что-нибудь о других классах с замкнутыми времениподобными траекториями? Таких как PSPACE_CTC?

Скотт: Этот класс тоже совпадает с PSPACE. С другой стороны, нельзя просто взять произвольный класс сложности и приписать к нему индекс CTC. Нужно сказать точно, что это означает, к тому же для некоторых классов (таких как NP) это вообще не имело бы смысла.

В последней части этой главы я могу намекнуть вам, почему BQP_CTC ⊆ PSPACE. Если дан супероператор S, описанный полиномиального размера квантовой схемой, которая отображает n кубитов на n кубитов, то наша цель — вычислить смешанное состояние ρ, такое, что S(ρ) = ρ. Мы не сможем записать ρ явно (получится слишком длинно для памяти PSPACE-машины), но нам и нужно всего лишь имитировать результат некоторого полиномиального по времени вычисления, которое можно было бы произвести над ρ.

Пусть vec(ρ) — «векторизация» ρ (вектор из 2²ⁿ компонент, по одному на каждый элемент матрицы ρ). Тогда существует матрица M размера 2²ⁿ × 2²ⁿ, такая, что S(ρ) = ρ для любого ρ в том и только том случае, когда M vec (ρ) = vec(ρ). Иными словами, мы можем просто расширить все, от матриц до векторов, и затем нашей целью будет найти a + 1 собственный вектор M.

Определим P:= lim_z→1 (1 — z) (I — zM)^–1. Тогда по разложению в ряд Тейлора

Иными словами, P проецируется на неподвижные точки M. Для любых v имеем M(Pv) = (Pv).

Таким образом все, что нам теперь нужно сделать, это начать с какого-нибудь произвольного вектора v, скажем vec(I), где I есть максимально смешанное состояние, и затем вычислить:

Но как применить эту матрицу P в PSPACE? Ну, мы можем применить M в PSPACE, поскольку это всего лишь полиномиальное по времени квантовое вычисление. Но как насчет того, чтобы найти обратную матрицу? Здесь мы заимствуем кое-что из вычислительной линейной алгебры. Алгоритм Чанки, предложенный в 1970-х гг., позволяет нам вычислить матрицу, обратную матрице n × n, не просто за полиномиальное время, но при помощи схемы глубиной log² n. Аналогичные алгоритмы реально используются сегодня, к примеру, при проведении научных расчетов с участием множества параллельных процессоров. Далее, «подняв все наверх» в показатели степеней, мы обнаруживаем, что можно обратить матрицу размером 2²ⁿ × 2²ⁿ при помощи схемы размером 2^O(n) и глубиной O(n²). Но вычисление результата работы схемы экспоненциального размера и полиномиальной глубины (описанной неявно) — это расчет класса PSPACE, более того, это PSPACE-полный расчет. В качестве финального шага можно взять предел при z → 1 при помощи алгебраических правил и еще кое-каких фокусов, за которые мы должны благодарить Бима, Кука и Хувера[181].

Понятно, что я пропускаю здесь многие подробности.

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

Поскольку в первый раз эта глава писалась в 2006 г., с тех пор появились кое-какие интересные продвижения и дополнения в вопросе о CTC-вычислениях, так что мне, пожалуй, следует сейчас «вернуться назад во времени» и рассказать о них! Во-первых, в квантово-вычислительном сообществе возникли споры о том, действительно ли модель причинно-следственной непротиворечивости Дойча — это «верный» взгляд на замкнутые времениподобные траектории. Началось все со статьи Беннетта с соавторами[182], которые указали, что позиция Дойча не учитывает «статистической интерпретации смешанных состояний». Иными словами, если подать состояние ρ = (ρ₁ + ρ₂)/2 на вход CTC-компьютера, результат может не совпасть с тем, что вы получите, если подадите ρ₁ с вероятностью 1/2 и ρ₂ тоже с вероятностью 1/2. Проблема особенно серьезна, если представить, что на вход CTC подается лишь половина от некоторого большего запутанного состояния, — в этом случае нет никакого определенного рецепта на то, что следует делать CTC-компьютеру. С одной стороны, вы могли бы сказать, что это совершенно неудивительно: в конце концов, весь смысл CTC-компьютера состоит в решении трудных задач путем разрушения линейности квантовой механики или даже классической теории вероятностей! А разрушая линейность, вы напрашиваетесь именно на подобного рода неполную определенность. С другой стороны, весьма неприятно все же столкнуться лицом к лицу с неполной определенностью.

Итак, что Беннетт и коллеги предлагают в качестве альтернативы? Их рецепт таков: если вы в принципе хотите говорить об CTC, то вам придется считать, что происходящее внутри замкнутой времениподобной траектории не связано причинными связями ни с чем в остальной Вселенной. В этом случае выходные состояния CTC могут оказаться полезными как «состояния квантового совета» (см. главу 14), но не более того. Так что, согласно Беннетту и компании, аналогом класса сложности BQPCTC на самом деле является подкласс BQP/qpoly. Мою собственную реакцию на это можно обозначить так: да, конечно, можно сделать и так, но по существу это сводится к утверждению о том, что замкнутых времениподобных траекторий не существует! Иными словами, если CTC по Дойчу и правда серьезно «больны», то такое решение проблемы напоминает мне тех медиков, которые способны покончить с болезнью, только убив пациента. Если исключить CTC из динамики, — если оговорить, что природа может снабжать нас определенными статичными «состояниям-советами», которые можно интерпретировать (если захочется) как неподвижные точки супероператоров, но при этом мы не имеем возможности задать свой собственный супероператор S и заставить природу найти для нас неподвижную точку S, — то можно спросить себя, в каком смысле мы все еще говорим об CTC.

Второй крупный залп в войнах при CTC прозвучал в 2009 г. с выходом статьи Ллойда с соавторами[183]. В отличие от группы Беннетта, эти авторы не хотели «определить CTC так, чтобы стало ясно, что их не существует». Они привели теоретическую модель их работы, принципиально отличную от модели Дойча. Поместить чистое состояние |ψ〉 в замкнутую времениподобную траекторию, по существу, означает просто применить к |ψ〉 некоторое преобразование, затем провести проективное измерение, а затем процедурой поствыбора вернуться назад, к тому же состоянию |ψ〉, с которого начали. Если поствыбор пройдет успешно, то можно сказать, что |ψ〉 «прошло сквозь время и встретилось с собой прошлым». Это порождает класс сложности, входящий в PostBQP, то есть квантовый полиномиальный по времени с поствыбором. В самом деле, несложно показать, что получается при этом в точности PostBQP, а это по моей теореме PostBQP = PP (см. главу 18) означает, что вы получаете в точности PP, который считается шире NP, но строго входит в PSPACE. На самом деле Ллойд с соавторами утверждают, что их модель «разумнее» модели Дойча, поскольку Дойч позволяет решать PSPACE-полные задачи полиномиальными средствами, тогда как они позволяют решать «всего лишь» PP-полные задачи! С другой стороны, есть и очевидный аспект, в котором их модель менее разумна, а именно: легко могут существовать поствыбранные измерения, которые имеют успех с нулевой вероятностью. (К примеру, если вы начинаете с кубита в состоянии |0〉, затем применяете к нему операцию не, а затем измеряете его в базисе {|0〉, |1〉}, то вы никогда не найдете его в начальном состоянии.) По этой причине нельзя сказать, что модель Ллойда «разрешает парадокс дедушки» тем же способом, что модель Дойча. В самом деле, единственный способ разобраться с парадоксом дедушки — это считать, что небольшие ошибки всегда приводят к тому, что поствыбранные измерения оказываются успешными с ненулевой вероятностью. Это аналог старой идеи о том, что «если вернуться назад во времени и попытаться убить собственного дедушку, то обязательно обнаружишь, что либо ружье дало осечку, либо еще что-то загадочным образом не позволило вам этого сделать». (Чуть позже мы поговорим об этом подробнее.)

Лично я считаю, что Ллойд с соавторами говорит не столько о самих замкнутых времениподобных траекториях, сколько об определенных поствыбранных квантовомеханических экспериментах, которые «имитируют» или «моделируют» CTC. (В самом деле, одной из особенностей модели Ллойда является то, что по крайней мере при небольшом числе кубитов и умеренно большой вероятности успеха поствыбора требуемые эксперименты можно реально проделать. Более того, они были проделаны[184] и привели к совершенно предсказуемым результатам — и к совершенно предсказуемому недопониманию со стороны популярной прессы, которая честно сообщила, что физики экспериментально продемонстрировали квантовую машину времени.)

Самые большие, вероятно, перемены в моих представлениях об CTC-вычислениях произошли в результате осмысления позиции, которую Дойч изложил в своей первой статье, посвященной CTC. Я же непростительно пропустил этот момент и понял его лишь много позже, когда проводил семинар по теореме BQPCTC = PSPACE и философ науки Тим Модлин (присутствовавший в аудитории) буквально вынудил меня в нем разобраться. Суть в следующем: даже если (1) законы природы позволяют нам реализовать любую полиномиального размера схему C, какую захочется, и (2) нахождение неподвижной точки произвольной полиномиального размера схемы представляет собой PSPACE-полную задачу, это все же не подразумевает непосредственно, что мы могли бы использовать CTC для решения PSPACE-полных задач.

Проблема в том, что моделирование абстрактной схемы C «реальными» законами природы, даже если оно прекрасно работает в мире без CTC, вполне возможно, не сохраняет свойство, согласно которому задача поиска неподвижных точек является PSPACE-полной. Иными словами, не исключено, что законы природы, которые мы используем для реализации схемы, всегда разрешают какой-то «выход» — к примеру, в нужный компьютер попадает метеорит или этот компьютер таинственным образом не включается в нужный момент, — позволяющий сохранить причинно-следственную непротиворечивость внутри CTC, вообще не пуская в ход C. (Это, конечно же, вычислительный аналог «осечки ружья» в случае, если вы отправились в прошлое и пытаетесь убить своего дедушку.) Если так, то при запуске CTC-компьютера вы, возможно, всегда будете получать одну из никому не нужных и вычислительно неинтересных неподвижных точек, которые очень легко находятся.

Здесь вы можете возразить, что даже в обычной жизни, без всяких путешествий во времени, всегда есть вероятность того, что ваш компьютер будет разбит метеоритом или из-за какого-то другого непредвиденного происшествия вполне «реальный» процесс вычисления отклонится от своей абстрактной математической модели! Тем не менее мы, как правило, не считаем, что этот очевидный факт как-то отражается на нашей теории сложности или означает, к примеру, что законы природы вообще не поддерживают универсальных вычислений. Так чем же отличается ситуация в случае присутствия на сцене CTC? Тем, что в этом случае мы делаем кое-что новое и экзотическое: просим природу найти нам неподвижную точку заданного физического процесса, но не говорим, какую именно неподвижную точку. В такой ситуации, если вокруг имеются «обманные» неподвижные точки — те, что не соответствуют никаким неподвижным точкам первоначальной схемы C, которую мы моделируем, и не требуют решения каких бы то ни было трудных вычислительных задач, то почему бы Природе не полениться немного и не выбрать одну из таких точек вместо одной из «трудных» неподвижных точек? Если так, то в присутствии CTC «загадочные» отказы компьютеров были бы нормой, а не экзотической аберрацией.

Чтобы решить эту проблему, необходимо было бы показать, что поиск неподвижной точки в реальных уравнениях эволюции Вселенной — заданных Стандартной моделью, квантовой гравитацией, чем-то еще — является PSPACE-полной задачей (и также что можно в принципе задать нужные начальные состояния). Принципиально важно: здесь недостаточно указать, что законы природы универсальны по Тьюрингу, поскольку легко построить игрушечные образцы «законов природы», универсальных по Тьюрингу, для которых неподвижные точки будут легко находиться. (В качестве иллюстрации представьте, что всякая физическая система содержит «контрольный бит» b и что вселенная осуществляет универсальное вычисление при b = 1 или тождественное при b = 0. Такая вселенная была бы так же способна на универсальное вычисление, как и наша, но при этом она всегда могла бы выдавать фиктивные неподвижные точки, установив b = 0.) Мы с Ватрусом показали лишь, что существуют вычислительно эффективные законы, для которых поиск неподвижных точек — это трудная вычислительная задача, но вопрос о том, относятся ли законы нашей настоящей Вселенной к этой категории, остается открытым.

Интересно отметить, что, по мнению Дойча, CTC не должны позволять решение трудных вычислительных задач. Ведь если бы они это позволяли, то нарушали бы тем самым то, что Дойч называет «эволюционным принципом», — это принцип, согласно которому «знание может возникать только в результате эволюционных процессов» (или, если перевести это на язык теоретической информатики, что NP-полные и другие аналогичные задачи не должны «решаться как по волшебству»). Иначе говоря, Дойч сказал бы, что окончательные законы природы, каковы бы они ни были, непременно воспользуются этими фиктивными неподвижными точками, избавив таким образом природу от необходимости решать PSPACE-полную задачу, чтобы гарантировать непротиворечивость вокруг CTC. Лично мне подобные рассуждении кажутся странными. Если бы замкнутые времениподобные траектории существовали, они, очевидно, заставили бы нас пересмотреть чуть ли не все наши представления о пространстве, времени, причинности и многих других вещах. Что, позвольте спросить, дает Дойчу такую уверенность в том, что эволюционный принцип пережил бы такой переворот, при том что многие другие тоже казавшиеся фундаментальными интуитивные знания не пережили бы? Коли на то пошло, почему не подкрепить эволюционный принцип и еще много чего, просто предположив, что замкнутые времениподобные траектории не могут существовать, — такая гипотеза, судя по всему, полностью согласуется со всем, что нам известно?

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