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

уже двигаться дальше. Единственное возражение, которое прежде можно было выдвинуть против результатов применения оракулов, состояло в том, что некоторые из них были попросту тривиальны. Они, по существу, просто сводились к переформулированию вопроса. Но сегодня у нас появились кое-какие очень нетривиальные разделения с применением оракула. Я имею в виду, что можно очень конкретно сформулировать, для чего годятся результаты применения оракула. Приблизительно раз в месяц на сайте arxiv.org я встречаю новую статью, в которой NP-полные задачи решаются на квантовом компьютере за полиномиальное время. Должно быть, это самая простая задача в мире. Такие статьи обычно очень длинны и сложны. Но если вы знаете о результатах работы с оракулами, вам не обязательно читать эти статьи. Это очень полезное приложение. Вы можете сказать: если это доказательство верно, то оно верно и относительно оракулов, а этого не может быть, потому что нам известен оракул, для которого это неверно. Автора такой аргумент, вероятно, не убедит, но, по крайней мере, он может убедить вас.

В качестве еще одного примера я привел оракул, относительно которого класс SZK (статистический, с нулевым разглашением) не входит в BQP. Иными словами, поиск противоречий — трудная задача для квантового компьютера. Конечно, годы идут, и на глаза то и дело попадаются статьи, где авторы рассуждают о том, как находить противоречия при помощи постоянного числа запросов на квантовом компьютере. Я, не читая статью, могу сказать, что нет, так не получится, потому что не происходит ничего нерелятивизирующего. Так что оракулы существуют, чтобы подсказывать вам, какие подходы пробовать не стоит. Они направляют вас к нерелятивизирующим методикам, которые, как нам известно, в конце концов нам непременно потребуются.

Студент: К какому классу сложности принадлежите вы сами?

Скотт: Я не дотягиваю даже до полноценного P. Даже до LOGSPACE! Особенно если не выспался.

Студент: К какому классу сложности относится творчество?

Скотт: Прекрасный вопрос. Я сам только сегодня утром думал об этом. Кто-то спросил, есть ли у человека в голове оракул для NP. Может, у Гаусса или Уайлса был. Но для большинства из нас поиск доказательств — в значительной мере дело случая. Попал или промахнулся… Можно посмотреть и с другой стороны: после трех миллиардов лет естественного отбора и тысячелетий строительства цивилизации, после всех войн и остального, мы можем решить несколько примеров типа SAT — но стоит перейти к гипотезам Римана или Гольдбаха, и внезапно окажется, что это предел, что здесь мы ничего уже решить не можем.

Когда речь заходит о доказательстве теорем, нам приходится иметь дело с очень специальным случаем NP-полной задачи. Вы не просто берете какую-то произвольную формулу полиномиального по n размера, вы берете какой-то фиксированный вопрос фиксированного размера и задаетесь вопросом, имеет ли он доказательство размера n. Так что вы формируете эти примеры для доказательств той длины, что вам нужна. Но даже для таких задач нет убедительных свидетельств того, что у нас имеется какой-то общий алгоритм для их решения. Мало кто готов отказаться от общения и провести всю жизнь по-монашески, в размышлениях о математике. Наконец, таким людям удается решать кое-какие задачи и даже получать иногда за это Филдсовскую премию. Но задач, о которых все знают и которые никто не может решить, вокруг меньше не становится. Так что я бы сказал, что прежде чем вслед за Пенроузом пускаться в рассуждения о том, что математическая изобретательность человека превосходит возможности вычислений, нам следовало бы убедиться, что объективные данные подтверждают гипотезу о том, что человек хорошо умеет отыскивать доказательства. Я в этом, откровенно говоря, не убежден.

Ясно, что в определенных случаях у нас очень хорошо получается находить закономерности или брать задачи, которые кажутся трудными, и раскладывать их на более простые подзадачи. Во многих случаях это у нас получается лучше, чем у любого компьютера. Мы можем задать вопрос: «Почему так?» Это очень серьезный вопрос, но мне кажется, что ответ заключается отчасти в том, что у нас фора в миллиард лет. Миллиард лет естественного отбора снабдил нас отличным набором инструментов эвристики для решения поисковых задач определенного типа. Не всех и не всегда, но в некоторых случаях у нас действительно здорово получается. Как я уже говорил, я считаю, что NP-полные задачи не решаются эффективно в реальной Вселенной; поэтому я уверен, что не может быть машины, которая просто сможет эффективно доказать любую теорему. Тем не менее наверняка возможна машина, которая сможет пользоваться теми же творческими озарениями, какими пользуются математики-люди. Машинам не придется соперничать с Богом, только с Эндрю Уайлсом. Возможно, это проще, но это уже не относится к теории вычислительной сложности; это вопрос искусственного интеллекта.

Студент: Значит, даже если не существует способа решать NP-полные задачи за полиномиальное время, все равно можно считать, что математики-люди устаревают?

Скотт: Конечно. И после того, как компьютеры примут у нас эстафету, возможно, им тоже придется беспокоиться о том, что когда-нибудь появится NP-оракул и оставит их без работы.

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

Скотт: Хороший вопрос, и есть люди, которые над ним думают.

Чтобы немного показать контекст, скажу, что есть важное достижение, известное как неравенство Цирельсона[192], которое можно считать «квантовым вариантом неравенства Белла». Неравенство Белла утверждает, что Алиса и Боб могут выиграть в своеобразной игре под названием CHSH не более чем в 75 % случаев в классической вселенной, но в ~85 % случаев, если у них будут общие запутанные кубиты. А неравенство Цирельсона гласит, что даже при наличии запутанных кубитов все же есть предел возможностям Алисы и Боба: они не могут выигрывать в CHSH-игре более чем в ~85 % случаев, невзирая на тот факт, что даже 100-процентный выигрыш не позволил бы им посылать сигналы быстрее скорости света. Поэтому можно сказать, что ограничения, наложенные квантовой механикой, немного сильнее, чем им «необходимо быть», сильнее, в частности, чем ограничения, связанные с отсутствием обмена информацией.

Итак, примерно десять лет назад возникла тенденция изучения гипотетических «суперквантовых» теорий, в которых нарушалось бы неравенство Цирельсона, но все же не разрешалась бы сверхсветовая коммуникация. Простейший способ добиться этого — постулировать существование так называемых «нелокальных ящиков» — волшебных устройств, позволяющих Алисе и Бобу выигрывать CHSH-игру, скажем,