Toffoli-Tor – Wikipedia

Posted on by
before-content-x4

Universelles reversibles Logikgatter, angewendet im Quantencomputer

Schaltungsdarstellung des Toffoli-Tors
 after-content-x4

In Logikschaltungen ist die Toffoli-Tor (ebenfalls CCNOT-Tor), erfunden von Tommaso Toffoli, ist ein universelles reversibles Logikgatter, was bedeutet, dass jede reversible Schaltung aus Toffoli-Gattern aufgebaut werden kann. Es ist auch als “gesteuert-gesteuert-nicht” -Tor bekannt, das seine Wirkung beschreibt. Es verfügt über 3-Bit-Ein- und Ausgänge; Wenn die ersten beiden Bits beide auf 1 gesetzt sind, wird das dritte Bit invertiert, andernfalls bleiben alle Bits gleich.

Hintergrund[edit]

Ein eingangsverbrauchendes Logikgatter L. ist umkehrbar, wenn für eine Ausgabe ygibt es eine eindeutige Eingabe x so dass sich bewerben L.((x) = y. Wenn ein Tor L. ist reversibel, gibt es ein inverses Gate L.‘, Welche Karten y zu x für welche L.‘(y) = x. Von herkömmlichen Logikgattern ist NOT reversibel, wie aus der nachstehenden Wahrheitstabelle ersichtlich ist.

Das gemeinsame UND-Gatter ist jedoch nicht umkehrbar. Die Eingänge 00, 01 und 10 sind alle dem Ausgang 0 zugeordnet.

Reversible Gates wurden seit den 1960er Jahren untersucht. Die ursprüngliche Motivation war, dass reversible Tore weniger Wärme (oder im Prinzip keine Wärme) abgeben.[1] Wenn wir uns ein Logikgatter als verbrauchend vorstellen, gehen Informationen verloren, da im Ausgang weniger Informationen vorhanden sind als am Eingang. Dieser Informationsverlust verliert aufgrund der thermodynamischen Entropie Energie als Wärme an die Umgebung.[citation needed] Ein anderer Weg, dies zu verstehen, besteht darin, dass Ladungen in einem Stromkreis geerdet sind und somit wegfließen und eine kleine Menge Energie mitnehmen, wenn sie ihren Zustand ändern. Ein reversibles Gate bewegt nur die Zustände, und da keine Informationen verloren gehen, wird Energie gespart.[citation needed]

Neuere Motivation kommt vom Quantencomputer. Für die Quantenmechanik müssen die Transformationen reversibel sein[citation needed] und erlaubt allgemeinere Berechnungszustände als klassische Computer (Überlagerungen).

after-content-x4

Universalität und Toffoli-Tor[edit]

Jedes reversible Gate, das seine Eingänge verbraucht und alle Eingangsberechnungen zulässt, darf nach dem Pigeonhole-Prinzip nicht mehr Eingangsbits als Ausgangsbits haben. Für ein Eingangsbit gibt es zwei mögliche umkehrbare Gatter. Einer von ihnen ist NICHT. Das andere ist das Identitätsgatter, das seinen Eingang unverändert dem Ausgang zuordnet. Für zwei Eingangsbits ist das einzige nicht triviale Gatter das gesteuerte NICHT-Gatter, das das erste Bit zum zweiten Bit XOR-verknüpft und das erste Bit unverändert lässt.

Wahrheitstabelle Permutationsmatrixform
EINGANG AUSGABE
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

[1000010000010010]{ displaystyle { begin {bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \ end {bmatrix}}}

Leider gibt es reversible Funktionen, die nicht nur mit diesen Gates berechnet werden können. Mit anderen Worten, die Menge, die aus NOT- und XOR-Gattern besteht, ist nicht universell. Wenn wir eine beliebige Funktion mit reversiblen Gates berechnen wollen, brauchen wir ein anderes Gate. Eine Möglichkeit ist die Toffoli-Tor, 1980 von Toffoli vorgeschlagen.[2]

Dieses Gate verfügt über 3-Bit-Ein- und Ausgänge. Wenn die ersten beiden Bits gesetzt sind, wird das dritte Bit umgedreht. Das Folgende ist eine Tabelle der Eingabe- und Ausgabebits:

Wahrheitstabelle Permutationsmatrixform
EINGANG AUSGABE
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

[1000000001000000001000000001000000001000000001000000000100000010]{ Display { begin {bmatrix} 1 0 0 0 0 0 0 0 \ 0 & 1 & 0 0 0 0 0 0 \ 0 0 & 1 & 0 0 0 0 0 \ 0 0 0 1 0 0 0 0 \ 0 0 0 0 1 0 0 0 \ 0 0 0 0 0 1 0 0 \ 0 0 0 0 0 0 0 1 \ 0 0 0 0 0 0 1 0 \ end {bmatrix}}}

Es kann auch als Abbildung der Bits {a, b, c} auf {a, b, c XOR (a UND b)} beschrieben werden.

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

Verwandte Logikgatter[edit]

Das Toffoli-Gate kann aus Single-Qubit-Gates und mindestens sechs CNOTs aufgebaut werden.
  • Das Fredkin-Gatter ist ein universelles reversibles 3-Bit-Gatter, das die letzten beiden Bits vertauscht, wenn das erste Bit 1 ist. eine kontrollierte Swap-Operation.
  • Das n-bit Toffoli Gate ist eine Verallgemeinerung des Toffoli Gates. Es braucht n Bits x1, x2, …, xn als Ein- und Ausgänge n Bits. Der Erste n−1 Ausgangsbits sind gerade x1, …, xn−1. Das letzte Ausgabebit ist (x1 UND UND xn−1) XOR xn.
  • Das Toffoli-Gate kann durch fünf Zwei-Qubit-Quantentore realisiert werden.[3] Tatsächlich sind mindestens fünf Zwei-Qubit-Quantentore erforderlich, um das Toffoli-Gatter zu implementieren.[4]
  • Ein verwandtes Quantentor, das Deutsch-Gatter, kann durch fünf optische Impulse mit neutralen Atomen realisiert werden.[5] Das Deutsch-Gate ist ein universelles Gate für das Quantencomputing.[6]

Beziehung zum Quantencomputer[edit]

Jedes reversible Gate kann auf einem Quantencomputer implementiert werden, und daher ist das Toffoli-Gate auch ein Quantenoperator. Das Toffoli-Gate kann jedoch nicht für universelle Quantenberechnungen verwendet werden, obwohl dies bedeutet, dass ein Quantencomputer alle möglichen klassischen Berechnungen implementieren kann. Das Toffoli-Gatter muss zusammen mit einigen inhärenten Quantengattern implementiert werden, um für die Quantenberechnung universell zu sein. Tatsächlich reicht jedes Single-Qubit-Gate mit reellen Koeffizienten aus, das einen nichttrivialen Quantenzustand erzeugen kann.[7]

Ein auf Quantenmechanik basierendes Toffoli-Gate wurde im Januar 2009 an der Universität Innsbruck erfolgreich realisiert.[8] Während die Implementierung von n-Qubit Toffoli mit Schaltungsmodell 2n C-NOT-Gatter erfordert,[9] Die Anwendung der Vielkörper-Wechselwirkung könnte für den direkten Betrieb des Gates in Rydberg-Atomen und für die Implementierung supraleitender Schaltungen verwendet werden.[10][11][12]

Siehe auch[edit]

Verweise[edit]

  1. ^ Landauer, R. (Juli 1961). “Irreversibilität und Wärmeerzeugung im Rechenprozess”. IBM Journal für Forschung und Entwicklung. 5 (3): 183–191. doi:10.1147 / rd.53.0183. ISSN 0018-8646.
  2. ^ Technischer Bericht MIT / LCS / TM-151 (1980) und eine angepasste und komprimierte Version: Toffoli, Tommaso (1980). JW de Bakker und J. van Leeuwen (Hrsg.). Reversibles Rechnen (PDF). Automaten, Sprachen und Programmierung, Siebtes Kolloquium. Noordwijkerhout, Niederlande: Springer Verlag. S. 632–644. doi:10.1007 / 3-540-10003-2_104. ISBN 3-540-10003-2. Archiviert von das Original (PDF) am 15.04.2010.
  3. ^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (November 1995). “Elementare Gates für die Quantenberechnung”. Körperliche Überprüfung A.. American Physical Society. 52 (5): 3457–3467. arXiv:quant-ph / 9503016. Bibcode:1995PhRvA..52.3457B. doi:10.1103 / PhysRevA.52.3457. PMID 9912645. S2CID 8764584.
  4. ^ Yu, Nengkun; Duan, Runyao; Ying, Mingsheng (30.07.2013). “Für die Implementierung des Toffoli-Gates sind fünf Zwei-Qubit-Gates erforderlich.” Körperliche Überprüfung A.. 88 (1): 010304. arXiv:1301.3372. Bibcode:2013PhRvA..88a0304Y. doi:10.1103 / physreva.88.010304. ISSN 1050-2947. S2CID 55486826.
  5. ^ Shi, Xiao-Feng (Mai 2018). “Deutsch, Toffoli und CNOT Gates über Rydberg Blockade neutraler Atome”. Körperliche Überprüfung angewendet. 9 (5): 051001. arXiv:1710.01859. Bibcode:2018PhRvP … 9e1001S. doi:10.1103 / PhysRevApplied.9.051001. S2CID 118909059.
  6. ^ Deutsch, D. (1989). “Quantum Computational Networks”. Verfahren der Royal Society of London. Reihe A, Mathematik und Physik. 425 (1868): 73–90. Bibcode:1989RSPSA.425 … 73D. doi:10.1098 / rspa.1989.0099. ISSN 0080-4630. JSTOR 2398494. S2CID 123073680.
  7. ^ Shi, Yaoyun (Januar 2003). “Sowohl Toffoli als auch Controlled-NOT benötigen wenig Hilfe für die universelle Quantenberechnung.” Quanteninformation & Berechnung. 3 (1): 84–92. arXiv:quant-ph / 0205115. Bibcode:2002quant.ph..5115S.
  8. ^ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, AS; Schindler, P.; Chwalla, M.; Hennrich, M.; Blatt, R. (Januar 2009). “Realisierung des Quantentoffoli-Tors mit gefangenen Ionen”. Briefe zur körperlichen Überprüfung. American Physical Society. 102 (4): 040501. arXiv:0804.0082. Bibcode:2009PhRvL.102d0501M. doi:10.1103 / PhysRevLett.102.040501. PMID 19257408. S2CID 2051775.
  9. ^ Shende, Vivek V.; Markov, Igor L. (15.03.2008). “Über die CNOT-Kosten von TOFFOLI-Toren”. arXiv:0803.2316 [quant-ph].
  10. ^ Khazali, Mohammadsadegh; Mølmer, Klaus (11.06.2020). “Schnelle Multiqubit-Gates durch adiabatische Evolution in wechselwirkenden Verteilern von Rydberg-Atomen und supraleitenden Schaltkreisen im angeregten Zustand”. Körperliche Überprüfung X.. 10 (2): 021054. Bibcode:2020PhRvX..10b1054K. doi:10.1103 / PhysRevX.10.021054. ISSN 2160-3308.
  11. ^ Isenhower, L.; Saffman, M.; Mølmer, K. (04.09.2011). “Multibit-CkNOT-Quantentore über Rydberg-Blockade”. Quanteninformationsverarbeitung. 10 (6): 755. arXiv:1104.3916. doi:10.1007 / s11128-011-0292-4. ISSN 1573-1332. S2CID 28732092.
  12. ^ Rasmussen, SE; Groenland, K.; Gerritsma, R.; Schoutens, K.; Zinner, NT (07.02.2020). “Einstufige Implementierung von High-Fidelity-n-Bit-Toffoli-Gates”. Körperliche Überprüfung A.. 101 (2): 022308. arXiv:1910.07548. Bibcode:2020PhRvA.101b2308R. doi:10.1103 / physreva.101.022308. ISSN 2469-9926. S2CID 204744044.

Externe Links[edit]

after-content-x4