Wie kann ich ein n-Bit-Toffoli-Gate implementieren?

Ich möchte ein Toffoli-Gate erstellen, das von n Qubits gesteuert wird, und es in QISKit implementieren. Kann das gemacht werden? Wenn das so ist, wie?

Ein einfacher Weg, dies zu tun, ist in Abbildung 4.10 von Nielsen & Chuang dargestellt.

Wobei U eine beliebige Single-Qubit-Rotation sein kann (in diesem Fall ein X-Gatter).

Diese Schaltung funktioniert folgendermaßen: Wir wollen U nur dann auf das Ziel-Qubit anwenden, wenn das UND aller Kontroll-Qubits 1 ist. Ein normaler Toffoli gibt uns das UND von 2 Qubits. Wenn wir also ein paar Toffolis verketten, erhalten wir c1.c2.c3.c4.c5 mit dem Haken, dass einige "Work" - (oder Ancilla-) Qubits eingeführt wurden, um Zwischenergebnisse zu speichern. Nach dem Anwenden der endgültigen CU erhalten wir das endgültige Ergebnis im Ziel. Jetzt können wir die Zwischenarbeits-Qubits bereinigen, indem wir ihre Berechnungen rückgängig machen und sie in den Zustand | 0> zurückversetzen. Dieses Modell der reversiblen Berechnung ist als "compute-copy-uncompute" -Verfahren bekannt und wurde erstmals 1973 von Charlie Bennett vorgeschlagen .

Hier ist der QISKit-Code zum Aufbau und zur Visualisierung der Schaltung:

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)

Erträge:

Ich möchte eine Methode hinzufügen, die keine Ancilla-Qubits verwendet, sondern Gates erfordert, die komplizierter sind als nur gesteuert-nicht. Ich glaube, diese Methode wurde zuerst von Barenco et. al. In diesem Artikel , Lemma 7.5:

Wo . In diesem Fall möchte man, dass und damit $V^2=U$$V^2=X$

Dies ist eine rekursive Definition, so dass das Qubit-Steuergatter n in Bezug auf das Qubit-Steuergatter n-1 definiert ist. Dies würde so lange dauern, bis Sie das CNOT mit zwei Qubit-Gates erreichen.

Diese Implementierung ist etwas schwierig, es gibt jedoch eine einfachere, wenn es einem nichts ausmacht, eine relative Phase zu sammeln (siehe Lemma 7.9 desselben Papiers).

Um ein Gate wie in QISKIT zu implementieren , müssen Sie die erweiterten Single-Qubit-Gates verwenden.$V$

QuantumCircuit von Qiskit verfügt über die Methode mct , um ein Toffoli-Tor mit mehreren Steuerelementen und verschiedenen Modi zu erstellen: Basic, Basic-Dirty-Ancilla, Advanced, Noancilla. Zum Beispiel Toffoli Gate mit 3 Kontroll-Qubits:

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)

Ausgabe:

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 ├
           └───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘