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

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

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

• В главе 14 поднимается вопрос о «размере» квантовых состояний: действительно ли в них зашифровано экспоненциальное количество классической информации? Кроме того, этот вопрос соотносится, с одной стороны, с дебатами о квантовой интерпретации, а с другой – с недавними исследованиями квантовых доказательств и совета на базе теории сложности.

• В главе 15 разбираются аргументы скептиков квантовых вычислений – тех, кто считает, что создать реальный квантовый компьютер не просто сложно (с чем согласны решительно все!), но невозможно по некоторым фундаментальным причинам.

• В главе 16 разбирается юмова проблема индукции; она используется как трамплин для обсуждения теории вычислительного обучения, а также недавних работ по изучаемости квантовых состояний.

• В главе 17 рассказывается о некоторых прорывных открытиях, меняющих наши представления о классических и квантовых интерактивных системах доказательства (к примеру, о теоремах IP= PSPACEи QIP= PSPACE); в основном эти открытия интересуют нас постольку, поскольку ведут к нерелятивизирующим нижним оценкам сложности схемы и, следовательно, могли бы осветить некоторые аспекты вопроса о равенстве Pи NP.

• В главе 18 разбираются знаменитый антропный принцип и «аргумент Судного дня»; дискуссия начинается как сугубо философическая (разумеется), но постепенно сводится к обсуждению квантовых вычислений с постселекцией и теоремы PostBQP= PP.

• В главе 19 обсуждаются парадокс Ньюкома и свобода воли, что выливается в рассказ о «теореме о свободе воли» Конуэя – Кохена и использовании неравенства Белла для генерации «случайных чисел по Эйнштейну».

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

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

• глава 22 остается «на десерт»; в ее основе лежит завершающая лекция курса «Квантовые вычисления со времен Демокрита», на которой студенты могли задавать мне абсолютно любые вопросы и смотреть, как я с ними справлюсь. Среди затронутых тем: возможность падения квантовой механики; черные дыры и так называемые пушистые клубки; что дают оракулы в вопросе о вычислительной сложности; NP-полные задачи и творческое начало; «сверхквантовые» корреляции; дерандомизация рандомизированных алгоритмов; наука, религия и природа разума; а также почему информатика не является разделом физики.

И последнее замечание. Чего вы точно не найдете в этой книге, так это рассуждений о практической стороне квантовых вычислений: ни о физической реализации, ни о коррекции ошибок, ни о деталях базовых квантовых алгоритмов, таких как алгоритмы Шора, Гровера и др. Одна из причин такого подхода кроется в случайном обстоятельстве: книга основана на лекциях, которые я читал в Канаде в Институте квантовых вычислений Университета Ватерлоо, и студенты, слушавшие его, уже разбирались со всеми этими аспектами на других курсах. Вторая причина заключается в том, что эти аспекты рассматриваются в десятках других книг [7] Стандартным учебным пособием в этой области остаются «Квантовые вычисления и квантовая информация» Майкла Нильсена (Michael Nielsen) и Айзека Чуанга (Isaac Chuang). и выложенных в сеть лекций (включая и мои собственные), и я не видел смысла изобретать велосипед. Но есть и третья причина: техническая перспектива создания компьютера нового типа, конечно, интересна, но не ради этого я занялся квантовыми вычислениями. (Только тс-с-с , не передавайте моих слов директорам агентств, занимающихся финансированием науки.)