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

хокинговского излучения, но процесс, порождающий эти фотоны, нисколько не хуже можно было описать с «комплементарной» позиции Алисы, с ее точки зрения, согласно которой Боба просто размазало по горизонту событий, и он вообще его не прошел! При этом Алисе не придется даже упоминать о «переживаниях» Боба после прохождения горизонта событий. Так что в каком смысле последние часы субъективного осознания себя Бобом — часы между прохождением горизонта событий и попаданием в сингулярность — реально «существуют»? Один Боб знает!

Конечно, вы могли бы возразить, что ситуация здесь не слишком отличается от обычной, в какой находимся мы все и все время по отношению к чужим, не нашим сознаниям. Философски говоря, Алиса не может быть абсолютно уверена в том, что существует «нечто, испытываемое как» быть Бобом, даже если Боб сидит с ней за одним столом в кливлендской квартире, а не несется кувырком в сингулярность черной дыры. Я бы сказал, что здесь, как часто бывает, физика просто «проводит нас по кругу» и вынуждает посмотреть на древнюю философскую загадку с новой стороны, в данном случае — через возможность двух комплементарных описаний, по одному из которых Боба размазывает в блин толщиной порядка планковской длины, а по второму он проживает еще несколько часов.

Оставив в стороне субъективные переживания Боба, заметим, что все современные представления о черных дырах соглашаются, кажется, в одном: нет нужды хотя бы чуть-чуть менять квантовую механику. Да, черные дыры — чудесная и пугающая лаборатория принципов квантовой механики, но очень многое, судя по всему, свидетельствует о том, что в конечном итоге они, как и прочие физические объекты, не противоречат этим принципам. Но если так, если даже самые экстремальные объекты, самые модные источники гравитации во Вселенной не разрушают квантовую механику, то становится гораздо труднее вообразить, что могло бы ее разрушить. Что-то космологическое? Что-то из самого начала времен? Из связи между сознанием и мозгом? Конечно, все возможно, но очень может быть также, что нам придется примириться с возможностью того, что квантовая механика фундаментально верна.

И это наконец приводит меня к главному моменту этого долгого отступления и поводу его завершить. Фигурально выражаясь, физики к настоящему времени заглянули во многие уголки вселенной, но не обнаружили там никаких явлений, которые могли бы образовать класс сложности, превосходящий наши вычислительные возможности сильнее, чем BQP — класс задач, решаемых квантовым компьютером с ограниченной ошибкой за полиномиальное время. Это не значит, что ничего подобного никогда не произойдет, просто BQP оказался чрезвычайно серьезным противником.

Во всяком случае, ориентироваться на физику — «очевидный» способ разобраться с тем, что может быть за BQP. Второй способ — попытаться найти ответ на этот вопрос внутри теории вычислительной сложности. Иными словами, мы можем спросить с чисто математической позиции, какие разумные с виду классы сложности могут быть выше BQP; когда-нибудь, возможно, новая физическая теория сможет правдоподобно их обосновать.

Первое, что мы замечаем, задав этот вопрос, — это то, что вычислительные модели, дающие нам больше чем BQP, дают в большинстве своем намного больше: позволяют решать не только NP-полные задачи за полиномиальное время, но часто даже PP-полные и PSPACE-полные задачи. Именно так происходит, к примеру, при добавлении нелинейностей, поствыбранных измерений или замкнутых времениподобных траекторий. И конечно, хотя все эти модели логически возможны, мне они представляются не просто слишком фантастическими, но и слишком скучными! В прошлом Природа всегда оказывалась коварнее, чем мы ожидали; она всегда находила способ дать нам то, что мы хотели, но не целиком. Итак, предположим, что мы хотим точно знать, что существует нечто более мощное, чем квантовые вычисления, но при этом такое, что все же не может решать NP-полные задачи за полиномиальное время. Сколько у нас тогда «места» для такой модели? У нас действительно есть задачи, которые вроде бы проще NP-полных, но все же слишком сложны, чтобы эффективно решаться квантовым компьютером. Два примера таких задач — это изоморфизм графа и проблема кратчайшего вектора. Они очень «близки» к NP-полным, но, вероятно, все же не совсем; представляется, что эти задачи сводятся к инвертированию односторонних функций и различению функций случайных и псевдослучайных.

Много лет назад я предложил пример вычислительной модели (обсуждается в главе 12), в которой вы видите всю историю скрытой переменной в ходе квантового расчета. Я привел свидетельства того, что в этой модели вы действительно получаете больше, чем при обычных квантовых вычислениях, — к примеру, вы решаете задачи об изоморфизме графа и об аппроксимации кратчайшего вектора, — но по-прежнему не можете решать NP-полные задачи. С другой стороны, признаю, что моя модель была довольно искусственной. Так что, возможно, прежде чем дойти до NP-полных задач, нам все же придется сделать еще один драматический шаг, но я в этом не уверен.

Студент: Откуда вы знаете, что шаг этот один? Теоретически между двумя задачами всегда можно втиснуть еще одну.

Скотт: Разумеется, но вот какое дело: никто не интересовался квантовыми вычислениями, когда Бернштейн и Вазирани выяснили, что с их помощью можно решить задачу рекурсивной выборки Фурье. Интерес возник только тогда, когда обнаружилось, что таким способом можно решать задачи, которые и раньше считались важными, такие как разложение на простые множители. Так что если мы оценим нашу гипотетическую новую модель по тем же стандартам и спросим себя, какие задачи из тех, что мы считаем важными, она может решить, то, возможно, окажется, что между разложением на простые множители и NP-полной задачей их вмещается не так уж много. Опять же может существовать какая-то модель, которая позволит нам зайти чуть дальше BQP, скажем решить задачу об изоморфизме графа или задачу о скрытой подгруппе еще для нескольких неабелевых групп, но, по современным представлениям, «место» между BQP и NP-полными задачами ограничено.

Студент: Откуда вообще берутся оракулы?

Скотт: Их просто определяют. Пусть A — оракул…

Студент: Ничего себе!

Скотт: Ну да, ну да. Мне всегда странно, почему только компьютерщиков критикуют так остро за использование при поиске ответов на вопросы методик, которые имеются в их распоряжении. Вот физики говорят, что собираются провести какой-то расчет в рамках теории возмущений. «О! Конечно, что тут еще сделаешь? Это глубокая и сложная задача». Разумеется, нужно делать то, что работает. Специалисты по теоретической информатике говорят, что мы не можем пока доказать, что P ≠ NP, но мы попробуем исследовать этот вопрос в релятивизированном мире. «Это нечестно!» Представляется очевидным, что начинать всегда нужно с результатов, которые вы можете доказать, и оттуда