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

Грубо говоря, мотивация изучения квантового вычисления исходит из нескольких источников: физики, технологии, гносеологии и математики.
(i) С точки зрения физики квантовый способ описания более фундаментален, чем классический. В семидесятых и восьмидесятых годах было замечено, что из-за принципа суперпозиции моделирование квантовых процессов на классических компьютерах сложно с вычислительной точки зрения ([Po], [Fe1]). Грубо говоря, квантуя класси-
*Доклад, прочитанный на семинаре Н. Бурбаки, июнь 1999. Перевод А. П. Бельтюкова.
ческую систему с $N$ состояниями, мы получим квантовую систему, пространство состояний которой – ( $N-1)$-мерное комплексное проективное пространство, объем которого растет экспоненциально с ростом $N$. Можно утверждать, что основное занятие квантовой химии борьба с возникающими в связи с этим трудностями. Обращая этот аргумент, можно ожидать, что квантовые компьютеры, если они вообще могут быть построены, будут значительно более мощными, чем классические ([Fe1], [Ma2]).

Прогресс в технике миниатюризации современных компьютеров уже привел нас к такому уровню, при котором квантовый шум становится существенным препятствием для получения безошибочно работающих микросхем. Единственно логичный подход – начать использовать существенно квантовомеханическое поведение малых объектов при конструировании компьютеров вместо того, чтобы нейтрализовать его.
(ii) В качестве другой мотивации можно привлечь крайне спекулятивные, но интригующие предположения о том, что наш головной мозг на самом деле – квантовый компьютер. Например, недавний прогресс в написании эффективного программного обеспечения для игры в шахматы (компьютер Deep Blue) показывает, что для моделирования уровня мирового чемпионата с использованием только классических алгоритмов нужно уметь проанализировать около $10^{6}$ позиций в секунду, и использовать около $10^{10}$ байтов памяти. Поскольку характерное время срабатывания нейрона – около $10^{-3}$ сек, очень трудно объяснить с точки зрения классической физики как головной мозг мог бы выполнить эту работу и играть в шахматы столь же успешно, как Карпов. Менее впечатляющая, но не менее ресурсоемкая задача – генерация и восприятие речи, которая без труда выполняется головным мозгом любым из миллиардов людей, но пока представляет непосильную задачу для современных компьютеров, использующих классические алгоритмы.

Вычислительная сложность задач распознавания имеет несколько источников: основные переменные могут быть полями; ограниченное число малых блоков может комбинироваться в экспоненциально растущие деревья альтернатив; должны быть организованы хранение и поиск несжимаемой информации в базах данных.
Для преодоления этих трудностей были разработаны две парадигмы: логикоподобные языки и комбинаторные алгоритмы, с одной стороны, и статистическое сопоставление наблюдаемых данных с ненаблюдаемой моделью, с другой стороны (более подробное обсуждение второй парадигмы см. в статье Д. Мамфорда (D. Mamford) [Mu]).

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

Идея «квантового параллелизма» (см. разд. 2 ниже) – привлекательная теоретическая альтернатива. Тем не менее, не совсем ясно, может ли она быть согласована с имеющимися результатами экспериментов, которые описывают центральную нервную систему как чисто классическое устройство.

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

По-видимому, трудности увеличиваются из-за того, что квантовые измерения дают недетерминированные результаты. На самом деле, можно попытаться использовать это как преимущество, потому что существуют ситуации, когда мы можем отличить квантовую случайность от классической, анализируя распределения вероятностей и используя неравенства типа белловских. При внимательном рассмотрении в подходе Белла обнаруживается первый пример игровой ситуации, где квантовые игроки могут вести себя очевидно более эффективно, чем классические (см. описание этого подхода в [Ts], с. 52-54).
Было бы крайне интересно разработать экспериментальную установку с целью показать, что некогорые фрагменты центральной нервной системы, отвечающие за обработку информации, могут фактически быть в квантовой суперпозиции классических состояний.
(iii) Наконец, обратимся к математике. Можно сказать, что в настоящее время не нужно даже дополнительной мотивации, так как имеется преобладающая тенденция, предписывающая квантовать «все, что движется». В голову приходят квантовые группы, квантовые когомологии, квантовые инварианты узлов и т. д. Кажется, что это действительно было первоначальной мотивацией до 1994 года, когда П. Шор ([Sh]) изобрел первый квантовый алгоритм, показав, что разложение на простые множители может быть сделано на квантовых компьютерах за полиномиальное время, т.е. значительно быстрее, чем с помощью любого известного классического алгоритма. (Работа П. Шора была инспирирована более ранней работой [Si] Д. Саймона). Статья Шора дала новый толчок предмету. Другой прекрасный результат, полученный Л.Гровером ([Gro]), состоит в том, что квантовый поиск среди $N$ предметов может быть выполнен за $c \sqrt{N}$ шагов. А. Китаев [Ki1] изобрел новые квантовые алгоритмы для вычисления стабилизаторов действий абелевых групп; его работе предшествовала работа Д. Боне и Р. Липтона $[\mathrm{BoL}]$, которые изучали более общую проблему с помощью модификации метода Шора (ср. также [Gri]). Инструменты, разработанные Шором, Гровером и Китаевым, сами по себе не менее важны, чем их результаты.

Работа Шора – центральный предмет этой лекции. Она объясняется в разделе 4. Это объяснение следует за обсуждением общих принципов квантового вычисления и массивного квантового параллелизма в разделе 2 и четырех квантовых подпрограмм, включая алгоритм поиска Гровера в разделе 3. Вторая из этих подпрограмм, включающая квантовые вычисления классических вычислимых функций, показывает, как справиться с основной проблемой достижения квантовой обратимости при наличии классической необратимости. С большей частью этого можно ознакомиться в [Ben1] и [Ben2]. Открывающий раздел 1 содержит краткий обзор классической теории вычислимости. Я сделал некоторую попытку выразить определенные понятия компьютерных наук, включая $\mathrm{P} / \mathrm{NP}$, на языке обычной математики. В последнем разделе 5 обсуждается колмогоровская сложность в контексте классических и квантовых вычислений.

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