Universalität des Toffoli-Tors

In Bezug auf das Quantentoffoli- Tor :

1. ist es klassisch universell und wenn ja, warum?
2. ist es quantenuniversal und warum?

Toffoli ist universell für die klassische Berechnung (wie von @Victor gezeigt). Toffoli ist jedoch NICHT universell für die Quantenberechnung (es sei denn, wir haben etwas Verrücktes wie ).$P = BQP$

Um für die Quantenberechnung universell zu sein (gemäß der üblichen Definition), muss die von Ihren Gattern erzeugte Gruppe in den Unitaries dicht sein. Mit anderen Worten, wenn ein beliebiges und ein beliebiges Zieleinheits- U gegeben sind, gibt es eine Möglichkeit, eine endliche Anzahl von Quantentoren anzuwenden, um ein einheitliches U 'zu erhalten, so dass | | U - U ′ | | < ϵ .$\epsilon$$U$$U'$$||U - U'|| < \epsilon$

Toffoli an sich ist unter dieser Definition eindeutig nicht universell, da es immer Basiszustände zu Basiszuständen nimmt und daher etwas, das | benötigt, nicht implementieren kann 0 ⟩ → 1zum Beispiel. Mit anderen Worten, es kann keine Überlagerung erzeugen.$|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

Aus dem Wikipedia-Artikel, den Sie zitiert haben :

Das Toffoli-Tor ist universell; Dies bedeutet, dass es für jede Boolesche Funktion f (x1, x2, ..., xm) eine Schaltung gibt, die aus Toffoli-Gates besteht, die x1, x2, ..., xm und einige zusätzliche Bits, die auf 0 oder 1 gesetzt sind, verwendet und ausgibt x1, x2, ..., xm, f (x1, x2, ..., xm) und einige zusätzliche Bits (Müll genannt). Im Wesentlichen bedeutet dies, dass man Toffoli-Gatter verwenden kann, um Systeme zu erstellen, die jede gewünschte Boolesche Funktionsberechnung reversibel durchführen.

Einfach ausgedrückt bedeutet dies, dass jede Boolesche Funktion nur mit Toffoli-Toren konstruiert werden kann.

Boolesche Funktionen bestehen normalerweise aus OR-, AND- und NOT-Gates, die kombiniert werden können, um eine beliebige boolesche Funktion zu bilden. Es ist allgemein bekannt, dass dies nur mit NOR-Gattern oder nur mit NAND-Gattern möglich ist.

Das Toffoli-Tor kann wie folgt zusammengefasst werden:

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

Da der erste und der zweite Ausgang immer gleich dem ersten und dem zweiten Eingang sind, können wir sie ignorieren. Also haben wir:

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

Damit ist es möglich, das NAND-Gatter wie folgt zu definieren:

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

Da das NAND-Gatter universell ist und das NAND-Gatter als Toffoli-Gatter definiert werden kann, ist das Toffoli-Gatter universell.

Es gibt einen anderen Weg, um zu beweisen, dass Toffoli universell ist, indem Sie die UND- und NICHT-Gatter direkt konstruieren:

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

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

Dann können wir das ODER-Gatter unter Verwendung von De Morgans Gesetzen konstruieren :

$\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))$

BEARBEITEN, da die Frage bearbeitet und ihr Umfang geändert wurde:

Erstens verstehe ich Quantical Computing nicht. Wenn also etwas nicht stimmt, fügen Sie bitte einen Kommentar hinzu. Ich habe ein wenig nachgeforscht, um diese Antwort zu vervollständigen und endete damit:

Das Toffoli-Tor ist umkehrbar (das oben verwendete Toffoli-Tor jedoch nicht). Dies bedeutet, dass jede damit durchgeführte Berechnung rückgängig gemacht werden kann. Das ist:

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

Dies bedeutet, dass für jedes Triple (a, b, c), wenn der Toffoli zweimal angewendet wird, die ursprüngliche Eingabe als Ausgabe erhalten wird.

Reversibilität ist wichtig, da Quantentore reversibel sein müssen, weshalb das (klassische) Toffoli-Gate als Quantentor verwendet werden kann.

Wie hier gezeigt , ist das Deutsch-Tor ähnlich wie das Toffoli-Tor definiert, es ist jedoch kein klassisches Tor, sondern ein quantisches:

$\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}$

Auf diese Weise ist das Toffoli-Tor ein besonderer Fall des Deutsch-Tors, bei dem:

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

$\frac{\pi}{2}$

Ein universeller Quanten-Tgate-Satz kann erhalten werden, wenn man das Toffoli-Gate mit dem Hadamard-Gate kombiniert. Genau das macht das Deutsch Gate.

Interessante Referenzen finden Sie hier , hier und hier . Ein möglicher wertvoller Verweis, der die Grundlagen der Deutsch-Transformation zeigt, sollte hier sein , der Link ist jedoch passwortgeschützt.