Читать онлайн книгу «Квантовые вычисления со времен Демокрита» автора Скотт Ааронсон

Издательство благодарит Российский квантовый центр и Сергея Белоусова за помощь в подготовке издания

Все права защищены. Произведение предназначено исключительно для частного использования. Никакая часть электронного экземпляра данной книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, включая размещение в сети Интернет и в корпоративных сетях, для публичного или коллективного использования без письменного разрешения владельца авторских прав. За нарушение авторских прав законодательством предусмотрена выплата компенсации правообладателя в размере до 5 млн. рублей (ст. 49 ЗОАП), а также уголовная ответственность в виде лишения свободы на срок до 6 лет (ст. 146 УК РФ).

* * *

Предисловие

Критический обзор книги Скотта Ааронсона «Квантовые вычисления со времен Демокрита», Написанный им самим

«Квантовые вычисления со времен Демокрита» – достойный кандидат на звание самой странной книги, когда-либо опубликованной издательством Кембриджского университета. Ее необычность начинается с названия, которое загадочным образом не объясняет, о чем, собственно, говорится в этой книге. Быть может, это очередной учебник по квантовым вычислениям – модной области науки на стыке физики, математики и информатики, которая уже лет двадцать обещает миру новый тип компьютера, но пока не создала реального устройства, способного на что-нибудь более впечатляющее, чем разложение 21 на множители 3 × 7 (правда, с высокой вероятностью)? Если так, то что добавит именно эта книга к десяткам других, в которых уже изложены основы теории квантовых вычислений? Или, может быть, эта книга – наивная попытка связать квантовые вычисления с историей древнего мира? Но какое отношение может иметь Демокрит – древнегреческий философ-атомист – к книге, содержание которой по крайней мере наполовину было бы откровением для ученых даже в 1970-е годы, не говоря уже о IV веке до н. э.?

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

Трудно, однако, избежать подозрения в том, что «Квантовые вычисления со времен Демокрита» – это, по существу, «дамп памяти»: не особенно систематизированная коллекция мыслей о теории вычислительных систем, физике, математике и философии, которые присутствовали в сознании автора осенью 2006 г., когда он прочел серию лекций в Университете Ватерлоо; из этих лекций и выросла данная книга. Ее материал объединяет скучноватый юмор автора, его «сократический» подход к каждому вопросу и его одержимость теорией вычислений и тем, как она соотносится с физическим миром. Но если в книге и присутствует некий главный «тезис», который должен вынести из нее читатель, то я, хоть убейте, не могу его сформулировать.

Можно также задаться вопросом, на какого читателя рассчитана данная книга. С одной стороны, она намного глубже, чем полагается быть популярной книге. Как и «Путь к реальности» Роджера Пенроуза, – чье предисловие обещает легкую прогулку даже тем читателям, которым в начальной школе плохо давались дроби, но первые же несколько глав заводят неосторожного в дебри голоморфных функций и расслоённых пространств, – «Квантовые вычисления со времен Демокрита» не годятся для людей с фобией к математике. Разумеется, любопытный дилетант сможет извлечь из этой книги немало информации, но при этом он (или она) должен быть готов пропускать некоторые особо темные места, – возможно, для того, чтобы вернуться к ним позже. Так что если вы из тех, кто может переварить «научный текст» только после того, как из него тщательно вычистили всю науку, вам лучше поискать что-нибудь другое.

С другой стороны, книга получилась также слишком многотемной, легкомысленной и своеобразной, чтобы ее можно было использовать как учебник или справочник. Конечно, в ней есть теоремы, доказательства и упражнения и она охватывает основы поразительного числа научных областей, таких как логика, теория множеств, вычислимость, сложность, криптография, квантовая информация и теория вычислительного обучения. Представляется, что студенты высших учебных заведений в любой из этих областей, от предпоследнего курса и выше, могли бы обогатиться при помощи этой книги ценной информацией – или использовать ее в качестве занимательного самоучителя или курса переподготовки. Помимо основ, в книге содержится также значительный материал по квантовой теории сложности, к примеру о силе квантовых доказательств и совета, что (насколько известно автору настоящего обзора) нигде больше не в виде книги не издавалось. Но все же книга перескакивает с предмета на предмет слишком поспешно, чтобы ее можно было считать каноническим текстом на какую-либо тему.

Итак, для кого же предназначена эта книга? Неужели для неспециалистов, которые в реальности не пройдут дальше первой главы, но которые захотят впечатлить гостей, положив такую интеллектуальную книгу на журнальный столик? Я вижу лишь одну иную возможность: существует определенная аудитория (как правило, ей уделяют мало внимания) у научных книг, которые нельзя отнести ни к «популярной», ни к «профессиональной» категории. Речь идет о книгах, которые описывают участок интеллектуального ландшафта с позиции некоего исследователя (весьма предвзятой) и пользуются при этом примерно тем же языком, каким этот исследователь мог бы обсуждать свою тему в коридоре университета с коллегой из другой научной области. Возможно, помимо упомянутых коллег, эта гипотетическая «неохваченная аудитория» могла бы включать одаренных студентов или, скажем, программистов и инженеров, которым в университете нравились теоретические курсы и которые хотят выяснить, что в соответствующей области появилось нового. Возможно, это та же аудитория, что регулярно посещает «научные блоги», о которых мне приходилось слышать: онлайновые площадки, где кто угодно может, судя по всему, наблюдать, как настоящие ученые, люди с переднего края человеческого познания, занимаются мелкими дрязгами, обзывают друг друга и демонстрируют другие формы подросткового поведения. Там можно даже спровоцировать ученых и вынудить их показать себя с еще более неприглядной стороны. (Следует отметить, что автор книги ведет особенно эпатажный и скандальный блог такого рода.) Если такая аудитория действительно существует, то, быть может, автор знает, что делает, когда обращается к ней. Однако мне кажется, что автор получил при подготовке этой книги слишком много удовольствия, чтобы поверить, что он руководствовался сколько-нибудь проработанным планом.

А теперь – настоящее предисловие

Хотя я ценю добрые слова автора рецензии о моей книге (и даже о моей внешности!), которые вы могли видеть на предыдущих страницах, я при всем том категорически возражаю против высказанного им невежественного утверждения о том, что в книге «Квантовые вычисления со времен Демокрита» нет обобщающего тезиса. Он в книге есть – хотя, как ни странно, не я первым сумел понять, в чем он состоит. За формулировку центральной мысли этой книги я должен поблагодарить Love Communications – рекламное агентство из Сиднея (Австралия), вложившее эту мысль в уста гламурных моделей с целью повышения продаж принтеров.

Позвольте мне рассказать эту историю – она того стоит.

В 2006 г. я читал курс «Квантовые вычисления со времен Демокрита» в Университете Ватерлоо. В течение следующего года я выкладывать краткие заметки по этому курсу в своем блоге Shtetl-Optimized[1] – именно из этих заметок позже сложилась данная книга. Меня тогда воодушевил энтузиазм, с которым заметки были встречены читателями блога; должен сказать, что именно реакция читателей убедила меня опубликовать их в виде книги. Но был один отклик, который ни я, ни кто-либо другой не мог предвидеть заранее.

1 октября 2007 г. я получил электронное письмо от некоего австралийца по имени Уоррен Смит, который писал, что видел по телевизору интересную рекламу принтеров Ricoh. В ней, продолжал он, две девушки-модели в гримерной вели следующий диалог:

Первая модель: Но если квантовая механика – это не физика в обычном смысле слова, если она не занимается ни веществом, ни энергией, ни волнами, то чем же она занимается?

Вторая модель: Ну, с моей точки зрения, она занимается информацией, вероятностями, наблюдаемыми величинами и тем, как все они соотносятся между собой.

После этого в ролике вспыхивал слоган: «Наша модель умнее», после которого появляется изображение принтера Ricoh.

Смит сообщил, что заинтересовался происхождением столь необычного рекламного текста и стал гуглить его. Поиск привел его к девятой главе моих конспектов на тему «Квантовые вычисления со времен Демокрита», где он обнаружил следующий пассаж:

Но если квантовая механика – это не физика в обычном смысле слова, если она не занимается ни веществом, ни энергией, ни волнами, ни частицами, то чем же она занимается? С моей точки зрения, она занимается информацией, вероятностями, наблюдаемыми величинами, и еще тем, как все они соотносятся между собой.

Оказалось, что в рекламном диалоге присутствовала ровно одна фраза, которую написал не я («Как интересно!»). Смит нашел ссылку[2], по которой я смог сам увидеть этот рекламный ролик на YouTube, и вся история подтвердилась.

Меня это больше позабавило, нежели рассердило. Я сделал в блоге запись под заголовком «Австралийские актрисы сплагиатили мою лекцию по квантовой механике, чтобы продавать принтеры»[3]. После изложения происшедшего и ссылки на видео пост заканчивался так:

Едва ли не впервые в жизни я не нахожу слов. Я не знаю, как на это реагировать. Не знаю, какую из 500 000 возможных шуток выбрать. Помогите мне, читатели. Должен ли я чувствовать себя польщенным? Или, может быть, пора звонить юристу?

Этому посту суждено было стать самым популярным из всех, когда-либо мной написанных. На следующее утро эта история попала на страницы в Sydney Morning Gerald («Профессор: "Рекламное агентство сплагиатило запись моей лекции"»[4]), на сайт Slashdot («Скотт Ааронсон рекламирует принтеры»[5]) и еще на нескольких новостных сайтах. Я в тот момент находился в Латвии в гостях у своего коллеги Андриса Амбайниса, но журналистам удалось каким-то образом меня разыскать в рижской гостинице; меня разбудили в пять утра, чтобы взять интервью.

Тем временем реакция читателей в моем блоге и на других онлайн-форумах оказалась смешанной. Некоторые говорили, что я поступлю глупо, если не подам в суд на рекламное агентство и не получу с него максимально возможную компенсацию. Что, если бы они вставили в свой рекламный ролик несколько тактов из какой-нибудь песни Rolling Stones, не получив предварительно на то разрешения? Выплаты по подобным процессам, заверили меня, иногда составляют миллионы долларов. Другие читатели утверждали, что сама постановка вопроса делает меня стереотипным американцем-сутяжником, воплощением всех недостатков этого мира. Я должен чувствовать себя польщенным, продолжали они, что авторы рекламного текста сочли нужным дать моим взглядам на квантовую механику такую бесплатную рекламу. В десятках комментариев мне в разных выражениях предлагалась одна и та же пошлая шутка: потребовать в качестве компенсации свидание с «моделями». (На это я ответил, что, если уж говорить о компенсации, предпочел бы получить бесплатный принтер.) Кто-то из комментаторов написал просто: «Да уж, не исключено, что эта история – самое смешное, что когда-либо происходило».

Love Communications, со своей стороны, признали, что использовали в рекламе текст моей лекции, но заявили, что консультировались с юристом и были уверены, такая практика не выходит за рамки добросовестного использования. Я тем временем все-таки связался с австралийским юристом, специализирующимся на интеллектуальных правах, и он сказал, что мое дело вполне может оказаться выигрышным, но участие в процессе потребует усилий и времени. Я колебался: с одной стороны, плагиат – один из немногих непростительных грехов научного мира, да и бесцеремонный ответ рекламного агентства, пойманного на горячем, вызвал у меня раздражение. С другой стороны, если бы они меня спросили, я, вероятно, с радостью разрешил бы им использовать свои слова – либо за символическую сумму, либо вообще бесплатно.

В конце концов мы нашли решение, которое понравилось всем. Love Communications извинились (не признавая при этом, что поступили неправильно) и пожертвовали 5000 долларов двум австралийским научно-просветительским организациям, которые я назвал[6]. В ответ я отказался от всяких дальнейших действий и почти что забыл об этой истории и вспоминаю теперь о ней только тогда, когда коллеги начинают надо мной подшучивать, вспоминая австралийских моделей (им это никак не надоест).

Но замечательна эта история – и потому я ее здесь пересказываю (ну, помимо того, что это подлинная забавная история, связанная с этой книгой) – что если бы мне нужно было выбрать из всей книги один абзац для телепередачи, я, кажется, выбрал бы именно тот, что выбрали копирайтеры агентства, хотя они, вероятно, просто просматривали книгу по диагонали в поисках какой-нибудь наукообразной ерунды, а я никак эту мысль не выделил, поскольку даже не задумался о ее важности.

Идея о том, что квантовая механика занимается информацией, вероятностями и наблюдаемыми величинами, а вовсе не волнами и частицами, безусловно, нельзя назвать оригинальной. Физик Джон Арчибальд Уилер говорил нечто подобное еще в 1970-е гг.; сегодня вокруг этой идеи построена вся научная область, связанная с квантовыми вычислениями и информацией. В самом деле, во время дискуссии в моем блоге, развернувшейся после эпизода с австралийскими моделями, один из наиболее частых аргументов (и наиболее забавных, по-моему) состоял в том, что мне, по существу, не на что жаловаться, поскольку заимствованный отрывок не отличался ничем особенным; в нем высказана очевидная мысль, которую можно найти в любой книге по физике!

Как бы мне хотелось, чтобы это было действительно так! Даже сегодня, в 2013 г., взгляд на квантовую механику как на теорию информации и вероятностей остается в общем и в целом точкой зрения меньшинства. Возьмите почти любую книгу по физике – хоть популярную, хоть теоретическую, и вы узнаете, что (а) в современной физике полно парадоксальных на первый взгляд утверждений, к примеру что волны – это частицы, а частицы – это волны, (б) никто по-настоящему глубоко этих вещей не понимает, (в) даже на перевод их на язык математики требуются годы интенсивной работы, но (г) благодаря им атомные спектры удается рассчитать правильно, а именно это, в конце концов, и важно.

Так, красноречивое изложение этого «традиционного взгляда» можно найти в книге Карла Сагана «Мир, полный демонов»:

«Предположим, вы решили всерьез разобраться в квантовой механике. Сначала нужно овладеть математическим аппаратом, целым рядом математических дисциплин, каждая из которых подводит к следующей, более высокой ступени. Арифметика, геометрия Евклида, алгебра по программе старших классов, дифференциальное и интегральное исчисление, дифференциальные уравнения, обычные и в частных производных, векторное исчисление, некоторые специальные функции математической физики, матричная алгебра и теория групп… Нелегка задача популяризатора науки, который захочет дать широкой публике, не прошедшей весь этот обряд посвящения, хоть какое-то представление о квантовой механике. На мой взгляд, удачных популяризаций квантовой механики просто не существует, и отчасти по этой самой причине. На все эти математические сложности накладывается тот факт, что квантовая теория демонстративно контринтуитивна. Подходить к ней, вооружившись здравым смыслом, почти бесполезно. Как говорил в свое время Ричард Фейнман, бессмысленно спрашивать, почему так. Этого никто не знает. Так устроено, и все тут».

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

Лично я просто верю экспериментаторам, когда они говорят, что мир устроен и работает совершенно иначе, чем я себе представлял. Дело не в том, чтобы убедить меня. Кроме того, я не пытаюсь предсказывать, что экспериментаторы откроют в следующий раз. Единственное, что я хочу знать: Что случилось с моей интуицией? Как мне ее поправить, чтобы интуиция не слишком расходилась с результатами экспериментов? Как мог бы я рассуждать, чтобы реальное поведение мира не удивляло бы меня так сильно?

Если говорить о нескольких предыдущих научных революциях – о ньютоновой физике, дарвиновой эволюции, о специальной теории относительности, то я, как мне кажется, примерно представляю себе ответы на приведенные вопросы. И если моя интуиция пока еще не до конца приспособилась даже к этим теориям, то я, по крайней мере, знаю, как ее нужно настроить. А потому, если бы я, к примеру, создавал новую вселенную, я мог бы сделать ее инвариантной или не инвариантной относительно преобразований Лоренца, но я определенно рассмотрел бы такую возможность и я бы понял, почему Лоренц-инвариантность является неизбежным следствием пары других свойств, которые мне могли бы понадобиться для новой вселенной.

Но с квантовой механикой все иначе. Здесь, уверяют нас физики, никто не знает, как нужно настроить интуицию, чтобы поведение элементарных частиц перестало казаться столь безумным. Более того, не исключено, что такого способа просто не существует; может быть, субатомное поведение навсегда останется для нас всего лишь произвольным грубым фактом, и нам нечего будет сказать о нем, помимо того, что «такие-то и такие-то формулы дают верный ответ». Моя реакция на это достаточно радикальна: если это правда, то мне нет дела до того, как ведут себя элементарные частицы. Несомненно, кому-то другому необходимо это знать, к примеру тем, кто разрабатывает лазеры или транзисторы, – так пусть они и изучают. Что до меня, я просто займусь изучением какого-нибудь другого предмета, более мне понятного, скажем теории вычислительных систем. Сказать мне, что моя физическая интуиция не работает, и не дать никакого способа скорректировать эту интуицию, – все равно что завалить меня на экзамене и даже не намекнуть, в чем дело и как можно было бы добиться лучшего результата. Как только появится возможность, я просто переключусь на другие курсы, где у меня есть возможность заработать высший балл, где моя интуиция работает.

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

Квантовая механика – это красивое обобщение законов вероятности, обобщение, основанное скорее на второй норме, нежели на первой, и скорее на комплексных, нежели на неотрицательных действительных числах. Ее можно изучать совершенно отдельно от ее приложения к физике (более того, такое изучение обеспечивает хороший старт для последующего изучения приложений к физике). Эта обобщенная теория вероятностей естественным образом приводит нас к новой вычислительной модели – к модели квантовых вычислений, которая бросает вызов всем нашим идеям, связанным с вычислениями и считавшимся прежде само собой разумеющимися. Эту модель специалисты по теории вычислительных систем могли бы предложить и сами для собственного удобства, даже если бы она не была связана с физикой. Короче говоря, хотя квантовая механика была придумана сто лет назад для решения технических проблем физики, сегодня ее можно плодотворно объяснить с совершенно иной точки зрения: как часть истории идей в математике, логике, вычислительных системах и философии, идей о пределах познаваемого.

В этой книге я попытаюсь выполнить сделанные обещания, двигаясь к цели неторопливым кружным путем. Наш путь начнется в главе 1 настолько близко к «началу», насколько это возможно, – с древнегреческого философа Демокрита. Дошедшие до нас фрагменты трудов Демокрита, который рассуждает, в частности, о том, что все природные явления проистекают из сложных взаимодействий между несколькими разновидностями крохотных «атомов», стремительно летающих в пустом по большей части пространстве, ближе к современному научному мировоззрению, чем что бы то ни было в античности (и много ближе, чем любые идеи Платона и Аристотеля). Но стоит Демокриту сформулировать атомную гипотезу, как он замечает с тревогой, что она стремится «целиком поглотить» тот самый чувственный опыт, который он как будто пытался объяснить с самого начала. Каким образом его можно свести к движению атомов? Демокрит изложил эту дилемму в форме диалога между Разумом и Чувствами:

Разум: Только по договоренности между людьми существует сладость, по договоренности – горечь, по договоренности – цвет, на самом деле существуют только атомы и пустота.

Чувства: Глупый разум! Неужели ты стремишься ниспровергнуть нас, хотя именно от нас получаешь все данные?

Этот обмен репликами служит, по существу, краеугольным камнем всей книги. Одной из тем для моих рассуждений будет то, что квантовая механика снабжает, судя по всему, и Разум, и Чувства новыми аргументами в их 2400-летнем споре, хотя по-прежнему (я так считаю) не обеспечивает чистой победы ни для одной стороны.

В главах 2 и 3 я перехожу к обсуждению самой глубокой из всех имеющихся у нас областей знания, совершенно намеренно не зависящей от «грубых фактов» об окружающем мире, а именно математики. Даже здесь что-то внутри меня (и, как я подозреваю, внутри многих других компьютерщиков!) с подозрением относится к тем разделам математики, которые несут на себе явный отпечаток физики, – это, к примеру, дифференциальные уравнения в частных производных, дифференциальная геометрия, группы Ли и что угодно еще, выглядящее «слишком непрерывным». Поэтому я начинаю с самых «нефизических» разделов математики, известных на данный момент, – с теории множеств, логики и вопросов вычислимости. Я рассказываю о великих открытиях Кантора, Фреге, Гёделя, Тьюринга и Коэна, которые помогли нанести на карту контуры математических рассуждений как таковых и которые – в процессе демонстрации причин, по которым всю математику невозможно свести к фиксированному «механическому процессу», – продемонстрировали также, сколь значительную часть ее все же можно свести к такому процессу; заодно удалось прояснить, что, собственно, представляет собой сей «механический процесс». Поскольку я никак не могу от этого удержаться, в главе 4 я углубляюсь в давний спор о том, не сводится ли работа человеческого разума к «устоявшимся механическим процессам». Я стараюсь излагать позиции сторон в этом споре как можно беспристрастнее (хотя мои собственные пристрастия, несомненно, тоже заметны).

В главе 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] и выложенных в сеть лекций (включая и мои собственные), и я не видел смысла изобретать велосипед. Но есть и третья причина: техническая перспектива создания компьютера нового типа, конечно, интересна, но не ради этого я занялся квантовыми вычислениями. (Только тс-с-с, не передавайте моих слов директорам агентств, занимающихся финансированием науки.)

Поясняю. На мой взгляд, вполне вероятно, что я еще увижу при своей жизни действующие квантовые компьютеры (разумеется, возможно также, что и не увижу). И если у нас действительно появятся масштабируемые универсальные квантовые компьютеры, то они почти наверняка найдут себе реальное применение (даже если не говорить о взломе шифров): мне кажется, что по большей части это будут специализированные задачи, такие как квантовое моделирование, и в меньшей степени – решение задач комбинаторной оптимизации. Если это произойдет, я, естественно, обрадуюсь не меньше прочих и буду гордиться, если какие-то результаты моей работы найдут применение в этом новом мире. С другой стороны, если бы кто-то завтра дал мне реальный квантовый компьютер, то ума не приложу, к чему лично я мог бы его применить: в голову лезут только варианты его использования другими людьми!

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

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

Что нового

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

Чтобы проиллюстрировать развитие вещей, позвольте мне привести неполный список достижений, о которых пойдет речь в книге, но о которых не могла идти речь на лекциях 2006 г. по той простой причине, что события эти на тот момент еще не произошли. Компьютер Watson фирмы IBM выиграл у чемпиона мира по «Своей игре» Кена Дженнингса, вынудив меня дополнить разговор об ИИ новым примером (см. главу 4), совершенно иным по характеру, чем предыдущие, такие как ELIZA и Deep Blue. Вирджиния Василевская-Уильямс, опираясь на работы Эндрю Стозерса, нашла способ перемножить две матрицы n × n с использованием всего O(n^2,373) шагов, слегка превзойдя при этом результат Копперсмита и Винограда O(n^2,376), который держался так долго, что число 2,376 начало уже восприниматься как природная константа (см. главу 5).

Достаточно серьезные события произошли в области криптографии на решетках, которая представляется самой перспективной базой для создания систем шифрования с открытым ключом, устойчивых даже против квантовых компьютеров (см. главу 3). Следует особо отметить, что Крейг Джентри смог решить задачу, которая никому не давалась 30 лет: он использовал решетки, чтобы предложить первые полностью гомоморфные криптосистемы. Эти системы позволяют клиенту доверить любые вычисления незащищенному серверу, при этом на сервер передаются зашифрованные входные данные, а обратно получаются зашифрованные результаты, и только сам клиент может расшифровать результат и удостовериться в его подлинности; сервер же не получает никакой информации о том, что именно ему поручили считать.

Если говорить об основах квантовой механики, Чирибелла с соавторами (см. главу 9) привели новый аргумент в пользу того, «почему» в квантовой механике должны действовать именно такие правила. А именно: они доказали, что только эти правила совместимы с некоторыми общими аксиомами теории вероятностей и одновременно с немного загадочной аксиомой о том, что «любые смешанные состояния могут быть очищены», то есть всякий раз в том случае, когда мы знаем о физической системе A не все, что можно знать, наше незнание должно полностью объясняться предположением о корреляциях между A и некоторой далекой системой B, такой, что мы должны иметь полные данные об объединенной системе AB.

В теории квантовых вычислений задача Бернштейна – Вазирани о «рекурсивной выборке Фурье», которой в лекциях 2006 г. я посвятил довольно много времени, была вытеснена моей задачей о «проверке коэффициентов Фурье» (см. главу 10). Задача Бернштейна – Вазирани осталась в истории как первая когда-либо предложенная задача с черным ящиком, которую квантовый компьютер доказуемо может решить сверхполиномиально быстрее, чем классический вероятностный компьютер, и, следовательно, как важный предшественник прорывных открытий Саймона и Шора. Но сегодня, если нам потребуется кандидат на роль задачи класса BQP/PH, иными словами, задачи, которую квантовый компьютер может решить с легкостью, но которая вообще не входит в классическую «полиномиальную иерархию», то представляется, что «проверка коэффициентов Фурье» во всех отношениях превосходит «рекурсивную выборку Фурье».

Несколько задач, которые излагались в моих лекциях 2006 г. как нерешенные, успели с тех пор изменить свой статус. Так, мы с Эндрю Друкером показали, что класс BQP/qpoly входит в класс QMA/poly (к тому же доказательство получилось релятивизирующее), опровергнув тем самым мою гипотезу о том, что эти классы должны различаться по оракулам (см. главу 14). Кроме того, произошел справедливо отмеченный прорыв в теории квантовых вычислений: Джайн с соавторами доказал, что QIP = PSPACE (см. главу 17); это означает, что квантовые интерактивные системы доказательства не мощнее классических. В этом случае я по крайней мере угадал правильный ответ!

(На самом деле был еще один прорыв в исследовании квантовых интерактивных систем доказательства, о котором я не буду рассказывать в этой книге. Недавно мой постдок Томас Видик вместе с Цуёси Ито[8] показал, что NEXP ⊆ MIP*; это означает, что любую интерактивную систему доказательства с многими доказателями можно «привить» против того, чтобы эти доказатели втайне скоординировали свои отклики посредством квантовой запутанности.)

В главе 20 этой книги обсуждается предложенная Дэвидом Дойчем модель квантовой механики в присутствии замкнутых времениподобных траекторий, а также мой и Джона Ватруса новый (на тот момент) вывод о том, что модель Дойча обеспечивает в точности вычислительную мощность PSPACE. (Отсюда, в частности, следует, что путешествующие во времени квантовые компьютеры оказались бы не более мощными, чем классические компьютеры того же назначения, если вас почему-то интересовал этот вопрос.) Однако после 2006 г. вышли новые важные статьи, в которых подвергаются сомнению предположения, положенные в основу модели Дойча, и предложены альтернативные модели, что, как правило, ведет к вычислительной мощности меньшей, чем PSPACE. К примеру, одна из моделей, предложенная Ллойдом с соавторами, «всего лишь» позволит путешественнику во времени решить все задачи класса PP! Об этих достижениях речь пойдет в главе 20.

А что с нижними оценками сложности схемы (для специалистов по теоретической информатике это, по существу, кодовое слово, обозначающее «попытку доказать P ≠ NP», точно так же как для физиков «замкнутые времени подобные траектории» – кодовое слово для обозначения путешествий во времени)? Рад сообщить, что и здесь после 2006 г. имеются интересные подвижки – безусловно, более серьезные, чем можно было тогда ожидать. В качестве примера скажу, что Рахул Сантханам при помощи интерактивных методик доказательства получил нерелятивизирующий результат, согласно которому класс PromiseMA не имеет схем какого бы то ни было фиксированного полиномиального размера (см. главу 17). Результат Сантханама, в частности, побудил меня и Ави Вигдерсона в 2007 г. сформулировать теорему о барьере алгебраизации (см. там же) – обобщение теоремы о барьере релятивизации Бейкера, Гилла и Соловея, сформулированной еще в 1970-е гг. (см. так же главу 17). Алгебраизация объясняет, почему методики интерактивного доказательства в попытке доказать P ≠ NP позволяют нам лишь дойти до определенного предела и не более того – к примеру, почему эти методики привели к сверхлинейной нижней оценке сложности схемы для класса PromiseMA, но не для класса NP, который всего лишь «чуть ниже его». Мы поставили задачу разработки новых методик поиска нижней оценки сложности схемы, которые позволяли бы убедительно обойти барьер алгебраизации. Эту задачу решил в 2010 г. Райан Уильямс своим прорывным доказательством того, что NEXP ⊄ ACC⁰ (речь об этом идет в главе 17).

Конечно, даже интереснейший результат Уильямса чертовски далек еще от доказательства P ≠ NP. Но в последние шесть лет наблюдается еще и растущий интерес – и, соответственно, прогресс – к программе создания геометрической теории сложности Кетана Мулмулея (см. главу 17); теория эта играет для доказательства P ≠ NP почти в точности ту же роль, что теория струн в физике для цели создания Теории Всего. То есть, если говорить о конкретных результатах, программа геометрической теории сложности пока даже отдаленно не приблизилась к конечному результату, и даже самые рьяные ее сторонники предсказывают несколько десятилетий кропотливой работы, тогда как остальных просто отпугивает ее математическая сложность. В активе этой программы две вещи: во-первых, то, что она создает математические связи, «слишком глубокие и поразительные, чтобы их можно было считать простым совпадением», и во-вторых, то, что (хотя так считают далеко не все!) на безрыбье и рак рыба и что это единственный реальный претендент на успех, имеющий хоть какие-то шансы.

Позвольте мне упомянуть еще три открытия, сделанных после 2006 г. и важных для содержания этой книги.

В 2011 г. мы с Алексом Архиповым предложили «бозонную выборку» (см. главу 18) – рудиментарную, почти наверняка не универсальную модель квантовых вычислений с участием невзаимодействующих фотонов, которая совсем недавно была продемонстрирована в небольшом масштабе. Уверенность в том, что бозонную выборку трудно смоделировать на классическом компьютере, кажется, даже выше, чем в том, что трудно смоделировать (к примеру) алгоритм Шора разложения на множители.

В 2012 г. Умеш Вазирани и Томас Видик, опираясь на более ранние работы Пиронио с соавторами, показали, как можно использовать нарушения неравенства Белла для достижения экспоненциального расширения случайности (см. главу 19), то есть превращения n случайных бит в 2n бит, которые гарантированно будут почти совершенно случайными, если только Природа не воспользуется сверхсветовой связью, чтобы их изменить.

Тем временем дебаты об «информационном парадоксе черной дыры» – то есть об очевидном конфликте между принципами квантовой механики и локальностью пространства-времени, когда биты и кубиты падают в черную дыру, – развивались с 2006 г. в новых направлениях. Самыми, возможно, важными достижениями здесь стали возросшая популярность и подробность модели черной дыры как «пушистого клубка», выдвинутой Самиром Матхуром, и спорное утверждение Алмхейри с соавторами о том, что наблюдатель, падающий в черную дыру, никогда даже не приблизится к сингулярности, а встретит на своем пути «огненную стену» и сгорит на горизонте событий. Я в меру своих сил расскажу об этих достижениях в главе 22.

Несколько дополнений и изменений в книге объясняются не какими-то новыми открытиями или аргументами, а просто тем, что я (ну надо же!) изменил мнение о чем-то. Один из примеров – мое отношение к аргументам Джона Сёрла и Роджера Пенроуза против «сильного искусственного интеллекта». Как вы увидите в главах 4 и 11, я по-прежнему считаю, что Сёрл и Пенроуз неправы в принципиальных моментах, причем Сёрл в большей степени, нежели Пенроуз. Но я, перечитав свой текст 2006 г., посвященный причинам, по которым они неправы, испытал неприятное чувство. Мне не понравился мой легкомысленный тон, моя готовность посмеяться над этими знаменитыми учеными, пытающимися завернуться в логический крендель в отчаянной и очевидно обреченной попытке обосновать человеческую уникальность. В результате я пребывал в ленивой уверенности, что все вокруг заранее согласны со мной: что для (по большей части) физиков и специалистов по информатике попросту самоочевидно, что человеческий мозг есть не что иное, как «горячая и влажная машина Тьюринга», – и считал, что глупо тратить лекционное время на такой давно решенный вопрос. С тех пор, кажется, я лучше проникся невероятной сложностью этих вопросов, и в частности необходимостью выдвигать такие аргументы, которые действовали бы на людей отличных от моей философских позиций.

С надеждой на то, что в 2020 г. эта книга будет так же сильно нуждаться в переработке, как нуждаются в ней сегодня, в 2013 г., конспекты лекций 2006 года,

Скотт Ааронсон, Кембридж (штат Массачусетс), январь 2013 г.

Благодарности

Мой практикант 2008 года Крис Гранад с энтузиазмом взялся за превращение разрозненных конспектов и аудиозаписей в полноценные черновики, которые я смог выложить у себя на сайте, – и это стало первым шагом на их долгом пути к превращению в книгу. После этого Алекс Архипов, мой замечательный докторант в MIT, прошелся по черновикам частой гребенкой и отметил места, которые были неверны, непонятны или не представляли более интереса. Я глубоко благодарен им обоим: эта книга одновременно и их книга, она бы не появилась без их помощи.

Она бы также не была возможна без Саймона Кейплина, моего издателя из Cambridge University Press (CUP), который предложил мне идею книги. Саймон понял, что мне нужно: он дергал меня раз в несколько месяцев, чтобы проверить, насколько я продвинулся, но никогда не давил на меня и всегда полагался на мое внутреннее чувство вины, чтобы увидеть конец в работе над проектом. (И в конце концов я его увидел.) Саймон также заверил меня в том, что хотя «Квантовые вычисления со времен Демокрита»… несколько отличны от обычных для издательства книг, он приложит все усилия для того, чтобы сохранить, как он выразился, ее «нетривиальное очарование». Я также благодарен другим сотрудникам CUP и компании Aptara Corp., которые помогли мне сделать книгу реальностью, – это Сара Хэмилтон, Эмма Уолкер и Диша Малхотра.

Я выражаю благодарность студентам и членам факультета, которые слушали мой курс «Квантовые вычисления со времен Демокрита» в Университете Ватерлоо в осеннем семестре 2006 года. Их вопросы и аргументы сделали курс таким, какой он есть, и вы увидите это в книге, особенно в ее последних главах. Ну и самое главное: студенты сделали аудиозаписи и первые конспекты. Говоря в целом, я вспоминаю два постдоковских года в Институте квантовых вычислений (IQC) Университета Ватерлоо как один из самых счастливых периодов своей жизни. Я благодарю всех, и в особенности директора IQC Рея Лафламма, за то что они не только разрешили мне читать столь безумный курс, но и сподвигли меня на это, и даже – это касается Рея и некоторых других – лично сидели на лекциях и подавали много ценных идей.

Я благодарен Лаборатории вычислительных систем и искусственного интеллекта MIT и его кафедре электротехники и вычислительных систем, а также Национальному научному фонду США, Агентству перспективных оборонных проектов DARPA, Фонду Слоана и компании TIBCO Inc. за всю ту поддержку, которые они оказывали мне на протяжении последних шести лет.

Спасибо читателям моего блога Shtetl-Optimized (http://www.scottaaronson.com/blog) за многочисленные комментарии к черновым главам, которые я там выкладывал, и за обнаружение множества ошибок. Я особенно благодарен тем из читателей, которые предлагали мне превратить этот курс лекций в книгу, – некоторые из них даже обещали купить ее, когда она выйдет.

Я благодарен тем людям, которые были моими учителями от старших классов школы и до постдока, – это Крис Линч, Барт Селман, Лав Гровер, Умеш Вазирани и Ави Вигдерсон. Джон Прескилл не был «формально» моим научным руководителем, но я считаю его таковым. Всем им я обязан больше, чем могу выразить.

Я также благодарен всем тем в сообществе квантовой информации и теоретической информатики и за его пределами, дискуссии и споры с которыми на протяжении многих лет нашли отражение в этой книге. Наверно, я не смогу составить полный список этих людей, но вот по крайней мере часть: Дорит Ааронов, Андрис Амбайнис, Майкл Бен-Ор, Гарри Бурман, Рафаэль Буссо, Дейв Бэкон, Майкл Вассар, Джон Ватрус, Дэниел Готтесман, Рональд де Вольф, Дэвид Дойч, Энди Друкер, Ричард Карп, Эльхам Кашефи, Джулия Кемпе, Ричард Клив, Грег Куперберг, Шон Кэрролл, Сет Ллойд, Микеле Моска, Майкл Нилсен, Христос Пападимитриу, Одед Регев, Ленни Сасскинд, Барбара Терхал, Грег Хайтин, Алекс Халдерман, Робин Хэнсон, Эд Фахри, Крис Фукс, Лен Шульман. Я прошу меня простить за неизбежные пропуски (а те, кто не хочет увидеть своих имен в этой книге, срочно сообщите!).

Я благодарен первым читателям, нашедшим ошибки в первом тираже книги. Это Эван Берковитц, Боб Гейлслут, Эрнест Дэвис, Эндрю Маркс, Крис Мур и Тайлер Сингер-Кларк.

Наконец, я хочу сказать спасибо маме и папе, моему брату Дэвиду и, конечно, моей жене Дейне, которая наконец-то познакомится со мной в состоянии, когда я не занят завершением этой чертовой книги.

1. Атомы и пустота

Я предпочел бы найти одно причинное объяснение, нежели стать царем персов. Демокрит

И все же почему Демокрит? Начнем с самого начала: кто такой Демокрит? Какой-то древнегреческий чувак. Он родился где-то около 450 г. до н. э. в том самом скучном провинциальном греческом городке под названием Абдера, о котором афиняне говорили, что сам воздух в нем порождает глупость. Согласно моему источнику, а именно Википедии, он был учеником Левкиппа. Его называют досократиком, хотя на самом деле он был современником Сократа. Это дает некоторое представление о том, какое ему придается значение: «Ну да, досократики… может, стоит упомянуть о них на первой лекции курса». Кстати, существует легенда о том, что Демокрит однажды посетил Афины специально для того, чтобы встретиться с Сократом, но при встрече с ним попросту не осмелился назвать свое имя.

До нас не дошло почти ничего из трудов Демокрита. Кое-что оставалось еще до Средних веков включительно, но к настоящему времени оказалось утрачено. Сведения о нем мы получаем в основном от других философов (к примеру, от Аристотеля), которые упоминают Демокрита, чтобы покритиковать его.

Что же они критикуют? Демокрит считал, что вся Вселенная состоит из атомов в пустоте, которые непрерывно движутся по вполне определенным и доступным для понимания законам. Эти атомы могут сталкиваться друг с другом и отскакивать при столкновении, а могут слипаться в более крупные объекты. Они могут иметь разный размер, вес и форму – может быть, некоторые из них представляют собой сферы, некоторые – цилиндры, а некоторые – еще что-нибудь. С другой стороны, Демокрит утверждает, что свойства вещей, такие как цвет и вкус, не определяются свойствами атомов, а возникают из взаимодействия многих атомов. Ибо если бы атомы, образующие океаны, были «синими по сути своей», то как они могли бы образовывать белую пену на верхушках волн?

Не забывайте, это примерно 400 г. до н. э. До сих пор все очень неплохо.

Почему Демокрит считает, что все вещи сделаны из атомов? Он приводит некоторые аргументы, один из которых можно сформулировать своими словами так: предположим, у нас есть яблоко, и предположим, что это яблоко сделано не из атомов, а из чего-то непрерывного и твердого. Предположим далее, что мы берем нож и разрезаем яблоко на две части. Ясно, что точки на одной стороне попадут на первый кусок, а точки на другой стороне – на второй, но как насчет точек, расположенных в точности на границе? Они что, исчезнут? Или удвоятся? А симметрия нарушится? Ни одна из перечисленных возможностей не кажется особенно элегантной.

Кстати говоря, ожесточенные споры между атомистами и антиатомистами идут и сегодня. Обсуждается вопрос о том, действительно ли сами пространство и время состоят из неделимых атомов на планковских масштабах в 10^–33 см или 10^–43 с. Опять же у физиков очень мало экспериментальных данных, на которые можно опереться в этом вопросе, и они, по существу, находятся в том же положении, в каком был Демокрит 2400 лет назад. Если хотите знать мнение на этот счет невежественного и не слишком информированного обывателя, то я бы поставил на атомистов. И аргументы, которые я бы при этом использовал, не полностью отличаются от тех, что использовал Демокрит: они опять же основываются в основном на неустранимых математических трудностях с континуумом.

Один из немногочисленных отрывков Демокрита, все же дошедших до нас, представляет собой диалог между Разумом и Чувствами. Разум начинает разговор: «Только по договоренности между людьми существует сладость, по договоренности – горечь, по договоренности – цвет, на самом деле существуют только атомы и пустота». По мне, одна эта строка уже ставит Демокрита в один ряд с Платоном, Аристотелем и любым другим древним философом, которого вы рискнете назвать: было бы трудно сформулировать более точно в одном предложении все научное мировоззрение, которое появится через 2000 лет! Но диалог на этом не заканчивается. Чувства отвечают: «Глупый Разум! Неужели ты стремишься ниспровергнуть нас, хотя именно от нас получаешь все данные?»

Я впервые встретил этот диалог в какой-то книге Шрёдингера[9]. Ага, Шрёдингер! – вот видите, мы продвигаемся потихоньку к «квантовым вычислениям», заявленным в названии книги. Не беспокойтесь, мы обязательно до них доберемся.

Но почему Шрёдингера должен был заинтересовать этот диалог? Ну вообще-то его интересовало множество вещей. Он не был склонен к интеллектуальной моногамии (да и ни к какой другой моногамии тоже). Но одна из возможных причин его интереса – тот факт, что он был одним из создателей квантовой механики – самого удивительного, на мой взгляд, открытия XX века (за ней с небольшим отрывом следует теория относительности) – и теории, которая добавила совершенно новый аспект в тысячелетний спор между разумом и чувствами, хотя и не сумела разрешить его.

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

Есть у нее и свои сложности. Не слишком хорошо, скажем, обстоит дело с достоверными данными, поставляемыми чувствами. В чем проблема? Ну, если отнестись к квантовой механике всерьез, окажется, что и вы сами должны, по идее, находиться в суперпозиции разных мест одновременно. В конце концов, вы тоже сделаны из элементарных частиц, правда? Представьте, в частности, что вы рассматриваете некую частицу, которая располагается в суперпозиции двух положений – A и B. В этом случае самое наивное и буквальное прочтение квантовой механики должно было бы предсказать, что наша Вселенная должна расщепиться на две «ветви»: в одной частица находится в A и вы ее видите в A, а в другой – частица находится в B и вы, соответственно, видите ее в B! И что вы думаете: неужели вы действительно расщепляетесь на несколько копий самого себя всякий раз, когда смотрите на что-то? Я лично не чувствую ничего подобного!

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

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

Таким образом, с точки зрения физики все обстояло бы намного проще и понятнее, если бы мы могли вообще избавиться от всей этой мороки с «измерениями»! Тогда мы могли бы сказать, перефразируя Демокрита на сегодняшний лад: не существует ничего, кроме атомов и пустоты, развивающихся в квантовой суперпозиции.

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

Именно так выглядит современный вариант демокритовой дилеммы, о котором физики и философы спорят уже почти сотню лет. Признаюсь откровенно: в этой книге мы с вами ее не разрешим.

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

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

Но что, если вам захочется применить квантовую механику ко всей Вселенной целиком, включая и себя самого? В интерпретациях эпистемологического толка ответ заключается просто в том, что подобные вопросы задавать не принято! Кстати говоря, именно в этом заключался любимый философский ход Бора, его убойный аргумент: «Такой вопрос задавать нельзя!»

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

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

Но хорошо, человеческий мозг – это водянистая, рыхлая, неаккуратная штука, и мы, возможно, не смогли бы поддерживать его в состоянии когерентной суперпозиции на протяжении 500 миллионов лет. Чем можно заменить этот эксперимент? Ну, мы могли бы поместить компьютер в состояние суперпозиции. Чем сложнее компьютер – чем сильнее он напоминает мозг и нас самих, тем дальше мы сможем отодвинуть ту самую «линию» между квантовым и классическим. Сами видите, от этого до идеи квантовых вычислений остался всего один крохотный шажок.

Я хотел бы извлечь из всего этого более общий урок. Какой смысл затевать разговор о философских вопросах? Дело в том, что в дальнейшем мы собираемся довольно активно заниматься этим – в смысле, пустой философской болтовней. На этот счет существует стандартный ответ: философия, мол, занимается интеллектуальной расчисткой, это уборщики, которые приходят вслед за физиками и пытаются навести порядок, разобрав оставленный ими хлам. Согласно этой концепции, философы сидят в своих креслах и ждут, чтобы в физике или вообще в науке появилось что-нибудь интересное – квантовая механика, скажем, или неравенства Белла, или теорема Гёделя; после этого они (приведем метафору с обратным знаком) слетаются на новинку, как стервятники, и объявляют: ах, вот что это означает на самом деле.

Ну, на первый взгляд все это кажется каким-то скучным. Но, когда привыкаешь к подобной работе, мне кажется, обнаруживаешь, что это… все равно скучно!

Лично меня интересует в первую очередь результат – поиск решений нетривиальных, хорошо определенных и еще нерешенных задач. Какова же здесь роль философии? Мне бы хотелось предложить для философии более интересную и возвышенную роль, чем роль интеллектуального дворника: философия может быть разведчиком. Она может быть исследователем-первопроходцем – наносить на карту интеллектуальный ландшафт, который позже будет обживать физика. Далеко не все области естественных наук были заранее обследованы философией, но некоторые были. А в недавней истории, мне кажется, квантовые вычисления могут послужить эталонным примером. Замечательно, конечно, говорить людям: «Заткнитесь и считайте», но вопрос в том, что именно им следует считать. По крайней мере, в квантовых вычислениях (моя специальность) то, что мы любим считать, – емкость квантовых каналов, вероятности ошибок в квантовых алгоритмах – это такие вещи, которые никому в голову не пришло бы считать, если бы не философия.

2. Множества

Здесь мы будем говорить о множествах. Что будут содержать эти множества? Другие множества! Как куча картонных коробок, открыв которые, обнаруживаешь внутри только новые картонные коробки, и так далее, до самого дна.

Вы можете спросить: «Какое отношение все это имеет к книге о квантовых вычислениях?»

Ну, будем надеяться, что кое-какие ответы на этот вопрос мы увидим чуть позже. Пока же достаточно сказать, что математика есть основа всякой человеческой мысли, а теория множеств – счетных, несчетных и др. – основа математики. Так что неважно, о чем у нас книга, в любом случае множества – прекрасная тема для начала.

Мне, вероятно, следует без обиняков сказать вам, что я собираюсь втиснуть весь курс математики в эту одну главу. С одной стороны, это означает, что я не рассчитываю всерьез, что вы все поймете. С другой стороны, в той мере, в какой поймете, – замечательно! Вы получаете целый курс математики в одной главе! Добро пожаловать.

Итак, начнем с пустого множества и посмотрим, как далеко нам удастся пройти.

Пустое множество

На самом деле, прежде чем говорить о множествах, нам необходимо обзавестись языком для разговора о множествах. Язык, который придумали для этого Фреге, Рассел и другие, называется логикой первого порядка. Он включает в себя булевы функции (и, или, не), знак равенства, скобки, переменные, предикаты, кванторы («существует» и «для любого»[10]) – и, пожалуй, все. Говорят, что физики испытывают со всем этим сложности… Эй, потише, я просто пошутил. Если вы прежде не встречались с таким способом мышления, значит, не встречались, ничего страшного в этом нет. Но давайте все же пойдем навстречу физикам и пробежимся по основным правилам логики.

Правила логики первого порядка

Все правила здесь говорят о том, как составлять предложения, чтобы они были корректны – что, говоря по-простому, означает «тавтологически истинны» (верны для всех возможных подстановок переменных)[11], но что мы пока можем представить просто как комбинаторное свойство определенных символьных строк. Я буду печатать логические предложения другим шрифтом, чтобы их было легко отличить от окружающего текста.

• Пропозициональные тавтологии: A или не A, не (A и не A) и т. п. – истинны.

• Modus ponens (правило отделения): если A истинно и из A следует B истинно, то B истинно.

• Правила равенства: высказывания x = x; из x = y следует y = x; если x = y и y = z, то x = z; и из x = y следует f (x) = f (y) – истинны.

• Замена переменных: при изменении имен переменных высказывание остается истинным.

• Исключение квантора: если для всех x A (x) истинно, то A (y) истинно для любого y.

• Добавление квантора: если истинно A (y), где y – переменная без ограничений, то для всех x, A (x) истинно.

• Правило квантификации: если не (для любого x, A (x)) истинно, то существует такой x, что не (A (x)) истинно.

Приведем в качестве примера аксиомы Пеано для неотрицательных целых чисел, записанные в терминах логики первого порядка. В них S(x) – это функция следования, интуитивно S(x) = x + 1, и я предполагаю, что функции определены заранее.

Аксиомы Пеано для неотрицательных целых чисел

• Нуль существует: существует такое z, что для любого x, S(x) не равно z. (Это z принимается за 0.)

• Каждое целое число имеет не более одного предшественника: для любых x, y если S(x) = S(y), то x = y.

Сами неотрицательные целые числа называют моделью этих аксиом: в логике слово «модель» означает всего лишь любой набор объектов и функций этих объектов, удовлетворяющий условиям аксиом. Интересно, однако, что точно так же, как аксиомам теории групп удовлетворяет множество разных групп, так и неотрицательные целые числа – не единственная модель аксиом Пеано. К примеру, вы можете убедиться, что добавление к этой модели дополнительных искусственных целых чисел, недостижимых от 0, – чисел, лежащих «за бесконечностью», так сказать, – даст нам еще одну полноценную модель. При этом, как только вы добавите к модели одно такое целое число, вам придется добавить их бесконечно много, поскольку у каждого целого числа должно быть число, непосредственно за ним следующее.

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

Так вот, именно поэтому я и не считаю, что аксиомы и формальную логику можно использовать для подведения под арифметику более надежного фундамента. Если вы почему-то не согласны с тем, что 1 + 1 = 2, то сколько ни изучай математическую логику, понятнее это не станет! Тем не менее все эти штучки безумно интересны не менее чем по трем причинам.

1. Ситуация изменится, как только мы начнем говорить не о целых числах, а о разных размерах бесконечности. Там формулирование аксиом и разбор следствий из них – это практически все наши инструменты!

2. Как только мы все формализовали, можно запрограммировать компьютер и заставить его думать за нас:

предположение 1: для любого x если A (x) истинно, то B (x) истинно;

предположение 2: существует x такой, что A (x) истинно;

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

3. Помимо того что доказательства для нас будет искать компьютер, мы сможем работать с этими доказательствами как с математическими объектами, что откроет путь к мета-математике.

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

Аксиомы теории множеств

В этих аксиомах фигурирует совокупность объектов, называемых «множествами», и отношения между множествами, которые характеризуются словами «является элементом», «содержится в» или «принадлежит к» и записываются с использованием символа ∈. Любая операция с множествами в конечном итоге определяется в терминах отношения принадлежности.

• Пустое множество: существует пустое множество, то есть множество x, для которого не существует такого y, что y ∈ x.

• Аксиома объемности: если в два множества входят одни и те же члены, то эти множества равны. То есть для любых x и y если (z ∈ x тогда и только тогда, когда z ∈ y для любого z), то x = y.

• Аксиома пары: для любых множеств x и y существует множество z = {x, y}, то есть множество z, такое, что для любого w w ∈ z тогда и только тогда, когда (w = x или w = y).

• Аксиома суммы: для любых множеств x существует множество, равное объединению всех множеств, содержащихся в x.

• Аксиома бесконечности: существует множество x, содержащее пустое множество и содержащее также {y} для любого y ∈ x. (Почему в этом x должно содержаться бесконечное число элементов?)

• Аксиома степени (множество всех подмножеств): для любого множества x существует множество, состоящее из всех подмножеств x.

• Аксиома замены (на самом деле бесконечное число аксиом, по одной для каждой функции A, устанавливающей соответствие одних множеств другим): для любого множества x существует множество z = {A(y) | y ∈ x}, которое образуется в результате применения A ко всем элементам x. (Технически следовало бы определить также, что подразумевается под «функцией, устанавливающей соответствие одних множеств другим»; сделать это можно, но я не буду здесь этим заниматься.)

• Фундирование (аксиома регулярности): в любом непустом множестве x имеется элемент y, такой, что для любого z либо z ∉ x, либо z ∉ y. (Это техническая аксиома, смысл которой в том, чтобы исключить такие множества, как {{{{…}}}}.)

Эти аксиомы, известные как аксиомы Цермело – Френкеля, служат фундаментом практически для всей математики. Поэтому я решил, что вам стоит посмотреть на них хотя бы раз в жизни.

Ну хорошо, один из самых базовых вопросов, которые мы можем задать о множестве, звучит так: насколько оно велико? Каков его размер, его мощность? В смысле, сколько в нем элементов? Вы можете сказать, что это просто: достаточно пересчитать элементы. Но что, если их бесконечно много? Скажите, целых чисел больше, чем нечетных целых чисел? Это приводит нас к Георгу Кантору (1845–1918) и первому из нескольких его громадных вкладов в копилку человеческого знания. Он сказал, что два множества равны по мощности тогда и только тогда, когда их элементы можно поставить в строгое соответствие попарно, то есть один к одному. И точка. А если, как бы вы ни пытались распределить элементы по парам, в одном из множеств все равно остаются лишние, значит, то множество, где остаются лишние элементы, большее из двух.

Какой может быть мощность множества, или, иначе, его кардинальное число? Разумеется, существуют множества конечной мощности, по одному на каждое натуральное число. Затем идет первая бесконечная мощность, мощность множества целых чисел, которую Кантор назвал ℵ0 («алеф-нуль»). Множество рациональных чисел обладает той же мощностью ℵ0; иначе этот факт можно выразить, сказав, что рациональные числа являются счетными – в том смысле, что их можно поставить в попарное соответствие с целыми числами. Иными словами, мы можем составить бесконечный список таким образом, что рано или поздно в нем появится каждое рациональное число.

Как доказывается, что множество рациональных чисел счетно? Вы никогда не видели этого доказательства? Ну хорошо. Для начала запишем 0 и добавим все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равна 2. Затем добавляем к списку все рациональные числа, у которых сумма абсолютных значений числителя и знаменателя равно 3. И так далее. Ясно, что любое рациональное число рано или поздно появится в этом списке. Следовательно, их бесконечное количество счетно. Что и требовалось доказать.

Но самый серьезный вклад Кантора заключался в том, что он показал, что не каждая бесконечность является счетной, – так что, к примеру, бесконечность действительных чисел больше, чем бесконечность целых чисел. В более общем плане: точно так же, как существует бесконечно много чисел, существует и бесконечно много бесконечностей.

С доказательством этого вы тоже не встречались? Ну хорошо, хорошо. Пусть у вас имеется бесконечное множество A. Мы покажем, как получить другое бесконечное множество B, которое будет больше, чем A. Просто возьмем в качестве множества B множество всех подмножеств A, которое гарантированно существует, согласно аксиоме о степенном множестве. Откуда мы знаем, что B больше, чем A? Ну предположим, что мы смогли каждому элементу a ∈ A поставить во взаимно однозначное соответствие элемент f (a) ∈ B, так что лишних элементов B не осталось. Тогда мы можем определить новое подмножество S ⊆ A, состоящее из всех a, которые не входят в подмножество f (a). Такое S также является элементом B. Но, заметьте, S не может соответствовать никакому a ∈ A, поскольку в противном случае a содержалось бы в f (a) тогда и только тогда, когда оно не содержалось бы в f (a). Получили противоречие. Следовательно, B больше A, и мы получили бесконечность большую, чем та, с которой мы начали.

Это определенно одно из четырех или пяти величайших доказательств во всей математике – и опять же полезно посмотреть на него хотя бы раз в жизни.

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

0, 1, 2, 3, …

Затем, говорим мы, определим нечто, что будет больше любого натурального числа:

ω.

ω + 1, ω + 2, …

2ω.

3ω, 4ω, …

ω², ω³, …

ω^ω, _ωω^ω, …

В таком духе мы могли бы продолжать довольно долго! По существу, для любого множества ординальных чисел (конечного или бесконечного) мы уславливаемся, что существует некоторое первое ординальное число, которое стоит после всего, что содержится в этом множестве.

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

А теперь кое-что интересное. Все ординальные числа, которые я перечислил, обладают одним особым свойством: они имеют не более счетного количества (то есть не более ℵ₀) предшественников. Что, если рассмотреть множество всех ординальных чисел с не более чем счетным числом предшественников? Ну, у такого множества тоже имеется следующий элемент, назовем его α. Но сколько предшественников у α, тоже ℵ₀? Разумеется, нет, поскольку в противном случае α не был бы следующим элементом по отношению к нашему множеству, а входил бы в это множество! Множественно предшествующих α элементов обладает следующей возможной мощностью, которая называется ℵ₁.

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

Таким образом, начиная с ℵ₀ (мощность множества целых чисел), мы уже видели два разных способа получить «большие бесконечности, чем бесконечность». Один из этих способов выдает мощность множества множеств целых чисел (или, что то же самое, мощность множества действительных чисел), которую мы обозначаем 2^ℵ₀. Другой способ выдает ℵ₁. Можно ли сказать, что 2ℵ₀ равно ℵ₁? Или скажем иначе: существует ли бесконечность промежуточного размера между бесконечностью целых чисел и бесконечностью действительных чисел?

Этот вопрос стоял первым в списке задач Давида Гильберта, предложенных им в 1900 г. Более полувека он оставался одной из великих нерешенных математических задач, пока не получил «решения» (оказавшегося несколько обескураживающим, как вы увидите).

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

Кроме континуум-гипотезы, существует еще одно утверждение касательно бесконечных множеств, которое никто не мог доказать или опровергнуть, исходя из аксиом Цермело – Френкеля. Это утверждение – печально известная аксиома выбора, в которой говорится, что если у вас имеется (возможно, бесконечное) множество множеств, то можно сформировать новое множество, взяв по одному элементу из каждого множества. Звучит разумно, не правда ли? Вот только если вы принимаете это утверждение, то вам придется признать также, что существует способ разрезать шар на конечное число кусочков, а затем собрать из этих же кусочков новый шар в тысячу раз большего размера. (Это «Парадокс Банаха – Тарского». Следует признать, что отрезать такие «части» ножом довольно проблематично…)

Но почему аксиома выбора приводит к таким драматическим последствиям? В основном потому, что утверждает, что некоторые множества существуют, но не дает никакого правила по формированию этих множеств. Как сказал по этому поводу Бертран Рассел, «чтобы взять по одному носку от каждой из бесконечного числа пар носков, требуется аксиома выбора, а для ботинок такой аксиомы не требуется». (Какая разница?)

Оказывается, аксиома выбора эквивалентна утверждению о том, что любое множество может быть вполне упорядоченным: иными словами, элементы любого множество можно попарно поставить в соответствие порядковым числам 0, 1, 2, …, ω, ω + 1, …, 2ω, 3ω, … вплоть до некоторого порядкового числа. Если подумать, к примеру, о множестве действительных чисел, это представляется далеко не очевидным.

Несложно убедиться, что полная упорядоченность подразумевает аксиому выбора: достаточно просто вполне упорядочить всю бесконечность носков, а затем выбрать из каждой пары носков тот, что идет первым по порядку.

Хотите убедиться в обратном? Почему аксиома выбора подразумевает, что любое множество можно полностью упорядочить? Да?

Хорошо! У нас имеется множество A, которое мы хотим полностью упорядочить. К каждому собственному[12] подмножеству B ⊂ A мы применим аксиому выбора, чтобы выбрать элемент f(B) ∈ A – B (где A – B означает множество всех элементов A, которые не являются также элементами B). Теперь мы можем начать упорядочение A так: пусть s₀ = f({}), далее пусть s₁ = f({s₀}), s2 = f({s₁}) и т. п.

Может ли этот процесс продолжаться до бесконечности? Нет, не может. Потому что если бы он продолжался до бесконечности, то посредством так называемой «трансфинитной индукции» мы могли бы запихнуть в A произвольно большие бесконечные кардинальные числа. А множество A хотя и бесконечно, но имеет не более чем фиксированный бесконечный размер! Так что процесс этот должен где-то остановиться. Но где? На некотором собственном подмножестве B множества A? Нет, это тоже невозможно, поскольку если бы это было так, то мы просто продолжили бы процесс добавлением f(B). Так что единственное место, где он может остановиться, это само A. Следовательно, A может быть полностью упорядочено.

Ранее я упоминал некие математические сложности, изначально присущие континууму, и есть у меня одна головоломка, некоторым образом связанная с ними.

Вы ведь знаете действительную числовую прямую? Пусть нам нужно объединение открытых отрезков, или интервалов (возможно, бесконечного их числа), которое перекрывает все рациональные точки. Вопрос: обязательно ли сумма длин таких интервалов должна быть бесконечной? Казалось бы, это совершенно естественно, это первое, что приходит в голову! В конце концов, рациональные числа у нас всюду!

Сноски

1

www.scottaaronson.com/blog. Использованное в названии блога слово штетл обозначало еврейское местечко в черте оседлости Российской империи. – Прим. пер.

2

www.youtube.com/watch?v=saWCyZupO4U. Здесь и далее примечания автора даются без дополнительных указаний.

7

Стандартным учебным пособием в этой области остаются «Квантовые вычисления и квантовая информация» Майкла Нильсена (Michael Nielsen) и Айзека Чуанга (Isaac Chuang).

8

T. Ito and T. Vidick, A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. In Proceedings of IEEE Symposium on Foundations of Computer Science (2012), pp. 243–252.

9

E. Schrödinger, What is Life? With Mind and Matter and Autobiographical Sketches, Cambridge University Press (reprinted edition), 2012.

10

У автора – «для всех» (for all). – Прим. пер.

11

Упрощая, автор использует далее как синонимы слова valid, которое описывает корректность (выводимость) логической формулы, и true, характеризующее истинность конкретного высказывания. – Прим. пер.

12

Собственным подмножеством называется подмножество, не совпадающее с самим множеством. – Прим. пер.

«Квантовые вычисления со времен Демокрита» » Скотт Ааронсон » Зарубежная образовательная литература

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

* * *

Предисловие

А теперь – настоящее предисловие

Что нового

Благодарности

1. Атомы и пустота

2. Множества

Пустое множество

Правила логики первого порядка

Аксиомы Пеано для неотрицательных целых чисел

Аксиомы теории множеств

0, 1, 2, 3, …

ω.

ω + 1, ω + 2, …

2ω.

3ω, 4ω, …

ω², ω³, …

ω^ω, _ωω^ω, …

Сноски

1

2

3

4

5

6

7

8

9

10

11

12

«Квантовые вычисления со времен Демокрита» » Скотт Ааронсон » Зарубежная образовательная литература

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

* * *

Предисловие

А теперь – настоящее предисловие

Что нового

Благодарности

1. Атомы и пустота

2. Множества

Пустое множество

Правила логики первого порядка

Аксиомы Пеано для неотрицательных целых чисел

Аксиомы теории множеств

0, 1, 2, 3, …

ω.

ω + 1, ω + 2, …

2ω.

3ω, 4ω, …

ω², ω³, …

ωω, ωωω, …

Сноски

1

2

3

4

5

6

7

8

9

10

11

12

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

ω^ω, _ωω^ω, …