Implementacja bramki CCCNOT przy użyciu tylko bram Toffoli

Bramka CCCNOT to czterobitowa bramka odwracalna, która odwraca swój czwarty bit, jeśli tylko pierwsze trzy bity są w stanie $1$ .

Jak wdrożyć bramę CCCNOT przy użyciu bram Toffoli? Załóżmy, że bity w obszarze roboczym zaczynają się od określonej wartości, 0 lub 1, pod warunkiem, że powrócisz do tej wartości.

Myślę, że szukasz tego obwodu. Tutaj $b_1,b_2,b_3,b_4 \in \{0,1\}$ , a $\oplus$ jest modułem dodatkowym $2$ .

Tutaj piąty kubit jest używany jako kubit pomocniczy lub kubełkowy . Zaczyna się o $|0\rangle$ a kończy w $|0\rangle$ gdy jest stosowany układ.

Pozwól mi rozwinąć sposób działania tego obwodu. Chodzi przede wszystkim o sprawdzenie, czy pierwsze dwa kubity są w stanie $|1\rangle$ . Można tego dokonać za pomocą pojedynczej bramki Toffoli, a wynik jest przechowywany w kubicie pomocniczym. Teraz problem sprowadza się do odwracania kubitu $4$ , ilekroć kubity $3$ i kubit pomocniczy są w $|1\rangle$ . Można to również osiągnąć, stosując jedno zastosowanie bramki Toffoli, a mianowicie środkowe w pokazanym powyżej obwodzie. Wreszcie ostatnia brama Toffoli służy do obliczenia tymczasowego wyniku, który zapisaliśmy w kubicie pomocniczym, tak że stan tego kubita powraca do $|0\rangle$ po zastosowaniu obwodu.

---

W sekcji komentarzy pojawiło się pytanie, czy możliwe jest zaimplementowanie takiego obwodu przy użyciu tylko bramek Toffoli, bez użycia kubitów pomocniczych. Na to pytanie można odpowiedzieć przecząco, jak pokażę tutaj.

Chcemy wdrożyć $\mathrm{CCCNOT}$ -gate, który działa na czterech qubitach. Można określić następującą macierz (reprezentację matryca Pauli- $X$ -gate):

$$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ Ponadto, oznaczenia $N$ -wymiarową macierz tożsamości przez $I_N$ . Teraz obserwujemy, że reprezentacja macierzy drzwi $\mathrm{CCCNOT}$ , działająca na cztery kubity, daje następująca macierz $16 \times 16$ : $$\mathrm{CCCNOT} = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix}$$ $$\det(\mathrm{CCCNOT}) = -1$$ $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$$ | 0001 ⟩ | 0010 ⟩ | 0101 ⟩ | 0110 ⟩ 2 S 4 S 4 1 Bramy Toffoli mogą oczywiście działać na różne kubity. Załóżmy, że pozwalamy bramce Toffoli działać na pierwszy, drugi i czwarty kubit, gdzie czwarty kubit jest kubitem docelowym. Następnie otrzymujemy nową reprezentację macierzy z tej pokazanej powyżej poprzez zamianę kolumn odpowiadających stanom, które różnią się tylko trzecim i czwartym kubitem, tj. z , z itp. Należy tutaj zauważyć, że liczba zamian kolumn jest parzysta, a zatem determinant pozostaje niezmieniony. Jak możemy zapisać każdą permutację kubitów jako sekwencję kolejnych permutacji tylko kubitów (to znaczy$|0001\rangle$$|0010\rangle$$|0101\rangle$$|0110\rangle$$2$$S_4$jest generowany przez transpozycje w ), okazuje się, że dla wszystkich bramek Toffoli, zastosowanych do dowolnej kombinacji kontrolnych i docelowych, jego reprezentacja macierzowa ma wyznacznik .$S_4$$1$

Ostatnią rzeczą do odnotowania jest to, że wyznacznik dojeżdża do mnożenia macierzy, tj. , dla dowolnych dwóch macierzy i zgodnych z mnożeniem macierzy. Stąd teraz staje się oczywiste, że zastosowanie wielu bramek Toffoli w sekwencji nigdy nie tworzy obwodu, którego reprezentacja macierzowa ma wyznacznik inny niż , co w szczególności oznacza, że nie można wdrożyć -gate przy użyciu tylko bramek Toffoli na kubitach .$\det(AB) = \det(A)\det(B)$$A$$B$$1$$\mathrm{CCCNOT}$$4$

Oczywistym pytaniem jest teraz, co się zmieni, kiedy pozwolimy na dodatkowy kubit. Odpowiedź znajdziemy, gdy działanie -gate w systemie qubit: Jeśli obliczymy ten wyznacznik, znajdziemy : Stąd wyznacznikiem -gate działającego na kubitów jest , zamiast . Dlatego poprzedni argument nie jest ważny dla$\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$ kubity, jak już wiedzieliśmy, z powodu wyraźnie skonstruowanego obwodu, o który poprosił OP.