Uniwersalność bramy Toffoli

Odnośnie kwantowej bramy Toffoli :

1. czy jest klasycznie uniwersalny, a jeśli tak, to dlaczego?
2. czy jest kwantowo uniwersalny i dlaczego?

Toffoli jest uniwersalny do obliczeń klasycznych (jak pokazuje @Victor). Jednak Toffoli NIE jest uniwersalny do obliczeń kwantowych (chyba że mamy coś szalonego jak ).$P = BQP$

Aby być uniwersalnym w obliczeniach kwantowych (zgodnie ze zwykłą definicją), grupa generowana przez wasze bramki musi być gęsta w jednostkach. Innymi słowy, biorąc pod uwagę arbitralny i docelową jednostkową istnieje sposób na zastosowanie skończonej liczby bramek kwantowych w celu uzyskania jednolitego takiego, że .U U ′ | | U - U ′ | | < $\epsilon$$U$$U'$$||U - U'|| < \epsilon$

Sam Toffoli wyraźnie nie jest uniwersalny w tej definicji, ponieważ zawsze przyjmuje stany bazowe do stanów bazowych, a zatem nie może implementować czegoś, co wymaga . Innymi słowy, nie może tworzyć superpozycji.$|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

Z cytowanego artykułu w Wikipedii :

Brama Toffoli jest uniwersalna; oznacza to, że dla każdej funkcji boolowskiej f (x1, x2, ..., xm) istnieje obwód składający się z bramek Toffoli, który przyjmuje x1, x2, ..., xm i niektóre dodatkowe bity ustawione na 0 lub 1 i wyjścia x1, x2, ..., xm, f (x1, x2, ..., xm) i kilka dodatkowych bitów (zwanych śmieciami). Zasadniczo oznacza to, że można użyć bramek Toffoli do budowy systemów, które będą wykonywać dowolne pożądane obliczenia funkcji logicznej w sposób odwracalny.

Co w uproszczeniu oznacza, że ​​dowolną funkcję boolowską można zbudować tylko z bramkami Toffoli.

Funkcje boolowskie są zwykle budowane z bramek OR, AND i NOT, które można łączyć, tworząc dowolną funkcję boolowską. Powszechnie wiadomo, że to samo jest możliwe tylko w przypadku bram NOR lub tylko w przypadku bram NAND.

Bramę Toffoli można podsumować jako:

$\rm{Toffoli}(a, b, c) = \begin{cases} (a, b, ¬c) & \mbox{when }a=b=1 \\ (a, b, c) & \mbox{otherwise.}\end{cases}$

Ponieważ pierwszy i drugi wynik są zawsze równe pierwszemu i drugiemu wejściowi, możemy je odrzucić. Więc mamy:

$\rm{Toffoli}'(a, b, c) = \begin{cases} ¬c & \mbox{when }a=b=1 \\ c & \mbox{otherwise.}\end{cases}$

Dzięki temu możliwe jest zdefiniowanie bramki NAND jako:

$\operatorname{NAND}(a, b) = \rm{Toffoli}'(a, b, 1)$

Ponieważ brama NAND jest uniwersalna, a brama NAND może być zdefiniowana jako brama Toffoli, brama Toffoli jest uniwersalna.

Istnieje inny sposób na udowodnienie, że Toffoli jest uniwersalny, poprzez bezpośrednią budowę bramek AND i NOT:

$\operatorname{NOT}(x) = \rm{Toffoli}'(1, 1, x)$

$\operatorname{AND}(a, b) = \rm{Toffoli}'(a, b, 0)$

Następnie możemy zbudować bramę OR na podstawie praw De Morgana :

$\operatorname{OR}(a, b) = \operatorname{NOT}(\operatorname{AND}(\operatorname{NOT}(a), \operatorname{NOT}(b)) = \rm{Toffoli}'(1, 1, \rm{Toffoli}'(\rm{Toffoli}'(1, 1, a), \rm{Toffoli}'(1, 1, b), 0))$

EDYCJA, ponieważ pytanie było edytowane, a jego zakres zmieniony:

Po pierwsze, nie rozumiem obliczeń ilościowych, więc jeśli coś jest nie tak, dodaj komentarz. Zrobiłem trochę badań, aby spróbować uzupełnić tę odpowiedź, i zakończyłem to:

Brama Toffoli jest odwracalna (ale użyte powyżej Toffoli nie jest). Oznacza to, że wszelkie wykonane z nim obliczenia można cofnąć. To jest:

$(a, b, c) = \rm{Toffoli}(\rm{Toffoli}(a, b, c))$

Co oznacza, że ​​dla każdego potrójnego (a, b, c), jeśli Toffoli zostanie zastosowany dwukrotnie, oryginalne wejście zostanie pobrane jako wyjście.

Odwracalność jest ważna, ponieważ bramki kwantowe muszą być odwracalne, dlatego (klasyczna) bramka Toffoli może być z tego powodu używana jako bramka kwantowa.

Jak wykazano tutaj , bramka Deutsch jest zdefiniowana w podobny sposób, jak brama Toffoli, ale zamiast klasycznej bramy jest bramą ilościową:

$\operatorname{Deutsch}(a, b, c) = |a,b,c\rangle \mapsto \begin{cases} i \cos(\theta) |a,b,c\rangle + \sin(\theta) |a,b,1-c\rangle & \mbox{for }a=b=1 \\ |a,b,c\rangle & \mbox{otherwise.}\end{cases}$

W ten sposób brama Toffoli jest szczególnym przypadkiem bramy Deutsch, w której:

$\rm{Toffoli}(a, b, c) = \operatorname{Deutsch}(\frac{\pi}{2})(a, b, c)$

Bramka Toffoli wykonuje klasyczne obliczenia, nie ma operacji przesunięcia fazowego, co oznaczałoby, że bramę Toffoli można stosować tylko do przesunięć fazowych 90 stopni ( ) (i łącząc wiele bramek, aby uzyskać wielokrotności 90 stopni). Ale oznacza to również, że nie można go użyć do stworzenia sobrepozycji stanu, ponieważ wymagałoby to przesunięć fazowych na kątach, które nie są wielokrotne niż 90 stopni, dlatego brama Toffoli nie jest uniwersalną bramą kwantową.$\frac{\pi}{2}$

Uniwersalny kwantowy zestaw Tgate można uzyskać, łącząc bramę Toffoli z bramką Hadamarda. Właśnie to robi bramka Deutsch.

Ciekawe referencje można znaleźć tutaj , tutaj i tutaj . Powinno tu być możliwe cenne odniesienie pokazujące podstawy transformacji Deutscha , jednak link jest chroniony hasłem.