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

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

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

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

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

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

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

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

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

Демокрит

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