Implementieren eines CCCNOT-Gates nur mit Toffoli-Gates

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.

Ich denke, was Sie suchen, ist die folgende Schaltung. Hier ist und Additionsmodulo .$b_1,b_2,b_3,b_4 \in \{0,1\}$$\oplus$$2$

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

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.$|1\rangle$$4$$3$$|1\rangle$| 0 ⟩$|0\rangle$

---

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: $\mathrm{CCCNOT}$$X$

$$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ $N$$I_N$$\mathrm{CCCNOT}$$16 \times 16$ $$\mathrm{CCCNOT} = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix}$$ $$\det(\mathrm{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$ $$\mathrm{Toffoli} \otimes I_2 = \begin{bmatrix} I_6 & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{12} & 0 \\ 0 & X \otimes I_2 \end{bmatrix} = \begin{bmatrix} I_{12} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ $$\det(\mathrm{Toffoli} \otimes I_2) = 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\rangle$$|0010\rangle$$|0101\rangle$$|0110\rangle$$2$$S_4$wird 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 .$S_4$$1$

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)$$A$$B$$1$$\mathrm{CCCNOT}$$4$

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ültig$\mathrm{CCCNOT}$$5$

$$\mathrm{CCCNOT} \otimes I_2 = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{28} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ $$\det(\mathrm{CCCNOT} \otimes I_2) = 1$$ $\mathrm{CCCNOT}$$5$$1$$-1$$5$ Qubits, wie wir bereits aufgrund der explizit konstruierten Schaltung wussten, nach der das OP gefragt hatte.