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

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

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

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

Отличие кубитов от классических битов

Классический компьютер состоит из элементарных ячеек – битов, двум состояниям которых приписываются значения $1$ или $0$. В наборе битов (регистре) записывается и обрабатывается информация в виде двоичных чисел. Один бит имеет два базисных состояния $0$ и $1$. Система из $N$ битов имеет $2N$ базисных состояний. Перебирая эти базисные состояния, можно закодировать двоичное число длиной $N$. Например, в системе из трех битов можно записать одну из восьми последовательностей нулей и единиц $000, 001, 011, 010, 100, 101, 110, 111$.

В квантовом компьютере кубит – это квантовая система, которая, как и бит, имеет два базисных состояния $\mid0\bigr\rangle$ и $\mid 1\bigr\rangle$, но в отличие от бита, кубит может находиться в любом суперпозиционном состоянии $\mid q\bigr\rangle=a\mid0\bigr\rangle+b\mid 1\bigr\rangle$. Состояние кубита – "немного" (с вероятностью $\left| {a^2} \right|$) ложно и "немного" (с вероятностью $\left| {b^2} \right|$ ) истинно.

Наиболее важным отличием кубитов от классических битов является не непрерывная природа суперпозиционных состояний, а возможность квантового перепутывания состояний в системе кубитов. В квантовой механике размерность пространства состояний системы в целом есть произведение (а не сумма) размерностей пространств состояний отдельных подсистем. Система из $N$ кубитов имеет $2^N$, а не $2N$ базисных состояний. Произвольное состояние $N$ кубитов $a_1\mid0\bigr\rangle+b_1\mid 1\bigr\rangle)(a_2\mid0\bigr\rangle+b_2\mid 1\bigr\rangle)...(a_n\mid0\bigr\rangle+b_n\mid 1\bigr\rangle)$ содержит все возможные бинарные строки (комбинации из нулей и единиц) длиной $N$. В приведенном выше примере для $N=3$ все $8$ двоичных чисел могут быть закодированы в трех кубитах одновременно. Это становится возможным за счет квантовомеханического перепутывания. Нелокальные корреляции в системе кубитов и обеспечивают экспоненциально большое вычислительное пространство и параллелизм квантовых вычислений.

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

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

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

Состояния квантовой системы и их преобразования можно описать используя компактные бра/кет обозначения, введённые Дираком. Кет-векторами $\mid x\bigr\rangle$ обозначают вектор-столбцы и обычно используют для описания квантовых состояний.

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

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

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

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

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

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

Однокубитный гейт $NOT$

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

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

Двукубитный гейт $CNOT$

Двубитный гейт $CNOT$ (Controlled NOT), действующий на двукубитное состояние в общем виде записывается так: $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$ $+R_{11}\left | \ 10\right \rangle +R_{10} \left | \ 11\right \rangle$

В классическом случае это просто $XOR$.

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

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

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

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

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

название гейта	графическое обозначение	матричная запись	таблица истинности
$NOT$		$\begin{pmatrix} 0& 1 \\ 1 & 0 \end{pmatrix}$	$\begin{array}{|c|c|} 0 & 1 \\ 1 & 0 \\ \end{array}$
$CNOT$		$\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0& 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$	$\begin{array}{|c c|c c|} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array}$
$H$ (Hadamard)	‎	$\frac{1}{\sqrt{2}}\begin{pmatrix} 1& 1 \\ 1 & -1 \end{pmatrix}$	$\begin{array}{|c|c|} 1 &\frac{1}{\sqrt{2}} \\ 0 & \frac{1}{\sqrt{2}}\\ \end{array}$
$S$ (swap)		$\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$	$\begin{array}{|c c|c c|} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array}$
$CCNOT$ (Toffoli)		$\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}$	$\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}$
$CSWAP$ (гейт Фредкина)		$\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}$	$\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}$

Применение квантовых гейтов

Квантовая модель вычислений позволяет:

• Разложить число на множители за $n^2$.
• Сделать полный перебор за ${\sqrt{n}}$
• Осуществить дискретный алгоритм нахождения логарифма за полиномиальное время
• Создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится

Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).

В 2005 году группой Ю. Пашкина при помощи японских специалистов был построен двухкубитный квантовый процессор на сверхпроводящих элементах.

В ноябре 2009 года физикам из Национального института стандартов и технологий в США впервые удалось собрать программируемый квантовый компьютер, состоящий из двух кубит.

11 мая 2011 года представлен компьютер D-Wave One, созданный на базе 128-кубитного процессора.

В декабре 2012 года представлен новый процессор Vesuvius, который объединяет 512 кубит.

См.также

• Троичная логика
• Контактная схема

Источники информации

• Философия квантовых вычислений

• Сыч Д.В. "Исследование возможностей реализации квантовых алгоритмов на аналоговых вычислительных машинах

• Гайнутдинова А. Ф. "Квантовые вычисления"

• Введение в квантовые вычисления

• Квантовая криптография стучится в дверь