Implementieren eines CCCNOT-Gates nur mit Toffoli-Gates

10

Ein CCCNOT-Gatter ist ein reversibles Vier-Bit-Gatter, das sein viertes Bit genau dann umdreht, wenn sich die ersten drei Bits alle im Zustand .1

Wie würde ich ein CCCNOT-Gate mit Toffoli-Gates implementieren? Angenommen, die Bits im Arbeitsbereich beginnen mit einem bestimmten Wert, entweder 0 oder 1, sofern Sie sie auf diesen Wert zurücksetzen.

Chuster
quelle
Verwenden Sie nur Toffoli-Tore oder Toffoli und CNOT sind Freiwild?
user1271772
Es sind nur Toffoli-Tore erlaubt.
Chuster
1
Welcher Teil dieser Frage ist Quanten? Es scheint, dass Sie ein klassisches reversibles Gate (CCCNOT) in kleinere klassische reversible Gates (CCNOTs) zerlegen möchten.
user1271772
1
Die Frage selbst bezieht sich nicht auf das Quantencomputing, aber die Gates sind für die Quantenschaltung wichtig.
Chuster

Antworten:

8

Ich denke, was Sie suchen, ist die folgende Schaltung. Hier ist und Additionsmodulo .b1,b2,b3,b4{0,1}2

Geben Sie hier die Bildbeschreibung ein

Hier wird das fünfte Qubit als Hilfs- oder Ancilla-Qubit verwendet . Es beginnt bei und endet bei wenn die Schaltung angelegt wird.|0|0

Lassen Sie mich näher darauf eingehen, wie diese Schaltung funktioniert. Die Idee ist, zunächst zu überprüfen, ob sich die ersten beiden Qubits im Zustand . Dies kann mit einem einzelnen Toffoli-Gate erfolgen, und das Ergebnis wird im Hilfs-Qubit gespeichert. Jetzt reduziert sich das Problem auf das Umdrehen von Qubit , wenn Qubits und das Hilfs-Qubit in . Dies kann auch erreicht werden, indem ein Toffoli-Gate angewendet wird, nämlich das mittlere in der oben gezeigten Schaltung. Schließlich dient das letzte Toffoli-Gatter dazu, das temporäre Ergebnis, das wir im Hilfs-Qubit gespeichert haben, nicht zu berechnen , so dass der Zustand dieses Qubits nach dem Anlegen der Schaltung auf zurückkehrt.|143|1| 0 |0


Im Kommentarbereich stellte sich die Frage, ob es möglich ist, eine solche Schaltung nur mit Toffoli-Gates ohne Verwendung von Hilfs-Qubits zu implementieren. Diese Frage kann verneint werden, wie ich hier zeigen werde.

Wir wollen das -gate implementieren , das auf vier Qubits wirkt. Wir können die folgende Matrix definieren (die Matrixdarstellung des Pauli- Gates): Weiterhin bezeichnen wir die dimensionale Identitätsmatrix mit . Nun beobachten wir, dass die Matrixdarstellung des -Tors, das auf vier Qubits wirkt, durch die folgende Matrix gegeben ist: Daher können wir seine Determinante bestimmen: CCCNOTX

X=[0110]
NINCCCNOT16×16
CCCNOT=[I1400X]
det(CCCNOT)=1
Betrachten Sie nun die Matrixdarstellung des Toffoli-Gates, die auf die ersten drei Qubits eines Qubit-Systems einwirkt. Die Matrixdarstellung lautet wie folgt: (wo wir das Kronecker-Produkt von Matrizen verwendet haben): Berechnung seiner Determinantenausbeuten: 4
ToffoliI2=[I600X]I2=[I1200XI2]=[I120000I20I20]
det(ToffoliI2)=1
Die Toffoli-Tore können natürlich auch auf verschiedene Qubits einwirken. Angenommen, wir lassen das Toffoli-Gate auf das erste, zweite und vierte Qubit einwirken, wobei das vierte Qubit das Ziel-Qubit ist. Dann erhalten wir die neue Matrixdarstellung aus der oben angezeigten, indem wir die Spalten austauschen, die den Zuständen entsprechen, die sich nur im dritten und vierten Qubit unterscheiden, dh mit , mit usw. Wichtig ist hierbei, dass die Anzahl der Spaltenwechsel gerade ist und die Determinante daher unverändert bleibt. Da wir jede Permutation von Qubits als eine Folge aufeinanderfolgender Permutationen von nur Qubits ( schreiben können|0001|0010|0101|01102S4wird durch die Transpositionen in ) erzeugt, finden wir, dass für alle Toffoli-Gates, die auf eine beliebige Kombination von Kontroll- und Ziel-Qubits angewendet werden, ihre Matrixdarstellung die Determinante .S41

Als letztes ist zu beachten, dass die Determinante mit der Matrixmultiplikation pendelt, dh , für zwei beliebige Matrizen und die mit der Matrixmultiplikation kompatibel sind. Daher wird jetzt offensichtlich, dass das Anwenden mehrerer Toffoli-Gatter niemals eine Schaltung erzeugt, deren Matrixdarstellung eine andere Determinante als , was insbesondere impliziert, dass das nicht nur mit Toffoli-Gattern auf Qubits implementiert werden kann .det(AB)=det(A)det(B)AB1CCCNOT4

Die offensichtliche Frage ist nun, was sich ändert, wenn wir ein Hilfs-Qubit zulassen. Wir finden die Antwort, wenn wir die Aktion des -Tors auf einem Qubit-System aufschreiben: Wenn wir diese Determinante berechnen, finden wir : Daher ist die Determinante des -Tors, das auf Qubits wirkt, anstelle von . Aus diesem Grund ist das vorherige Argument für nicht gültigCCCNOT5

CCCNOTI2=[I1400X]I2=[I280000I20I20]
det(CCCNOTI2)=1
CCCNOT5115 Qubits, wie wir bereits aufgrund der explizit konstruierten Schaltung wussten, nach der das OP gefragt hatte.

arriopolis
quelle
1
Eine Quelle oder Methode zur Ableitung der Schaltung wäre nützlich!
glS
1
Ich kenne keine Quellen, die erklären, wie solche Schaltungen umfassend zu gestalten sind. Die Quellen, die ich beim Erlernen des Quantencomputers verwendet habe, waren das Buch von Nielsen und Chuang und die Vorlesungsunterlagen, die hier zu finden sind: homepages.cwi.nl/~rdewolf/qcnotes.pdf , aber diese Quellen konzentrieren sich nicht speziell auf das Design von Quantenschaltungen.
Arriopolis
2
Ich habe versucht herauszufinden, wie die Schaltung ein bisschen mehr funktioniert. Hoffe, dies hilft beim Entwerfen ähnlicher Schaltungen! :)
Arriopolis
Ist es ohne Hilfsmittel möglich?
user1271772
1
Interessante Frage, aber ich denke nicht. Immer wenn man die Matrixdarstellung eines Toffoli-Gates schreibt, das auf ein Vier-Qubit-System einwirkt, ist die Determinante dieser Matrix . Die Determinante der Matrixdarstellung des , das auf Qubits wirkt, ist jedoch , so dass sie nicht durch aufeinanderfolgende Anwendungen des Toffoli-Gates konstruiert werden kann. Mit dieser Hilfs Qubit, ist der Unterschied , dass die Matrixdarstellung des -Gate wird . C C C N O T.+1CCCNOT41CCCNOT+1
Arriopolis