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

Мы начнем с рассмотрения различных однобитных операций и одной двубитной – XOR-операции. Их комбинации достаточны для построения Тоффоли-гейта для квантовых битов, или, на самом деле, любой унитарной операции на конечном числе битов.

Начнем с одного квантового бита. Если представить состояния $|\downarrow\rangle$ и. $|\uparrow\rangle$ (т. е. $|0\rangle$ и $|1\rangle$ ) как векторы $\left(\begin{array}{l}1 \\ 0\end{array}\right)$ и $\left(\begin{array}{l}0 \\ 1\end{array}\right)$, соответственно, то наиболее общему унитарному преобразованию отвечает матрица $2 \times 2$ вида
\[
U_{\theta} \equiv\left(\begin{array}{cc}
e^{i(\delta+\sigma+\tau)} \cos (\theta / 2) & e^{-i(\delta+\sigma-\tau)} \sin (\theta / 2) \\
-e^{i(\delta-\sigma+\tau)} \sin (\theta / 2) & e^{i(\delta-\sigma-\tau)} \cos (\theta / 2)
\end{array}\right),
\]

в которой обычно полагают $\delta=\sigma=\tau=0$ [14]. Используя этот оператор, мы можем инвертировать биты:
\[
U_{\pi}|0\rangle=-|1\rangle, \quad U_{\pi}|1\rangle=|0\rangle .
\]

Происшедшее изменение знака означает появление фазового множителя, который не влияет на логическую операцию гейтов и может быть опущен, если мы захотим, сразу или на более позднем этапе. Такие однобитные вычисления изображены схематично как квантовая цепь на рис. $5[14,15]$.
\[
|A\rangle-U_{\theta}|A\rangle
\]

Рис. 5. Схематичная диаграмма квантового цикла для однобитного гейта. Линия изображает один квантовый бит (такой, как задает частица спина $1 / 2$ ). Первоначально этот бит имеет состояние, описываемое вектором $|A\rangle$; после того, как он пройдет через эту цепь, он выйдет в состоннии $U_{\theta}|A\rangle$.

Другой важный однобитный гейт – это $U_{-\pi / 2}$, который отображает состояние со спином вниз в равную суперпозицию состояний со спином вниз и спином вверх
\[
U_{-\pi / 2}|0\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)
\]

Рассмотрим строку, задаваемую $k$ частицами спина $1 / 2$, спины которых первоначально направлены вниз. Если мы применим наш гейт независимо к каждой частице, то получим суперпозицию всех возможных двоичных строк длины $k$ :
\[
|0\rangle \rightarrow \frac{1}{\sqrt{q}} \sum_{a=0}^{q-1}|a\rangle
\]
где $q=2^{k}$. Наш компьютер находится теперь в суперпозиции экспоненциально большого числа целых чисел $a$ от 0 до $2^{k}-1$. Предположим, что мы можем теперь пост $\square$ которая отображает пару двоичных строк Тогда такой унитарный перпозицию состояний
\[
\frac{1}{\sqrt{q}} \sum_{a=0}^{q-1}|a ; 0\rangle \rightarrow \frac{1}{\sqrt{q}} \sum_{a=0}^{q-1}|a ; f(a)\rangle,
\]

вычисляет функцию $f(a)$ параллельно экспоненциально большое число раз для различных входных значений $a$.

Чтобы понять, как такие унитарные операторы могут быть построены из нескольких элементарных операторов, рассмотрим XOR-гейт $[14,15]$.
Записывая двухчастичные базисные состояния как вектора
\[
|00\rangle=\left(\begin{array}{l}
1 \\
0 \\
0 \\
0
\end{array}\right), \quad|01\rangle=\left(\begin{array}{l}
0 \\
1 \\
0 \\
0
\end{array}\right), \quad|10\rangle=\left(\begin{array}{l}
0 \\
0 \\
1 \\
0
\end{array}\right), \quad|11\rangle=\left(\begin{array}{l}
0 \\
0 \\
0 \\
1
\end{array}\right),
\]

мы можем представить XOR гейт унитарным оператором
\[
U_{\text {XOR }} \equiv\left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right)
\]

Здесь первая частица действует как условный гейт для инвертирования состояния второй частицы. Легко проверить, что состояние второй частицы отвечает действию XOR-гейт, заданного в таблице 1 . Квантовая цепь для XOR-гейта изобпаженцнапис 6.

Рис. 6. Диаграмма квантового цикла для XOR-гейта. Низший бит $|B\rangle$ инвертируется всякий раз, когда верхний бит $|A\rangle$ является единицей.

Эта цепь эквивалентна элементарной команде: если $(|A\rangle=1)$, то $|B\rangle \rightarrow \mathrm{NOT}|B\rangle$, что можно понимать как пример программы квантового компьютера [22]. Скобки |> являются напоминанием того, что мы имеем дело с квантовыми, а не классическими битами. XOR-гейт позволяет перемещать информацию, как показано на рис. 7 .
Рис. 7. Цикл для перестановки местами пары битов.
Как построить Тоффоли-гейт? Главная проблема с этим гейтом заключается в том, что он требует три бита на входе и три на выходе. Кажется, что это соответствует квантовому процессу рассеяния, включающему трехчастичные столкновения [16], требующие (возможно) непомерного контроля за частицами [5]. К счастью, Тоффоли-гейт может быть построен только из процессов двухчастичного рассеяния $[15,17$, $18,19,20]$. В частности, здесь мы показываем конструкцию, включающую XOR-гейт и некоторые однобитные гейты $U_{A}$ (рис. 8) [14].

Рис. 8. Тоффоли-гейт, построенный из двубитных XOR-гейтов плюс некоторых однобитных гейтов $[5,14]$. Эта цепь вводит некоторые дополнительные знаки в унитарной матрице $U_{\mathrm{XOR}}$, которые могут быть удалены на более позднем этапе.

XOR-гейт не только достаточен для всех логических операций на квантовом компьютере, но он может быть использован для построения произвольных унитарных преобразований на любом конечном наборе битов. Рассматривались многочисленные предложения, как создать такие гейты $[2,6]$.