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

17

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?

Ali Javadi
quelle
Vielen Dank für die Fragen und Antworten. Schön dich hier zu sehen, Ali!
James Wootton

Antworten:

18

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

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:

Qiskit generierte Schaltung

Ali Javadi
quelle
7

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: Bildbeschreibung hier eingeben

Wo . In diesem Fall möchte man, dass und damit V2=UV2=X

V=12(1+ich1-ich1-ich1+ich) .

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

maor
quelle
Hat jemand daran gearbeitet, dieses Gate auf Cirq zu implementieren?
Enrique Segura
5

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