Квантовые гейты

Идея квантового компьютера, высказанная Фейнманом (Richard Phillips Feynman) в 1982 году, достаточно проста. Она состоит в построении компьютера на основе квантовых, а не классических элементарных ячеек. Законы квантовой механики, определяющие поведение таких квантовых битов (quantum bit) – кубитов, обеспечивают огромные преимущества (скорость и параллелизм вычислений) квантового компьютера по сравнению с классическим компьютером.

Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения [math]1[/math] или [math]0[/math]. В наборе битов (регистре) записывается и перерабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния [math]0[/math] и [math]1[/math]. Система из [math]N[/math] битов имеет [math]2N[/math] базисных состояний. В квантовом компьютере элементарными ячейками для записи информации являются квантовые биты – кубиты. Кубит – это квантовая система, которая, как и бит, имеет два базисных состояния [math]\mid0\bigr\rangle[/math] и [math]\mid 1\bigr\rangle[/math], но в отличие от бита, кубит может находиться в любом суперпозиционном состоянии [math]\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle[/math]. Набор [math]N[/math] кубитов составляет квантовый регистр.

Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из [math]N[/math] кубитов имеет [math]2^N[/math], а не [math]2N[/math] базисных состояний.

Определение:

Любая логическая операция с кубитами называется квантовым гейтом.

По числу задействованных кубитов гейты делятся на одно- и многокубитные. Гейт переводит одно состояние регистра в другое. Действие гейта на регистр можно записать так: [math]G\mid R\bigr\rangle=\mid R^\prime\bigr\rangle[/math].

Гейты – линейные операции: [math]G(\mid p\bigr\rangle+\mid g\bigr\rangle)=G\mid p\bigr\rangle+G\mid g\bigr\rangle[/math].

Демонстрация действия гейта на кубит

Для демонстрации действия гейта на кубиты используют матричную запись гейта или таблицу истинности.

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

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

Также используется графическая форма записи квантовых алгоритмов. Гейты обозначаются некоторыми символами (часто это кружок или квадрат с цифрой или буквой внутри). Кубиты представлены горизонтальными нитями. Действие гейта на кубит показывается путем "нанизывания" гейта на нужный кубит (или несколько кубитов, если это не однобитный гейт. Квантовый алгоритм представляется в виде сети таких гейтов и называется квантовой сетью. Слева в такой сети находятся начальные состояния кубитов, справа — конечные. Действие алгоритма заключается в прохождении кубитов по своим нитям через гейты слева направо.

Описание используемых гейтов

В квантовом случае, как и в теории классических вычислений, любую обратимую унитарную операцию на кубитах можно представить как совокупность базовых операций. Базисом квантовой логики может служить один трехкубитный гейт (например Тоффоли [math](CCNOT)[/math] или Фредкина [math](CSWAP)[/math]) или один однокубитный и один двукубитный гейт (например [math]NOT[/math] и [math]CNOT[/math])

Однокубитный гейт [math]NOT[/math]

Однокубитная логическая операция [math]NOT[/math] переводит [math]\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle[/math] в [math]\mid q^\prime\bigr\rangle=b\mid0\bigr\rangle+a\mid 1\bigr\rangle[/math].

т.e. переставляет весовые коэффициенты кубита местами. В классическом случае ей соответствует обычный [math]NOT[/math], т.к. один из коэффициентов равен нулю.

Двукубитный гейт [math]CNOT[/math]

Двубитный гейт [math]CNOT[/math] (Controlled NOT), действующий на двукубитное состояние в общем виде записывается так: [math]CNOT(R_{00} \left | \ 00\right \rangle +R_{01} \left | \ 01\right \rangle +R_{10} \left | \ 10\right \rangle +R_{11} \left | \ 11\right \rangle) = R_{00} \left | \ 00\right \rangle +R_{01} \left | \ 01\right \rangle[/math] [math]+R_{11}\left | \ 10\right \rangle +R_{10} \left | \ 11\right \rangle[/math]

В классическом случае это просто [math]XOR[/math].

Другие используемые гейты

Кроме упомянутых выше гейтов [math]NOT[/math] и [math]CNOT[/math] в квантовых вычислениях используются также некоторые другие гейты. Их применение не необходимо, но запись алгоритма с их помощью намного проще. На практике часто используются такие гейты: однобитный [math]H[/math] (Hadamard), двубитный [math]S[/math] (swap), трехбитные [math]CCNOT[/math] (гейт Тоффоли), [math] CSWAP[/math] (гейт Фредкина).

Гейт Тоффоли инвертирует кубит [math]B[/math] при условии что значение кубитов [math]A[/math] и [math]C[/math] равны [math]1[/math].

Гейт Фредкина устроен следующим образом: он осуществляет перестановку кубитов [math]B[/math] и [math]C[/math] при условии, что значение кубита [math]A[/math] равно [math]0[/math].

Таблица различных обозначений квантовых гейтов

название гейта	графическое обозначение	матричная запись	таблица истинности
[math]NOT[/math]		[math]\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}[/math]	[math] \begin{array}{|c|c|} 0 & 1 \\ 1 & 0 \\ \end{array}[/math]
[math]CNOT[/math]		[math]\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}[/math]	[math] \begin{array}{|c c|c c|} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}[/math]
[math]H[/math] (Hadamard)		[math]\frac{1}{\sqrt{2}}\begin{pmatrix} 1& 1 \\ 1 & -1 \end{pmatrix}[/math]	[math] \begin{array}{|c|c|} 0 &\frac{1}{\sqrt{2}} \\ 1 & \frac{-1}{\sqrt{2}}\\ \end{array}[/math]
[math]S[/math] (swap)		[math]\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}[/math]	[math] \begin{array}{|c c|c c|} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array}[/math]
[math]CCNOT[/math] (Toffoli)		[math]\begin{pmatrix} 1 & 0 & 0 &0 & 0 & 0 &0 &0 \\ 0 & 1 & 0& 0& 0 &0 & 0 & 0 \\ 0 & 0 & 1 & 0& 0 &0 & 0 & 0 \\0 & 0 & 0& 1& 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0& 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\end{pmatrix}[/math]	[math] \begin{array}{|c c c ||c c c|} A & B & C & A' & B' & C'\\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ \end{array}[/math]
[math]CSWAP[/math] (гейт Фредкина)		[math]\begin{pmatrix} 1 & 0 & 0 &0 & 0 & 0 &0 &0 \\ 0 & 1 & 0& 0& 0 &0 & 0 & 0 \\ 0 & 0 & 1 & 0& 0 &0 & 0 & 0 \\0 & 0 & 0& 1& 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 0& 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix}[/math]	[math] \begin{array}{|c c c ||c c c|} A & B & C & A' & B' & C'\\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{array}[/math]