Toffoli brána - Toffoli gate

Reprezentace obvodu brány Toffoli

v logické obvody, Toffoli brána (taky Brána CCNOT), vynalezl Tommaso Toffoli, je univerzální reverzibilní logická brána, což znamená, že z vrat Toffoli lze postavit jakýkoli reverzibilní obvod. Je také známá jako brána „řízeno-řízeno-ne“, která popisuje jeho činnost. Má 3-bitové vstupy a výstupy; pokud jsou první dva bity nastaveny na 1, invertuje se třetí bit, jinak zůstanou všechny bity stejné.

Pozadí

Náročné na vstupy logická brána L je reverzibilní, pokud pro jakýkoli výstup y, existuje jedinečný vstup X takové, které platí L(X) = y. Pokud brána L je reverzibilní, je zde inverzní brána L′, Který mapuje y na X pro který L′(y) = X. Ze společných logických bran je NOT reverzibilní, jak je vidět z níže uvedené tabulky pravdivosti.

VSTUPVÝSTUP
01
10

Společná brána AND však není reverzibilní. Všechny vstupy 00, 01 a 10 jsou mapovány na výstup 0.

Reverzibilní brány byly studovány od 60. let. Původní motivací bylo, že vratné brány odvádějí méně tepla (nebo v zásadě žádné teplo).[1] Pokud si myslíme, že logická brána spotřebovává svůj vstup, dojde ke ztrátě informací, protože na výstupu je přítomno méně informací, než bylo přítomno na vstupu. Tato ztráta informací ztrácí energii do okolní oblasti jako teplo termodynamická entropie.[Citace je zapotřebí ] Další způsob, jak to pochopit, je to, že náboje v obvodu jsou uzemněny, a tak odtekají, přičemž při změně stavu s sebou berou malé množství energie. Reverzibilní brána pohybuje pouze stavy kolem a protože se neztrácejí žádné informace, energie se šetří.[Citace je zapotřebí ]

Novější motivace pochází z kvantové výpočty. Kvantová mechanika vyžaduje, aby transformace byly reverzibilní[Citace je zapotřebí ] a umožňuje obecnější stavy výpočtu než klasické počítače (superpozice ).

Univerzálnost a brána Toffoli

Jakákoli vratná brána, která spotřebovává své vstupy a umožňuje všechny vstupní výpočty, nesmí mít více vstupních bitů než výstupních bitů princip pigeonhole. Pro jeden vstupní bit jsou možné dva reverzibilní brány. Jeden z nich NENÍ. Druhým je brána identity, která mapuje svůj vstup na výstup beze změny. U dvou vstupních bitů je jedinou netriviální bránou řízená NOT brána, který XOR první bit na druhý bit a ponechá první bit beze změny.

Pravdivá tabulkaPermutační matice formulář
VSTUPVÝSTUP
 0  0  0  0 
0101
1011
1110

Bohužel existují reverzibilní funkce, které nelze vypočítat pomocí těchto bran. Jinými slovy, sada skládající se z bran NOT a XOR není univerzální. Pokud chceme vypočítat libovolnou funkci pomocí vratných bran, potřebujeme další bránu. Jednou z možností je Toffoli brána, navržený v roce 1980 Toffoli.[2]

Tato brána má 3-bitové vstupy a výstupy. Pokud jsou nastaveny první dva bity, převrátí třetí bit. Následuje tabulka vstupních a výstupních bitů:

Pravdivá tabulkaForma permutační matice
VSTUPVÝSTUP
 0  0  0  0  0  0 
001001
010010
011011
100100
101101
110111
111110

Lze jej také popsat jako mapovací bity {a, b, c} na {a, b, c XOR (a AND b)}.

Brána Toffoli je univerzální; to znamená, že pro všechny Booleovská funkce F(X1, X2, ..., Xm), existuje okruh skládající se z bran Toffoli, který trvá X1, X2, ..., Xm a některé další bity nastaveny na 0 nebo 1 na výstupy X1, X2, ..., Xm, F(X1, X2, ..., Xm) a některé další bity (nazývané odpadky). V podstatě to znamená, že lze použít brány Toffoli k vytváření systémů, které budou reverzibilním způsobem provádět libovolný výpočet booleovských funkcí.

Související logické brány

Bránu Toffoli lze postavit z bran single qubit a minimálně šesti CNOT.
  • The Fredkinova brána je univerzální reverzibilní 3bitová brána, která zamění poslední dva bity, pokud je první bit 1; řízená swapová operace.
  • The n-bit Toffoli gate je zobecněním brány Toffoli. Trvá to n bity X1, X2, ..., Xn jako vstupy a výstupy n bity. První n−1 výstupní bity jsou spravedlivé X1, ..., Xn−1. Poslední výstupní bit je (X1 A ... A Xn−1) XOR Xn.
  • Bránu Toffoli lze realizovat pětiqubit kvantové brány.[3] Ve skutečnosti minimálně pět dvou-qubit kvantové brány je nutné implementovat bránu Toffoli.[4]
  • Související kvantová brána, Deutsch brána, lze realizovat pěti optickými impulsy s neutrálními atomy.[5] Deutsch gate je univerzální brána pro kvantové výpočty.[6]

Vztah ke kvantovému výpočtu

Jakoukoli vratnou bránu lze implementovat na a kvantový počítač, a proto je brána Toffoli také kvantový operátor. Bránu Toffoli však nelze použít pro univerzální kvantové výpočty, ačkoli to znamená, že kvantový počítač může implementovat všechny možné klasické výpočty. Brána Toffoli musí být implementována spolu s některými inherentně kvantovými branami, aby byla univerzální pro kvantový výpočet. Ve skutečnosti postačuje jakákoli brána s jedním qubitem se skutečnými koeficienty, která může vytvořit netriviální kvantový stav.[7]Brána Toffoli založená na kvantová mechanika byla úspěšně realizována v lednu 2009 na univerzitě v Innsbrucku v Rakousku.[8] Zatímco implementace n-qubit Toffoli s obvodovým modelem vyžaduje 2n brány C-NOT,[9] aplikace interakce mnoha těl by mohla být použita pro přímý provoz brány v atomech Rydberg a implementace supravodivých obvodů.[10][11][12]

Viz také

Reference

  1. ^ Landauer, R. (červenec 1961). "Nevratnost a tvorba tepla ve výpočetním procesu". IBM Journal of Research and Development. 5 (3): 183–191. doi:10.1147 / kolo 53.0183. ISSN  0018-8646.
  2. ^ Technická zpráva MIT / LCS / TM-151 (1980) a upravená a zhuštěná verze: Toffoli, Tommaso (1980). J. W. de Bakker a J. van Leeuwen (vyd.). Reverzibilní výpočet (PDF). Automaty, jazyky a programování, sedmé kolokvium. Noordwijkerhout, Nizozemsko: Springer Verlag. str. 632–644. doi:10.1007/3-540-10003-2_104. ISBN  3-540-10003-2. Archivovány od originál (PDF) dne 2010-04-15.
  3. ^ Barenco, Adriano; Bennett, Charles H .; Cleve, Richard; DiVincenzo, David P .; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A .; Weinfurter, Harald (listopad 1995). "Základní brány pro kvantový výpočet". Fyzický přehled A. Americká fyzická společnost. 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 (2013-07-30). "K implementaci brány Toffoli je zapotřebí pět dvoubitových bran." Fyzický přehled 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 (květen 2018). „Deutsch, Toffoli a CNOT Gates prostřednictvím Rydbergovy blokády neutrálních atomů“. Byla provedena fyzická kontrola. 9 (5): 051001. arXiv:1710.01859. Bibcode:2018PhRvP ... 9e1001S. doi:10.1103 / PhysRevApplied. 9.051001. S2CID  118909059.
  6. ^ Deutsch, D. (1989). "Kvantové výpočetní sítě". Sborník královské společnosti v Londýně. Řada A, Matematické a fyzikální vědy. 425 (1868): 73–90. Bibcode:1989RSPSA.425 ... 73D. doi:10.1098 / rspa.1989.0099. ISSN  0080-4630. JSTOR  2398494. S2CID  123073680.
  7. ^ Shi, Yaoyun (leden 2003). „Toffoli i Controlled-NOT potřebují malou pomoc při provádění univerzálního kvantového výpočtu“. Kvantové informace a výpočet. 3 (1): 84–92. arXiv:quant-ph / 0205115. Bibcode:2002quant.ph..5115S.
  8. ^ Monz, T .; Kim, K .; Hänsel, W .; Riebe, M .; Villar, A. S .; Schindler, P .; Chwalla, M .; Hennrich, M .; Blatt, R. (leden 2009). "Realizace brány Quantum Toffoli Gate se zachycenými ionty". Dopisy o fyzické kontrole. Americká fyzická společnost. 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. (2008-03-15). "Na náklady CNOT na brány TOFFOLI". arXiv:0803.2316 [kvant. ph ].
  10. ^ Khazali, Mohammadsadegh; Mølmer, Klaus (11.6.2020). „Rychlé multikbitové brány adiabatickou evolucí při interakci rozrušených atomů Rydbergových atomů a supravodivých obvodů ve vzrušeném stavu“. Fyzická kontrola 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 kvantové brány prostřednictvím Rydbergovy blokády“. Zpracování kvantových informací. 10 (6): 755. arXiv:1104.3916. doi:10.1007 / s11128-011-0292-4. ISSN  1573-1332. S2CID  28732092.
  12. ^ Rasmussen, S.E .; Groenland, K .; Gerritsma, R .; Schoutens, K .; Zinner, N. T. (2020-02-07). "Jednostupňová implementace vysoce věrných n -bitových bran Toffoli". Fyzický přehled A. 101 (2): 022308. arXiv:1910.07548. Bibcode:2020PhRvA.101b2308R. doi:10.1103 / physreva.101.022308. ISSN  2469-9926. S2CID  204744044.

externí odkazy