Implementacja bramki CCCNOT przy użyciu tylko bram Toffoli


10

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.


Używanie tylko bramek Toffoli, czy Toffoli i CNOT to uczciwa gra?
user1271772,

Dozwolone są tylko bramy Toffoli.
chuster

1
Jaka część tego pytania jest kwantowa? Wygląda na to, że chcesz rozłożyć klasyczną bramę odwracalną (CCCNOT) na mniejsze klasyczne bramy odwracalne (CCNOT).
user1271772,

1
Samo pytanie nie dotyczy obliczeń kwantowych, ale bramki są ważne dla obwodów kwantowych.
chuster

Odpowiedzi:


8

Myślę, że szukasz tego obwodu. Tutaj b1,b2),b3),b4{0,1} , a jest modułem dodatkowym 2) .

wprowadź opis zdjęcia tutaj

Tutaj piąty kubit jest używany jako kubit pomocniczy lub kubełkowy . Zaczyna się o |0 a kończy w |0 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 . 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 . 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 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ć dododoN.OT. -gate, który działa na czterech qubitach. Można określić następującą macierz (reprezentację matryca Pauli- X -gate):

X=[0110]
Ponadto, oznaczenia N -wymiarową macierz tożsamości przez IN . Teraz obserwujemy, że reprezentacja macierzy drzwi CCCNOT , działająca na cztery kubity, daje następująca macierz 16×16 :
CCCNOT=[I1400X]
det(CCCNOT)=1
4
Toffaoljaja2)=[ja600X]ja2)=[ja1200Xja2)]=[ja120000ja2)0ja2)0]
det(T.ofafaoljaja2))=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|0010|0101|01102)S.4jest generowany przez transpozycje w ), okazuje się, że dla wszystkich bramek Toffoli, zastosowanych do dowolnej kombinacji kontrolnych i docelowych, jego reprezentacja macierzowa ma wyznacznik .S.41

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)AB1CCCNOT4

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 dlaCCCNOT5

CCCNOT.ja2)=[ja1400X]ja2)=[ja280000ja2)0ja2)0]
det(dododoN.OT.ja2))=1
dododoN.OT.51-15 kubity, jak już wiedzieliśmy, z powodu wyraźnie skonstruowanego obwodu, o który poprosił OP.


1
przydatne byłoby źródło lub metoda użyta do uzyskania obwodu!
glS

1
Nie znam źródeł, które wyjaśniają, jak zaprojektować takie obwody w sposób kompleksowy. Źródłem, z którego korzystałem podczas nauki o obliczeniach kwantowych, była książka Nielsena i Chuanga oraz notatki z wykładu, które można znaleźć tutaj: homepages.cwi.nl/~rdewolf/qcnotes.pdf , ale źródła te nie koncentrują się specjalnie na projektowaniu obwodów kwantowych.
arriopolis

2
Próbowałem rozwinąć nieco bardziej działanie obwodu. Mam nadzieję, że to pomaga w projektowaniu obwodów podobnych do tego! :)
arriopolis,

Czy to możliwe bez środków pomocniczych?
user1271772,

1
Ciekawe pytanie, ale nie wydaje mi się. Ilekroć ktoś wypisze reprezentację macierzy bramą Toffoli działającego w systemie czterech qubit, wyznacznik tej macierzy jest . Jednak decydującym o reprezentacji macierzowej o C, C, C N O T -gate Działając na 4 qubitach jest - 1 , a więc nie może być wykonana przez kolejnych zastosowań bramy Toffoli. Z tego pomocniczego qubitu z tą różnicą, że reprezentacja macierz C, C, C N O T -gate staje + 1 . +1dododoN.OT.4-1dododoN.OT.+1
arriopolis
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.