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

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

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

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

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

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

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

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

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

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

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

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

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

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