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

пор появились кое-какие интересные продвижения и дополнения в вопросе о CTC-вычислениях, так что мне, пожалуй, следует сейчас «вернуться назад во времени» и рассказать о них! Во-первых, в квантово-вычислительном сообществе возникли споры о том, действительно ли модель причинно-следственной непротиворечивости Дойча — это «верный» взгляд на замкнутые времениподобные траектории. Началось все со статьи Беннетта с соавторами[182], которые указали, что позиция Дойча не учитывает «статистической интерпретации смешанных состояний». Иными словами, если подать состояние ρ = (ρ1 + ρ2)/2 на вход CTC-компьютера, результат может не совпасть с тем, что вы получите, если подадите ρ1 с вероятностью 1/2 и ρ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. (Это, конечно же, вычислительный аналог «осечки ружья» в случае, если вы отправились в прошлое и пытаетесь убить своего