Предисловие

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

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

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

Основу книги составили материалы курса "Классическое и квантовое вычисление", прочитанного А. Шенем (классические вычисления) и А. Китаевым (квантовые вычисления) в Высшем колледже математики Независимого Московского университета в весеннем семестре 1998 г. При подготовке книги также использовались материалы курса Physics 229 - Advanced Mathematical Methods of Physics (Quantum computation), который вели Дж. Прескилл (John Preskill) и А. Китаев (при участии А. Ландала (Andrew Landahl)) в Калифорнийском технологическом институте в 1998-1999 уч. г.

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

Обозначения

$$\vee$$	дизъюнкция (логическое ИЛИ)
$$\wedge$$	конъюнкция (логическое И)
$$\neg$$	отрицание
$$\oplus$$	сложение по модулю 2 (а также прямая сумма линейных пространств)
$$\Longrightarrow$$	импликация (логическое следование)
$$\Longleftrightarrow$$	логическая эквивалентность
$$\calA^*$$	множество конечных слов в алфавите $$\calA$$
$$\emptycell$$	пустой символ (пробел) в алфавите машины Тьюринга
$$\delta(\cdot,\cdot,\cdot)$$	функция переходов машины Тьюринга
$$L_1\propto L_2$$	сводимость предикатов по Карпу ( $$L_1$$ сводится к $$L_2$$ ) (лекция 2)
$$f(n)=O(g(n))$$	существует такое число $$C$$, что $$f(n)\leq Cg(n)$$
$$f(n)=\Omega(g(n))$$	существует такое число $$C$$, что $$f(n)\geq Cg(n)$$
$$f(n)=\poly(n)$$	то же самое, что $$f(n)=O(n^{O(1)})$$
$$\FF_q$$	конечное поле из $$q$$ элементов
$$\ZZ/n\ZZ$$	кольцо вычетов по модулю $$n$$
$$\ZZ_n$$	аддитивная группа кольца $$\ZZ/n\ZZ$$
$$(\ZZ/n\ZZ)^*$$	мультипликативная группа обратимых элементов $$\ZZ/n\ZZ$$
$$E^*$$	( $$=\mathop{\rm Hom}(E,U(1))$$ ) — группа характеров абелевой группы $$E$$
$$\Sp_2(n)$$	симплектическая группа над полем $$\FF_2$$ размерности $$n$$ (лекция 14)
$$\ESp_2(n)$$	расширенная симплектическая группа над полем $$\FF_2$$ размерности $$n$$ (лекция 14)
$$\CC$$	множество комплексных чисел
$$z^*$$	комплексное сопряжение
$$U(\calM)$$	группа унитарных операторов на пространстве $$\calM$$
$$\SU(\calM)$$	специальная унитарная группа на пространстве $$\calM$$
$$\SO(\calM)$$	специальная ортогональная группа на евклидовом пространстве $$\calM$$
$$\CC(a,b,\dots)$$	пространство, порожденное векторами $$a,b,\dots$$
$$\calM^*$$	пространство линейных функционалов на пространстве $$\calM$$
$$\calM^{\otimes n}$$	$$n$$ -я тензорная степень
$$\LL(\calM)$$	пространство линейных операторов на $$\calM$$
$$\LL(\calN,\calM)$$	пространство линейных отображений из $$\calN$$ в $$\calM$$
$$\cb$$	классический бит (множество $$\{0,1\})$$
$$\BB$$	квантовый бит (q-бит, пространство $$\CC^2$$ )
$$\bra{\xi}$$	бра-вектор (лекция 5)
$$\ket{\xi}$$	кет-вектор (лекция 5)
$$\langle\xi|\eta\rangle$$	скалярное произведение
$$A^\dagger$$	эрмитово сопряженный оператор
$$\qxor$$	обратимое копирование бита (Controlled NOT) (лекция 6)
$$f_\oplus$$	обратимая функция, соответствующая булевой функции $$f$$ (лекция 6)
$$I_\calL$$	тождественный оператор на пространстве $$\calL$$
$$\hat G$$	унитарный оператор, соответствующий перестановке $$G$$ (лекция 6)
$$\Lambda(U)$$	оператор $$U$$ с квантовым управлением (лекция 7)
$$\Pi_\calM$$	проектор (оператор проектирования) на подпространство $$\calM$$
$$\sigma(\alpha_1,\beta_1,\dots,\alpha_n,\beta_n)$$	базисные операторы на пространстве $$\BB^{\otimes n}$$ (лекция 14)
$$A\cdot B$$	преобразование матриц плотности $$\rho\mapsto A\rho B$$ (лекция 14)
$$U[A]$$	оператор, действующий на квантовый регистр (множество q-битов) $$A$$ (лекция 5)
$$Tr_\calF A$$	частичный след от оператора $$A$$ по пространству $$\calF$$ (лекция 9)
$$\|\cdot\|$$	норма вектора (лекция 7) или операторная норма оператора (лекция 6)
$$\|\cdot\|_\trr$$	следовая норма (лекция 14)
$$\|\cdot\|_\trn$$	норма для преобразований матриц плотности (лекция 14)
$$|\cdot|$$	мощность множества или модуль числа
$$\delta_{jk}$$	символ Кронекера
$$\chi_S(\cdot)$$	характеристическая функция множества $$S$$
$$(x,y)$$	наибольший общий делитель $$x$$ и $$y$$
$$a\equiv b\pmod{q}$$	сравнение по модулю $$q$$
$$a\bmod{q}$$	остаток по модулю $$q$$
	представление рационального числа $$a/b$$ в виде несократимой дроби
$$\Prob[A]$$	вероятность события $$A$$
$$\PP(\cdot|\cdot)$$	условная вероятность (в различных контекстах)
$$\PP(\rho,\calM)$$	квантовая вероятность (лекция 9)

Обозначения матриц:

Обозначения сложностных классов:

Введение

Все компьютеры, начиная от так и не построенной "аналитической машины" Чарльза БэббиджаБэббидж начал работу над проектом "аналитической машины" в 1833 году. Преполагалось, что, в отличие от уже существовавших в то время вычислительных устройств, это будет универсальный компьютер. Бэббидж посвятил разработке компьютера всю жизнь, но ему так и не удалось осуществить свою мечту. (Более простая, но неуниверсальная "разностная машина" была построена частично, но проект был вполне реалистичен — в 1991 году машина была полностью воспроизведена по чертежам Бэббиджа.) и кончая Cray'ем, основаны на одних и тех же принципах. С логической точки зрения компьютер состоит из битов (переменных, принимающих значения $$0$$ или $$1$$ ), а программа — это последовательность операций, каждая из которых использует небольшое число битов. Конечно, новые компьютеры работают быстрее старых, но прогресс в этом направлении имеет предел. Трудно предположить, что размер транзистора или аналогичного элемента будет меньше $$10^{-8}$$ см (диаметр атома водорода), а рабочая частота — больше $$10^{15}$$ ~Гц (частота атомных переходов). Так что даже суперкомпьютеры будущего не смогут решать вычислительные задачи, имеющие экспоненциальную сложность. Рассмотрим, например, задачу о разложении целого числа $$x$$ на простые множители. Очевидный способ — это попробовать разделить $$x$$ на числа от $$2$$ до $$\sqrt{x}$$. Если число $$x$$ имеет $$n$$ знаков в двоичной записи, то придется перебрать $$\sim\sqrt{x}\sim 2^{n/2}$$ вариантов. Существует хитроумный алгоритм, решающий ту же задачу примерно за $$\exp(сn^{1/3})$$ шагов ( $$c={\rm const}$$ ). Даже в этом случае, чтобы разложить на множители число из миллиона знаков, не хватит времени жизни Вселенной. (Возможно, есть и более эффективные алгоритмы, но от экспоненты, по-видимому, избавиться не удастся.)

Существует, однако, другой способ ускорить процесс вычисления для некоторых специальных классов задач. Дело в том, что обычные компьютеры не используют всех возможностей, предоставляемых природой. Это утверждение может показаться слишком очевидным: в природе есть множество процессов, совершенно непохожих на операции с нулями и единицами. Можно попытаться использовать эти процессы для создания аналоговой вычислительной машины. Например, интерференция света может использоваться для вычисления преобразования Фурье. Однако в большинстве случаев выигрыш в скорости не является принципиальным, т.е. слабо зависит от размера устройства. Причина заключается в том, что уравнения классической физики (например, уравнения Максвелла) эффективно решаются на обычном цифровом компьютере. Что значит эффективно? Вычисление интерференционной картины может занять в миллионы раз больше времени, чем реальный эксперимент, потому что скорость света велика, а длина волны мала. Однако с увеличением размера моделируемой физической системы количество необходимых вычислительных операций растет не слишком быстро — степенным, или, как принято говорить в теории сложности, полиномиальным образом. (Как правило, число операций пропорционально величине $$Vt$$, где $$V$$ — объем, а $$t$$ — время.) Таким образом, классическая физика слишком "проста" с вычислительной точки зрения.

Квантовая механика устроена в этом смысле гораздо интереснее. Рассмотрим, например, систему из $$n$$ спинов. Каждый спин обладает двумя базисными состояниями ( $$0=\text{"спин вверх"}$$ и $$1=\text{"спин вниз"}$$ ), а вся система имеет $$2^n$$ базисных состояний $$|x_1,\dots,x_n\rangle$$ (каждая из переменных $$x_1,\dots,x_n$$ принимает значение $$0$$ или $$1$$ ). Согласно общим принципам квантовой механики, возможными состояниями системы являются также суперпозиции вида $$\sum_{x_1,\dots,x_n}c_{x_1,\dots,x_n}|x_1,\dots,x_n\rangle$$, где $$c_{x_1,\dots,x_n}$$ — комплексные числа, называемые амплитудами. Знак суммы здесь нужно понимать чисто формально. Суперпозиция является новым математическим объектом — вектором в $$2^n$$ -мерном комплексном пространстве. Квадрат модуля амплитуды, $$|с_{x_1,\dots,x_n}|^2$$, равен вероятности обнаружить систему в базисном состоянии $$|x_1,\dots,x_n\rangle$$ при измерении значений переменных $$x_j$$. (Отметим, что такое измерение разрушает суперпозицию.) Следовательно, должно выполняться условие $$\sum_{x_1,\dots,x_n}|с_{x_1,\dots,x_n}|^2=1$$. Итак, общее состояние системы (т.е. суперпозиция) — это вектор единичной длины в $$2^n$$ -мерном комплексном пространстве. Изменение состояния за определенный промежуток времени описывается унитарной матрицей размера $$2^n\times 2^n$$. Если промежуток времени очень мал ( $$\ll \hbar/J$$, где $$J$$ — энергия взаимодействия), то эта матрица устроена достаточно просто; каждый из ее элементов можно легко вычислить, зная взаимодействие между спинами. Если же мы хотим узнать изменение состояния системы за большой промежуток времени, то придется перемножать такие матрицы. Для этого требуется экспоненциально большое число операций. В настоящее время неизвестно никакого способа упростить данное вычисление, скорее всего, моделирование квантовой механики является экспоненциально сложной вычислительной задачей. Однако то же самое утверждение можно сформулировать иначе: квантовая система эффективно "решает" сложную вычислительную задачу — моделирует саму себя.

Можно ли использовать квантовые системы для решения других вычислительных задач? Какова должна быть математическая модель квантового компьютера, в той же степени не зависящая от физической реализации, что и модели классических вычисленийНаиболее известной математической моделью обычного компьютера является машина Тьюринга. Большинство моделей полиномиально эквивалентны друг другу, т.е. задача, разрешимая за $$L$$ шагов в одной модели, разрешима за $$cL^k$$ шагов в другой модели, где $$c$$ и $$k$$ — константы. ? Эти вопросы, по-видимому, впервые были поставлены в книге Ю. И. Манина "Вычислимое и невычислимое" (1980 г.). Они обсуждались также в работах Р. Фейнмана и других авторов. В 1985 году Д. Дойч [27] предложил конкретную математическую модель — квантовую машину Тьюринга, а в 1989 году — эквивалентную, но более удобную модель — квантовые схемы [28, 47].

Что такое квантовая схема? Пусть в нашем распоряжении имеется $$N$$ спинов, каждый из которых находится в отдельном ящичке и идеально изолирован от окружающего мира. В каждый момент времени мы можем выбрать, по нашему усмотрению, любые два спина и подействовать на них любой унитарной матрицей $$4\times 4$$. Последовательность таких операций называется квантовой схемой. Каждая операция определяется парой номеров спинов и шестнадцатью комплексными числами, поэтому квантовую схему можно записать на бумаге. Это своего рода программа для квантового компьютера.

Чтобы использовать квантовую схему для вычисления функцииЛюбая вычислительная задача может быть представлена в таком виде. Например, если мы хотим решать задачу о разложении целого числа $$x$$ на простые множители, то $$(x_1,\dots,x_n)=x$$ (в двоичной записи), а $$F(x)$$ — список простых множителей (в некоторой двоичной кодировке). $$F\colon\cb^n\to\cb^m$$, нужно уметь вводить входные данные, проделывать вычисления и считывать результат. Ввести в квантовый компьютер последовательность $$(x_1,\dots,x_n)$$ нулей и единиц — значит приготовить начальное состояние $$|x_1,\dots,x_n,0,\dots,0\rangle$$. (Объем входных данных $$n$$ обычно меньше общего количества "ячеек памяти", т.е. спинов, $$N$$. Оставшиеся ячейки заполняются нулями.) К начальному состоянию применяется квантовая схема, зависящая от решаемой задачи, но не от конкретных входных данных. В итоге возникает квантовое состояние$$|\psi(x_1,\dots,x_n)\rangle\ =\ \sum_{y_1,\dots,y_N} c_{y_1,\dots,y_N}(x_1,\dots,x_n)\, |y_1,\dots,y_N\rangle,$$ зависящее от $$(x_1,\dots,x_n)$$. Теперь нужно считать результат. Предполагаем, что ответ должен содержаться в первых $$m$$ битах строки $$(y_1,\dots,y_N)$$, т.е. мы ищем такие $$(y_1,\dots,y_m)$$, что $$(y_1,\dots,y_m)\double=F(x_1,\dots,x_n)$$. Для получения ответа производится измерение значений всех спинов. Результатом измерения может быть любая последовательность нулей и единиц $$(y_1,\dots,y_N)$$, вероятность получить ее равна $$|c_{y_1,\dots,y_N}(x_1,\dots,x_n)|^2$$. Таким образом, квантовый компьютер может, с некоторой вероятностью, дать любой ответ. Квантовая схема является "правильной" для данной функции $$F$$, если правильный ответ $$(y_1,\dots,y_m)=F(x_1,\dots,x_n)$$ получается с вероятностью, достаточно близкой к единице. Повторив все вычисление несколько раз и выбрав тот ответ, который встречается чаще, можно снизить вероятность ошибки до сколь угодно малой величины.

Мы только что сформулировали (опуская некоторые подробности) математическую модель квантового вычисления. Теперь естественно задать два вопроса.

По поводу первого вопроса сейчас известно следующее. Во-первых, на квантовом компьютере можно моделировать любую квантовую систему за полиномиальное число шагов. Это позволит (при наличии квантового компьютера) предсказывать свойства молекул и кристаллов, проектировать микроскопические электронные устройства размером в несколько десятков ангстрем. (Сейчас такие устройства находятся на пределе технологических возможностей, но в будущем они, вероятно, будут применяться в обычных компьютерах.) Второй пример — разложение на множители и аналогичные теоретико-числовые задачи, связанные с абелевыми группами. В 1994 году П. Шор (P. Shor) придумал квантовый алгоритмЕсли не вдаваться в тонкости, квантовый алгоритм — это то же самое, что квантовая схема. Отличие состоит в том, что схема определена для задачи фиксированного размера ( $$n={\rm const}$$ ), а алгоритм определен для всех $$n$$ сразу. , позволяющий разложить на простые множители число из $$n$$ знаков за $$n^3(\log n)^k$$ шагов ( $$k={\rm const}$$ ). Этот красивый результат может иметь скорее вредное, чем полезное применение: разлагая числа на множители, можно подбирать ключи к шифрам, подделывать электронные подписи и т.д. (Впрочем, трудности на пути создания квантового компьютера столь велики, что в течение ближайших 10 лет пользователи шифров могут спать спокойно.) Третий пример — это поиск нужной записи в неупорядоченной базе данных. Здесь выигрыш не столь значителен: для нахождения одной записи из $$N$$ требуется порядка $$\sqrt{N}$$ операций на квантовом компьютере вместо $$N$$ операций на классическом. На этом список известных примеров заканчивается — не потому что квантовые компьютеры бесполезны для других задач, а потому что теория квантовых вычислений пока не разработана. Будем надеяться, что скоро появятся новые математические идеи, которые позволят придумать новые примеры.

Физическая реализация квантового компьютера — чрезвычайно интересная, но сложная задача. Еще несколько лет назад высказывались сомнения в ее принципиальной разрешимости. Дело в том, что любое унитарное преобразование можно реализовать лишь с некоторой точностью. Кроме того, систему спинов или аналогичную квантовую систему нельзя полностью защитить от возмущений со стороны окружающей среды. Все это должно приводить к погрешностям, которые будут накапливаться в процессе вычисления. Через $$L\sim\delta^{-1}$$ шагов (где $$\delta$$ — точность каждого унитарного преобразования) вероятность ошибки станет порядка единицы. К счастью, эту трудность можно преодолеть, используя квантовые коды, исправляющие ошибки. В 1996 году П. Шор предложил схему коррекции ошибок в процессе квантового вычисления (fault-tolerant quantum computation), которая была вскоре усовершенствована. Окончательный результат состоит в следующем. Существует некоторое пороговое значение точности $$\delta_0$$, такое что при $$\delta<\delta_0$$ возможно сколь угодно длинное квантовое вычисление. Однако при $$\delta>\delta_0$$ ошибки накапливаются быстрее, чем их удается исправлять. По разным оценкам, $$\delta_0$$ лежит в интервале от $$10^{-2}$$ до $$10^{-6}$$ (точное значение зависит от характера возмущений и используемой схемы коррекции ошибок).

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