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

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

Перечислим важнейшие вехи в истории квантовых компьютеров. В 1973 году Чарльз Беннетт указал на теоретическую возможность обратимой машины Тьюринга, а первое квантовое описание машины Тьюринга дал Пол Бенёв в 1980 году. Огромное значение имела провидческая работа Ричарда Фейнмана (1982), показавшего, что классическая вычислительная машина Тьюринга – очень плохое средство описания квантовых явлений, в то время как квантовая машина Тьюринга будет уверенно решать как квантовые, так и их частный случай – классические – задачи. В 1985 году Давид Дойч впервые дал строгое описание квантовой машины Тьюринга. Его работа положила начало современной теории квантовых компьютеров. Важной вехой в развитии теории стала статья Дойча и Ричарда Джозса (1992), в которой показано, что квантовые вычисления могут быть выполнены за время, которое экспоненциально мало по сравнению со временем, потребным для этих же целей классическим компьютерам. Это общее утверждение вскоре получило блестящую реализацию в работе Питера Шора (1994). Он применил квантовое преобразование Фурье к задаче о факторизации целых чисел. Лучшие классические алгоритмы решают известную со времен Евклида задачу факторизации числа $N$ примерно за $C \exp \left(A(\ln N)^{\frac{1}{3}}\right)$ шагов, так что факторизация достаточно большого числа требует времени, сравнимого со временем существования Солнечной системы. Именно громадность этого времени была положена в основу современных алгоритмов кодирования. Шор показал, что квантовый алгоритм решает задачу факторизации примерно за $D(\ln N)^{2+\varepsilon}$ шагов. Это означало, что квантовому компьютеру (будь он только создан) немедленно найдется применение. Примерно с этого времени начинается продолжающееся до нынешнего дня бурное развитие теории квантовых компьютеров и смежных с ней проблем квантовой криптографии и квантовой телепортации.

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

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

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

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

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

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

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

Отметим некоторые особенности приннтой в сборнике терминологии. В англоязычной литературе общепринят термин gate, который поразному переводится на русский язык. В частности, используются такие обороты, как «логический элемент» или «вентиль». Мы позволили себе употребить слово гейт (в мужском роде), надеясь, что этот термин приживется в русском языке, как уже прижились слова «компьютер», «бит», «байт …». Нам кажется, что поддержку в таком употреблении слова гейт можно найти у Дойча (1989), определяющего гейт как компьютер: «in the classical theory of computation a logic gate is a computing machine whose input and output consist of fixed numbers of bits and which performs a fixed time that is independent of the input … A quantum gate is defined in a similar way»\”

Далее, в последнее время широкое распространение получили термины «entangled», «entanglement» («quantum systems» или «quantum states»), которые в нашем компьютерном фольклоре чаще всего переводятся как «запутанный», «перепутанный» и т. д. Английское «entanglement»- это прямой перевод немецкого слова «Verschränkung», введенного Шредингером в 1935 году (Naturwissenschaften 23, 807-812 (1935)). По-немецки verschanken – это «складывать накрест». В сборнике термины «entangled», «entanglement» переведены как «скрещение», «скрещенный», чтобы избежать невольного придания смысла случайности при переводе соответствующих терминов словом «запутанный». Этого смысла не было у Шредингера.
Наконец, слово «wavelate», которое, несомненно, скоро приобретет популярность и в квантовых вычислениях, точно также звучит и в переводе – «вейвлет».

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