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

чертовски мощные инструменты, но мы можем быть совершенно уверены, что квантовая разновидность мощнее! Я бы даже сказал, что мы можем быть намного более уверены в этом неравенстве, чем в более знакомой гипотезе BPP ≠ BQP, которая основана «всего лишь» на штучках вроде предполагаемой классической трудности разложения на простые множители, что вовсе не настолько «прочно», как бесконечность полиномиальной иерархии.

Но говорит ли это хоть что-нибудь о мощности квантовых компьютеров в «реальном» мире в противоположность гипотетическим мирам с поствыбором? Поскольку в первый раз я писал эту главу в 2006 г., за это время произошли некоторые изменения, появилась новая информация; многое указывает на то, что ответ на этот вопрос: да. А именно: Бремнер, Йожа (Джозза) и Шепард (2011)[162] указали, что если из любого распределения, из которого выборка может быть сделана за квантовое полиномиальное время, она может быть сделана также и за классическое полиномиальное время, то PostBPP будет равен PostBQP, а это (согласно приведенным рассуждениям) вызовет коллапс полиномиальной иерархии. Более того, этот вывод верен даже в том случае, когда мы ограничиваем свободу квантовых вычислений и рассматриваем только те распределения, выборку из которых можно сделать чрезвычайно примитивными и почти наверняка неуниверсальными типами квантовых компьютеров. Примером у Бремнера с соавторами служило то, что они назвали «мгновенным квантовым компьютером», способным лишь применять гамильтониан, представляющий собой сумму тензорных произведений операторов Паули с различными подмножествами кубитов. В другой, независимой работе мы с Алексом Архиповым[163] пришли к такому же выводу для линейно-оптических квантовых компьютеров, где единственное, что вам разрешается делать, — это сгенерировать группу идентичных фотонов, прогнать ее через сложную сеть «пассивных оптических элементов» (то есть расщепителей и фазовращателей), а затем подсчитать, сколько фотонов завершили свой путь в каждой возможной точке. В обоих случаях заканчивается все моделью квантовых вычислений, которая, вероятно, не способна реализовать алгоритм Шора, алгоритм Гровера или любой другой «стандартный» квантовый алгоритм и потому не может, вероятно, даже производить универсальные классические вычисления! Тем не менее в этих моделях вы можете легко генерировать выборки из вероятностного распределения, что невозможно эффективно проделать при помощи классического компьютера, если только не выполняется PostBPP = PostBQP и полиномиальная иерархия не схлопывается. Более того, с технической точки зрения эти модели может оказаться проще реализовать, чем универсальные квантовые вычисления[164].

На данный момент крупнейший теоретический вызов в этой области состоит в том, чтобы показать: даже если классический компьютер мог бы генерировать выборки из приблизительно того же распределения вероятностей, что и квантовый компьютер, то это все же привело бы к схлопыванию полиномиальной иерархии. Главное, что сделали в своей статье мы с Архиповым, — это привели свидетельства в пользу того, что даже это более сильное заявление верно. Но чтобы сделать его строгим, потребуется, судя по всему, серьезное продвижение в классической теории сложности, обращения к теореме PostBPP = PostBQP будет уже недостаточно. На случай, если вам это интересно, мы с Архиповым нашли, что достаточно было бы доказать, что оценка перманента матрицы размера n × n из независимых комплексных гауссовых элементов с высокой вероятностью над матрицей есть #P-полная задача. Уже известно, что аппроксимация перманента произвольной комплексной матрицы есть #P-полная задача и что точное вычисление перманента гауссовой случайной матрицы также #P-полная задача. Так что осталось «только» показать, что задача по-прежнему будет #P-полна даже после того, как мы совместим в ней аппроксимацию и средний случай!

Осталось только дать вам пару загадок, чтобы не было скучно. Мы обсуждали временной аспект и как он вносит дополнительную путаницу в аргумент Судного дня. Одна загадка никак не связана с этим, но тоже внушает тревогу. Эта загадка — тоже авторства Бострома — называется «самонадеянные философы». Представьте, что физики ограничили выбор теории всего и свели его к двум априорно равновероятным вариантам. Главная разница между ними состоит в том, что Теория 1 утверждает, что Вселенная в миллиард раз больше, чем по Теории 2. В частности, считая, что Вселенная относительно однородна (с чем согласны обе гипотезы), Теория 2 предсказывает существование в ней в примерно в миллиард раз больше разумных наблюдателей. Поэтому физики планируют построить огромный ускоритель частиц, чтобы различить две теории; понятно, что проект этот будет стоит много миллиардов долларов. И тут приходят философы и говорят, что Теория 2 верна с вероятностью миллиард к одному, поскольку при условии верности этой теории вероятность нашего существования тоже в миллиард раз больше. Вопрос в том, надо ли давать философам Нобелевскую премию по физике за это «открытие».

Конечно, то, что философы в данном случае опускают, это допущение самоиндикации. Именно сюда приводит нас следование SSA и SIA. SSA — прямой путь к аргументу Судного дня, а SIA — дорога к самонадеянным философам. Похоже, что какой бы вариант вы ни выбрали, следствие получится жутковатое.

Наконец, если мы хотим совместить идею антропных вычислений с аргументом Судного дня, то вот вам загадка Адама и Евы. Предположим, что Адам и Ева — это первые двое наблюдателей и что они очень хотели бы решить какую-нибудь реализацию NP-полной задачи, скажем 3-SAT. Для этого они выбирают некоторое случайное размещение и заранее формируют очень четкое намерение: в случае, если это размещение окажется приемлемым, они не будут заводить детей, а если неприемлемым, то начнут плодиться и размножаться. Примем подход SSA. Тогда, при условии, что выбранное размещение неприемлемо, какова вероятность того, что это именно Адам и Ева а не какие-то из громадного числа будущих наблюдателей? Если предположить, что в конце концов у них будет, скажем, 22n потомков, то вероятность этого, судя по всему, будет не больше 2–2n+1. Таким образом, если поставить условием тот факт, что они и есть двое первых наблюдателей, то SSA предсказывает, что с ошеломляющей вероятностью они выберут приемлемое размещение. Если же вы убежденный байесист, вы можете выбрать SSA или SIA по собственному желанию — и в любом случае смириться с последствиями своего выбора!

19. Свобода воли

Итак, в данной главе мы рассчитываем задать вопрос — и, будем надеяться, ответить на него — о том, существует ли свобода воли. Если вы хотите знать мое мнение, я скажу так: я верю в свободу воли. Почему? Ну, нейроны моего мозга просто срабатывают таким способом, что мой рот открывается и я говорю, что обладаю свободой воли. Какой же у меня выбор?

Прежде чем мы начнем, заметим, что существует два распространенных заблуждения, от которых