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

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

Можно сказать, что десятеричная система, которая совсем недавно считалась «искони принятой», появилась в результате физических экспериментов.

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

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

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

Поэт Андрей Белый вспоминал в 1921 году о лекциях по физике, которые он слушал на рубеже веков, будучи еще студентом Московского университета Борисом Бугаевым [2]:
… И строгой физикой мой ум
Переполнял: профессор Умов.
Над мглой космической он пел,
Развив власы главу и выгнув выю,
Что парадоксами Максвелл
Уничтожает энтропию …
Позднее Смолуховский показал, что демон Максвелла, пытаясь измерить скорость молекулы, будет увеличивать энтропию, и не сможет создать вечного двигателя второго рода. Однако, он не отрицал возможность создания таких устройств с помощью «более интеллигентных существ». Сциллард, рафинируя эти рассуждения, высказал предположение, что любое физическое измерение необратимо. К 1949 году рассуждения такого рода на уровне математического фольклора фон Нейман [3] применил к компьютерам. Он предположил, что платой за работу компьютера будет рассеяние энергии порядка $k T \ln 2$ за один шаг вычислений.

Однако все эти блестящие исследования были слишком абстрактными, чтобы изгнать демона Максвелла из физики.

Начиная с 50-х годов XX века производство компьютеров стало отраслью промышленности. Компьютерные фирмы были заинтересованы
в создании экономичных компьютеров. Изучение проблем необратимости стало предельно конкретным. Исследователи, казалось, вернулись к доисторическим временам, создавая методы вычислений с помощью подручных средств и законов физики.

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

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

Практическим выводом из исследований Ландауэра стала необходимость научить компьютеры считать обратимо. Задача создания логически обратимой схемы вычислений была решена в статье Беннета. Вскоре Бенёв показал, что процедура обратимых вычислений может быть представлена в гамильтоновой форме и описал квантовую машину Тьюринга.

Новая веха истории квантовых компьютеров отмечена работами Фейнмана. Еще в начале научной деятельности Фейнман изобрел свой знаменитый функциональный интеграл, который сводил вычисление функции Грина уравнения Шредингера для квантовой частицы к суммированию всех возможных ее классических траекторий. Это означает, что число возможных состояний квантовой системы экспоненциально велико по сравнению с таким же числом соответствующей классической системы. Таким образом, бессмысленно надеяться на помощь классических компьютеров в серьезных исследованиях квантовых систем, но можно попытаться использовать для этих целей квантовые компьютеры. Так прирученные слоны помогают в охоте на своих диких собратьев. Блестящие по стилю статьи Фейнмана, излагающие введение в проблемы квантовых компьютеров, привлекли к этой проблеме многих молодых физиков.

Следует отметить, что еще до Фейнмана необходимость развития квантовых вычислений именно в силу большой информационной емкости квантовых систем отстаивал Манин [4]. Главная задача теории квантовых автоматов виделась ему в необходимости абстрактной формулировки работы автомата, использующей лишь общие принципы квантовой теории, и прежде всего, описание эволюции системы в терминах общего унитарного преобразования в гильбертовом пространстве. Читатель, несомненно, с большим интересом прочтет статью блестящего математика, глубоко разбирающегося в физических проблемах.

Задача, о которой говорил Манин, вскоре была решена Дойчем. В сборнике приведена работа, положившая начало современной математической теории квантовых компьютеров. Формулировка теории квантового компьютера в терминах абстрактного гильбертова пространства привела Дойча к естественному, но все же несколько неожиданному открытию механизма быстрого счета, недоступного классическим вычислениям. При счете на квантовой руке можно пометить сразу все пальцы и вычислить или все значения нужной функции одновременно, или построить вектор состояния, одинаково близкий ко всем состояниям системы. В предыдущем сборнике [5] уже были приведены примеры блестящего использования открытия Дойча: это алгоритм Гровера поиска в случайной базе данных и решение задачи о коммивояжере, данное Черны.

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

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

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