Квантовые вычисления

Как уже говорилось во введении, обычные компьютеры не используют всех возможностей, предоставляемых природой. В них выполняются преобразования на конечных множествах состояний (действия с 0 и 1), а в природе есть возможность делать унитарные преобразования, т.е. действовать на бесконечном множествеКонечно, настоящей бесконечности в природе не бывает. В данном случае дело в том, что унитарное преобразование можно задать лишь с некоторой точностью - подробности см. в лекции 7. Эта возможность описывается квантовой механикой. Устройства (реальные или воображаемые), использующие эту возможность, называются квантовыми компьютерами.

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

Обычный компьютер работает с состояниями из конечного числа битов. Каждый бит может находиться в одном из двух состояний 0 или 1. Состояние всей системы задается указанием значений всех битов. Поэтому множество состояний $$\cb^n=\{0,1\}^n$$ конечно и имеет мощность $$2^n$$.

Квантовый компьютер работает с конечными наборами элементарных состояний, называемых q-битами. Каждый q-бит имеет два выделенных состояния (если считать q-биты спинами, то это состояния "спин вверх" и "спин вниз"). Указание выделенных состояний для каждого q-бита системы задает не все возможные состояния системы, а только базисные. Возможны также любые линейные комбинации базисных состояний с комплексными коэффициентами. Базисные состояния мы будем обозначать $$\ket{x_1,\dots,x_n}$$, где $$x_j\in\cb$$, или $$\ket{x}$$, где $$x\in\cb^n$$. Произвольное состояние системы может быть представлено в видеСкобки $$\ket{\dots}$$ в записи $$\ket{\psi}$$ не обозначают никакой операции над объектом $$\psi$$ — они просто указывают на то, что $$\psi$$ является вектором.

Пространство состояний для такой системы — конечномерное (размерности $$2^n$$ ) пространство над полем комплексных чисел.

Небольшое уточнение: если умножить вектор $$\sum_x c_x\ket{x}$$ на фазовый множитель, $$e^{\ii\phi}$$, ( $$\phi$$ — вещественное), то получится физически неотличимое состояние. Таким образом, состояние квантового компьютера — это вектор единичной длины, заданный с точностью до фазового множителя.

Вычисление можно представлять как последовательность преобразований на множестве состояний системы. Опишем, какие преобразования возможны в классическом, а какие — в квантовом случае.

Замечание. Все сказанное относится только к замкнутым системам. Реальный квантовый компьютер — это часть большой системы (Вселенной), взаимодействующая с остальным миром. Квантовые состояния и преобразования открытых систем будут рассмотрены в разделах 9-10.

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

Определения и обозначения

Пространство состояний системы из $$n$$ q-битов $$\CC^{2^n}$$ можно записать в виде тензорного произведения $$\CC^2\otimes\ldots\otimes\CC^2=\left(\CC^2\right)^{\otimes n}$$. Сомножители соответствуют пространству состояний одного q-бита.

Тензорное произведение двух пространств $$L$$ и $$M$$, в которых фиксированы базисы $$\{e_1,\dots,e_l\}$$ и $$\{f_1,\dots, f_m\}$$, можно определить как пространство с базисом из элементов $$e_j\otimes f_k$$. (В данном случае $$e_j\otimes f_k$$ — это то же самое, что $$(e_j,f_k)$$, т.е. просто пара векторов.) Размерность тензорного произведения равна $$lm$$ (произведению размерностей сомножителей).

Такое определение неинвариантно, т.е. зависит от выбора базисов в перемножаемых пространствах. Можно дать инвариантное определение. Для этого рассмотрим вначале пространство (бесконечномерное) с базисом $$e\otimes f$$, где $$e\in L$$, $$f\in M$$ — произвольные векторы из перемножаемых пространств. Тензорное произведение будет факторпространством этого пространства по подпространству, порожденному векторами вида$$\begin{align*} (e_1+e_2)\otimes f - e_1\otimes f - e_2\otimes f,\\ e\otimes(f_1+f_2) - e\otimes f_1 - e\otimes f_2,\\ (\lambda e)\otimes f - e\otimes(\lambda f),\\ \lambda(e\otimes f)-(\lambda e)\otimes f. \end{align*}$$ Другими словами, указанные векторы считаются равными 0.

Можно доказать, что данные определения эквивалентны.

В нашем случае имеется естественный выделенный базис (соответствующий выделенным состояниям): для $$\CC^2$$ — $$\{\ket0,\ket1\}$$, а для $$\left(\CC^2\right)^{\otimes n}$$ — $$\{\ket{x_1,\dots,x_n}\}, \ x_j\in\cb$$. Пространство $$\CC^2$$ с выделенным базисом обозначается через $$\BB$$. Выделенный базис считается ортонормированным, это задает скалярное произведение на пространстве состояний. Коэффициенты $$c_{x_1,\dots,x_n}$$ разложения вектора $$\ket{\psi}$$ по этому базису называются амплитудами. Их физический смысл состоит в том, что квадрат модуля амплитуды $$|c_{x_1,\dots,x_n}|^2$$ интерпретируется как вероятность обнаружить систему в данном базисном состоянии. Как и должно быть, суммарная вероятность всех состояний равна $$1$$, поскольку длина вектора предполагается единичной. (Вероятности будут подробно обсуждаться позже; до некоторых пор мы будем заниматься линейной алгеброй — изучать унитарные операторы на пространстве $$\BB^{\otimes n}$$ ).

Мы будем использовать (и уже использовали) принятые в физике обозначения, относящиеся к векторам и скалярному произведению в гильбертовом пространстве (их ввел Дирак). Векторы обозначаются $$\ket{\xi}$$, скалярное произведение — $$\langle\xi|\eta\rangle$$. Если $$\ket{\xi}=\sum_x a_x\ket{x}$$ и $$\ket{\eta}\double=\sum_x b_x\ket{x}$$, то $$\langle\xi|\eta\rangle=\sum_x a^*_xb^{\phantom{*}}_x$$. (Здесь и далее $$a^*$$ обозначает комплексное сопряжение.) В записи векторов скобки нужны лишь "для красоты" — они указывают на тип объекта и придают симметрию обозначениям (см. ниже). Вместо $$\ket{\xi}$$ можно было бы написать просто $$\xi$$, хотя это и не принято. Поэтому $$\ket{\xi_1+\xi_2}=\ket{\xi_1}+\ket{\xi_2}$$ — и то, и другое обозначает вектор $$\xi_1+\xi_2$$.

Скалярное произведение антилинейно по первому аргументуОбратите внимание, что математики обычно считают, что скалярное произведение в унитарном пространстве антилинейно по второму аргументу. и линейно по второму, т.е.$$\begin{align*} \langle \xi_1+\xi_2|\eta\rangle= \langle \xi_1|\eta\rangle+\langle \xi_2|\eta\rangle, \langle \xi|\eta_1+\eta_2\rangle= \langle \xi|\eta_1\rangle+\langle \xi|\eta_2\rangle,\\ \langle c\xi|\eta\rangle=c^*\langle \xi|\eta\rangle, \langle \xi|c\eta\rangle=c\langle \xi|\eta\rangle. \end{align*}$$

Если в обозначении скалярного произведения взять левую половину, то получим бра-вектор $$\bra{\xi}$$, т.е. линейный функционал на кет-векторах (векторах нашего пространства). Бра- и кет-векторы находятся во взаимно однозначном соответствии. (Тем не менее, нужно их как-то различать — именно для этого и были введены угловые скобки.) Из-за антилинейности скалярного произведения по первому аргументу имеем равенство $$\bra{c\xi}\double=c^*\bra\xi$$. Бра-вектор можно записать в виде строки, а кет-вектор — в виде столбца (чтобы его можно было умножить слева на матрицу):$$\bra{\xi}=c_0^*\bra{0}+c_1^*\bra{1}=(c_0^*,c_1^*), \qquad \ket{\xi}=c_0\ket{0}+c_1\ket{1}= \leftp \begin{array}{c} c_0\\ c_1 \end{array} \rightp\, .$$

Запись $$\langle \xi|A|\eta\rangle$$ ( $$A$$ — линейный оператор) можно толковать двояко: либо как скалярное произведение вектора $$\bra\xi$$ на вектор $$A\ket\eta$$, либо как — $$\bra\xi A$$ на $$\ket\eta$$. Так появляется сопряженный оператор $$A^\dagger$$: по определению, $$\bra{A^\dagger\xi}$$ (бра-вектор, соответствующий $$A^\dagger\ket{\xi}$$ ) равен линейному функционалу $$\bra\xi A$$. Из определения сразу следует, что$$\langle A^\dagger\xi |\eta\rangle = \langle\xi |A|\eta\rangle.$$

Унитарный оператор — это линейный оператор, сохраняющий скалярное произведение. Условие$$\langle \eta|\xi\rangle =\langle U\eta|U|\xi\rangle = \langle \eta|U^\dagger U|\xi\rangle$$ эквивалентно тому, что $$U^\dagger U=I$$ (где $$I$$ — тождественный оператор).

Наше определение скалярного произведения в $$\BB^{\otimes n}$$ согласовано с тензорным произведением:$$\Bigl(\bra{\xi_1}\otimes\bra{\xi_2}\Bigr) \Bigl(\ket{\eta_1}\otimes\ket{\eta_2}\Bigr)= \langle\xi_1|\eta_1\rangle\,\langle\xi_2|\eta_2\rangle\,.$$ В дальнейшем будет использоваться тензорное произведение операторов. Оно действует в тензорном произведении пространств, на которых действуют сомножители, по правилу$$(A\otimes B)\ket\xi\otimes\ket\eta=A\ket\xi\otimes B\ket\eta.$$ Если операторы заданы в матричном виде в некотором базисе, т.е.$$A\double=\sum_{j,k}^{} a_{jk}\ket{j}\bra{k},\quad B=\sum_{j,k}^{}b_{jk}\ket{j}\bra{k}$$ (легко понять, что $$\ket{j}\bra{k}$$ — линейный оператор: $$\ket{j}\bra{k}\;\ket\xi=\langle k|\xi\rangle\ket{j}$$ ), то матричные элементы оператора $$C=A\otimes B$$ имеют вид $$c_{(jk)(lm)}=a_{jl}b_{km}$$.

Вычисление состоит из преобразований, считаемых элементарными (выполняемых за единицу времени).

Тензорное произведение некоторого оператора $$U$$, действующего на множестве q-битов $$A$$, и тождественного оператора, действующего на остальных q-битах, будем обозначать $$U[A]$$. (В частности, $$U[1,\dots,r]\double=U\otimes I$$ обозначает действие на первых $$r$$ q-битах.)