Как я могу реализовать n-битные ворота Toffoli?

Я хочу создать ворота Toffoli, управляемые n кубитами, и реализовать их в QISKit. Можно ли это сделать? Если так, то как?

Простой способ сделать это показан на рисунке 4.10 Nielsen & Chuang.

Где U может быть любым поворотом одного кубита (в этом случае X-вентиль).

Эта схема работает следующим образом: мы хотим применить U к целевому кубиту, только если AND всех контрольных кубитов равно 1. Нормальный Toffoli дает нам AND 2 кубитов. Таким образом, связав несколько Toffolis, мы можем получить c1.c2.c3.c4.c5, с тем уловом, что некоторые «рабочие» (или вспомогательные) кубиты были введены для хранения промежуточных результатов. После применения окончательного CU, мы получаем конечный результат в целевой. Теперь мы можем очистить промежуточные рабочие кубиты, отменив их вычисления и вернув их в состояние | 0>. Эта модель обратимых вычислений известна как метод "compute-copy-uncompute" и была первой предложена Чарли Беннеттом в 1973 году .

Вот код QISKit для построения схемы и ее визуализации:

from qiskit import QuantumRegister, QuantumCircuit

n = 5  # must be >= 2

ctrl = QuantumRegister(n, 'ctrl')
anc = QuantumRegister(n-1, 'anc')
tgt = QuantumRegister(1, 'tgt')

circ = QuantumCircuit(ctrl, anc, tgt)

# compute
circ.ccx(ctrl[0], ctrl[1], anc[0])
for i in range(2, n):
    circ.ccx(ctrl[i], anc[i-2], anc[i-1])

# copy
circ.cx(anc[n-2], tgt[0])

# uncompute
for i in range(n-1, 1, -1):
    circ.ccx(ctrl[i], anc[i-2], anc[i-1])
circ.ccx(ctrl[0], ctrl[1], anc[0])    

from qiskit.tools.visualization import circuit_drawer
circuit_drawer(circ)

Урожайность:

Я хочу добавить метод, который не использует вспомогательные кубиты, но требует, чтобы ворота были более сложными, чем просто управляемые - нет. Я считаю, что этот метод был впервые представлен Barenco et. и др. в этой статье лемма 7.5:

$V^2=U$$V^2=X$

$$V = \frac{1}{2} \begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \\ \end{pmatrix} \ .$$

Это рекурсивное определение, поэтому управляющий логический элемент n-кубита определяется в терминах управляющего логического элемента n-1-кубита. Это будет продолжаться до тех пор, пока вы не достигнете двух кубитных ворот CNOT.

Эта реализация немного сложна, однако существует более простая, если не возражать против сбора относительной фазы (см. Лемму 7.9 той же статьи).

$V$

В QuantumCircuit компании Qiskit есть метод mct для построения нескольких элементов управления Toffoli с несколькими режимами: базовый, basic-dirty-ancilla, продвинутый, noancilla. Например, ворота Тоффоли с 3 контрольными кубитами:

from qiskit import QuantumCircuit, QuantumRegister

controls = QuantumRegister(3, "c_qb")
target = QuantumRegister(1, "t_qb")
circuit = QuantumCircuit(controls, target)

circuit.mct(controls, target[0], None, mode='advanced')

print(circuit)

Выход:

c_qb_0: |0>──────■────────■────────────────■──────────────────────────────────■──────────────────────────────────■────────────────────
                 │      ┌─┴─┐            ┌─┴─┐                                │                                  │                    
c_qb_1: |0>──────┼──────┤ X ├──────■─────┤ X ├──────■────────■────────────────┼─────────────────■────────────────┼────────────────────
                 │      └───┘      │     └───┘      │      ┌─┴─┐            ┌─┴─┐             ┌─┴─┐            ┌─┴─┐                  
c_qb_2: |0>──────┼─────────────────┼────────────────┼──────┤ X ├──────■─────┤ X ├──────■──────┤ X ├──────■─────┤ X ├──────■───────────
           ┌───┐ │-pi/4 ┌───┐┌───┐ │pi/4 ┌───┐┌───┐ │-pi/4 ├───┤┌───┐ │pi/4 ├───┤┌───┐ │-pi/4 ├───┤┌───┐ │pi/4 ├───┤┌───┐ │-pi/4 ┌───┐
t_qb_0: |0>┤ H ├─■──────┤ H ├┤ H ├─■─────┤ H ├┤ H ├─■──────┤ H ├┤ H ├─■─────┤ H ├┤ H ├─■──────┤ H ├┤ H ├─■─────┤ H ├┤ H ├─■──────┤ H ├
           └───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘