Многокубитные операции

Простейшим многокубитным оператором можно считать оператор SWAP. Он меняет местами значения двух кубитов. Конечно, можно считать, что это просто специально искривленные провода, но наличие оператора SWAP позволяет записать алгоритмы для некоторых архитектур квантовых компьютеров (обычно на сверхпроводниках), где невозможно связать два произвольных кубита, а многокубитовые операции должны производиться только над соседними кубитами.

Обозначения SWAP (если мы хотим подчеркнуть, что это гейт, или если хотим показать изменение порядка проводов):

Матрицей SWAP-гейта будет такая: \[ SWAP = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} \]

Более интересным оператором является CNOT. Можно сказать, что это простейший вид условного оператора: если управляющий кубит установлен в 1, то к управляемому кубиту применяется оператор NOT; если управляющий кубит установлен в 0, то управляемый кубит не меняется.

Обозначение CNOT следующее (управляющий кубит отмечен черным кружком, на управляемом нарисован по сути NOT; управление обозначено вертикальной линией):

Матрица CNOT выглядит так: \[ CNOT = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix} \]

Аналогичным образом можно определить и более сложные условные операции, в которых к управляемым кубитам применяется не NOT, а произвольное унитарное преобразование \(U\).

Такие преобразования называют controlled-U, и на схемах обозначают следующим образом:

Что получится, если к двум управляемым кубитам применять CNOT? Получится CCNOT (или \(C^2NOT\)). Он преобразует базисные состояния так:

\begin{equation*} |110\rangle \mapsto |111\rangle; \end{equation*} \begin{equation*} |111\rangle \mapsto |110\rangle; \end{equation*}

а для других комбинаций \(a,b,c \in \{0,1\}\)

\begin{equation*} |abc\rangle \mapsto |abc\rangle. \end{equation*}

Обозначается CCNOT следующим образом:

Аналогичным образом можно строить и операторы, где несколько кубитов управляют произвольным преобразованием \(U\).

Похожим образом можно выполнять управление, когда преобразование выполняется, если управляющий кубит установлен в 0 (а не в 1, как было в прошлых гейтах).

На схеме в этом случае управляющий кубит обозначается пустым кружком. Вот, к примеру, так выглядит NOT, управляемый таким образом:

Сколько всего возможно операторов, действующих на \(n\) кубитах?

Поскольку операторов столько же, сколько и унитарных матриц размера \(2^n \times 2^n\), и каждый элемент матрицы является комплексным числом, мы получаем, что их несчётное количество (что не означает, конечно, что их изучение займёт несчётное время).

Сколько всего возможно квантовых схем на \(n\) кубитах, содержащих известные нам одно- и многокубитные операторы?

Если исключить параметризованные операторы поворота на произвольный угол, таких схем будет счётное количество.

Как же получается, что нам достаточно только счётного количества схем из конечного числа операторов? Не должны ли мы изучать и изучать различные операторы на трёх, четырёх и большем количестве кубитов?

На этот вопрос отвечает теорема Соловэя–Китаева, которая гласит следующее.

Теорема приводится без доказательства, которое достаточно сложное. Желающих его изучить я отсылаю к книге Нильсена и Чанга.