В главе 5 представлена молодая сестра теории вычислимости – теория вычислительной сложности, которая в дальнейшем играет в книге центральную роль. Я пытаюсь проиллюстрировать, в частности, как вычислительная сложность позволяет нам методично брать «глубокие философские загадки» о пределах человеческого знания и превращать их во «всего лишь» безумно сложные нерешенные математические задачи, в которых, по мнению некоторых, отражается большая часть того, что нам хотелось бы знать! Невозможно придумать лучший пример такого превращения, чем так называемая проблема перебора, или вопрос о равенстве классов сложности P и NP, о котором я расскажу в главе 6. Затем, в качестве разогрева перед квантовыми вычислениями, в главе 7 будут рассмотрены многочисленные применения классического понятия случайности – как в теории сложности вычислений, так и в других областях жизни; а глава 8 объяснит, как при помощи идей из области вычислительной сложности начиная с 1970-х гг. удалось по-настоящему революционизировать теорию и практику криптографии.
Все это – всего лишь подготовка сцены для самой тяжелой части книги – главы 9, в которой представлен мой взгляд на квантовую механику как «обобщенную теорию вероятностей». В главе 10 объясняются основы моей собственной научной области – квантовой теории вычислений, которую можно кратко определить как соединение квантовой механики и теории вычислительной сложности.
В качестве «награды» за упорство глава 11 предлагает критический разбор идей сэра Роджера Пенроуза, убежденного, как известно, в том, что мозг – это не просто квантовый компьютер, но квантовый гравитационный компьютер, способный решать невычислимые по Тьюрингу задачи, и что это или что-то подобное можно показать при помощи теоремы Гёделя о неполноте. Указать на проблемы и недостатки этих идей проще простого, и я это делаю, но еще интереснее, как мне кажется, задаться вопросом о том, не скрываются ли все же в рассуждениях Пенроуза крупицы истины.
В главе 12 рассматривается то, что я считаю главной концептуальной проблемой квантовой механики: не то, что будущее неопределенно (а кому до этого есть дело?), но то, что прошлое также неопределенно! Я разбираю две очень разные реакции на эта проблему: во-первых, популярное среди физиков обращение к декогеренции и «эффективной стреле времени» на базе Второго начала термодинамики; и во-вторых, «теории со скрытыми параметрами», такие как теория волны-пилота (она же теория де Бройля – Бома). Я считаю, что теории со скрытыми параметрами, даже если они будут отвергнуты, ставят перед нами необычайно интересные математические вопросы.
В оставшейся части книги рассматривается приложение всего изложенного выше к тем или иным серьезным, захватывающим или противоречивым вопросам математики, информатики, философии и физики. В этих главах значительно больше, чем в начальных, уделено внимание недавним исследованиям, в основном в области квантовой информации и вычислительной сложности, но также в области квантовой гравитации и космологии; мне представляется, что появляется некоторая надежда пролить свет на эти «коренные вопросы». Поэтому мне кажется, что именно последние главы устареют первыми! Несмотря на кое-какие не слишком существенные логические завязки, в первом приближении можно сказать, что эти последние главы можно читать в любом порядке.
• В главе 13 говорится о новых концепциях математического доказательства (включая вероятностное доказательство и доказательство с нулевым разглашением), а затем рассказывается о приложении этих новых понятий к пониманию вычислительной сложности теорий со скрытыми параметрами.
• В главе 14 поднимается вопрос о «размере» квантовых состояний: действительно ли в них зашифровано экспоненциальное количество классической информации? Кроме того, этот вопрос соотносится, с одной стороны, с дебатами о квантовой интерпретации, а с другой – с недавними исследованиями квантовых доказательств и совета на базе теории сложности.
• В главе 15 разбираются аргументы скептиков квантовых вычислений – тех, кто считает, что создать реальный квантовый компьютер не просто сложно (с чем согласны решительно все!), но невозможно по некоторым фундаментальным причинам.
• В главе 16 разбирается юмова проблема индукции; она используется как трамплин для обсуждения теории вычислительного обучения, а также недавних работ по изучаемости квантовых состояний.
• В главе 17 рассказывается о некоторых прорывных открытиях, меняющих наши представления о классических и квантовых интерактивных системах доказательства (к примеру, о теоремах IP = PSPACE и QIP = PSPACE); в основном эти открытия интересуют нас постольку, поскольку ведут к нерелятивизирующим нижним оценкам сложности схемы и, следовательно, могли бы осветить некоторые аспекты вопроса о равенстве P и NP.
• В главе 18 разбираются знаменитый антропный принцип и «аргумент Судного дня»; дискуссия начинается как сугубо философическая (разумеется), но постепенно сводится к обсуждению квантовых вычислений с постселекцией и теоремы PostBQP = PP.
• В главе 19 обсуждаются парадокс Ньюкома и свобода воли, что выливается в рассказ о «теореме о свободе воли» Конуэя – Кохена и использовании неравенства Белла для генерации «случайных чисел по Эйнштейну».
• глава 20 посвящена путешествиям во времени: разговор уже традиционно начинается с широкой философской дискуссии, а заканчивается доказательством того, что классические и квантовые компьютеры с замкнутыми времениподобными траекториями выдают вычислительную мощность, в точности равную PSPACE (при допущениях, которые открыты для интересных возражений, о чем я расскажу подробно).
• В главе 21 речь пойдет о космологии, темной энергии, пределе Бекенштейна и голографическом принципе, но, что не удивительно, с акцентом на то, что все эти вещи значат для пределов вычислений. К примеру: сколько бит можно сохранить или просмотреть и сколько операций над этими битами можно проделать, не использовав при этом столько энергии, что вместо вычислений возникнет черная дыра?
• глава 22 остается «на десерт»; в ее основе лежит завершающая лекция курса «Квантовые вычисления со времен Демокрита», на которой студенты могли задавать мне абсолютно любые вопросы и смотреть, как я с ними справлюсь. Среди затронутых тем: возможность падения квантовой механики; черные дыры и так называемые пушистые клубки; что дают оракулы в вопросе о вычислительной сложности; NP-полные задачи и творческое начало; «сверхквантовые» корреляции; дерандомизация рандомизированных алгоритмов; наука, религия и природа разума; а также почему информатика не является разделом физики.
И последнее замечание. Чего вы точно не найдете в этой книге, так это рассуждений о практической стороне квантовых вычислений: ни о физической реализации, ни о коррекции ошибок, ни о деталях базовых квантовых алгоритмов, таких как алгоритмы Шора, Гровера и др. Одна из причин такого подхода кроется в случайном обстоятельстве: книга основана на лекциях, которые я читал в Канаде в Институте квантовых вычислений Университета Ватерлоо, и студенты, слушавшие его, уже разбирались со всеми этими аспектами на других курсах. Вторая причина заключается в том, что эти аспекты рассматриваются в десятках других книг[7] и выложенных в сеть лекций (включая и мои собственные), и я не видел смысла изобретать велосипед. Но есть и третья причина: техническая перспектива создания компьютера нового типа, конечно, интересна, но не ради этого я занялся квантовыми вычислениями. (Только тс-с-с, не передавайте моих слов директорам агентств, занимающихся финансированием науки.)
Поясняю. На мой взгляд, вполне вероятно, что я еще увижу при своей жизни действующие квантовые компьютеры (разумеется, возможно также, что и не увижу). И если у нас действительно появятся масштабируемые универсальные квантовые компьютеры, то они почти наверняка найдут себе реальное применение (даже если не говорить о взломе шифров): мне кажется, что по большей части это будут специализированные задачи, такие как квантовое моделирование, и в меньшей степени – решение задач комбинаторной оптимизации. Если это произойдет, я, естественно, обрадуюсь не меньше прочих и буду гордиться, если какие-то результаты моей работы найдут применение в этом новом мире. С другой стороны, если бы кто-то завтра дал мне реальный квантовый компьютер, то ума не приложу, к чему лично я мог бы его применить: в голову лезут только варианты его использования другими людьми!
