Toffoli ventil

Brána Toffoli (CCNOT) je univerzální řízená reverzibilní brána se třemi vstupy a výstupy, kterou navrhl Thomas Toffoli v roce 1980 [1] . Bylo prokázáno, že s použitím tohoto hradla samotného lze sestavit jakýkoli reverzibilní logický obvod , jako je aritmetická jednotka nebo procesor. Je to také populární kvantová brána při konstrukci reverzibilních obvodů v kvantových počítačích .

Ventil Toffoli je principiálně podobný CNOT . Má tři vstupy a tři výstupy, pokud jsou první dva vstupy rovny jednomu, pak je hodnota posledního bitu invertována. Jinak jsou všechny vstupy přiváděny na výstup beze změny. Pravdivostní tabulka a matice pro CCNOT vypadá takto:

pravdivostní tabulka Transformační matice
VSTUP VÝSTUP
 0   0   0   0   0   0 
0 0 jeden 0 0 jeden
0 jeden 0 0 jeden 0
0 jeden jeden 0 jeden jeden
jeden 0 0 jeden 0 0
jeden 0 jeden jeden 0 jeden
jeden jeden 0 jeden jeden jeden
jeden jeden jeden jeden jeden 0

Dokažme, že ventil je univerzální. Pokud rozložíme kvantové Toffoliho hradlo na jednoduché booleovské operace, pak můžeme vidět, že první a druhý qubit jsou na vstupu a výstupu vždy stejné a třetí qubit na výstupu má tvar C = C XOR (A AND B) , kde A, B a C jsou vstupy a výstupy ventilů. Je vidět, že hradlo je univerzální, protože provádí jakoukoliv z operací ( NOT , AND , XOR a FANOUT ) v závislosti na vstupních hodnotách.

Existuje další známá univerzální oboustranná třícestná brána - Fredkinova brána , CSWAP [1] .

Poznámky

  1. ↑ 1 2 Technická zpráva MIT/LCS/TM-151 Archivováno 4. ledna 2015 na Wayback Machine (1980) a varianta: Toffoli, Tommaso (1980). JW de Bakker a J. van Leeuwen , ed. Reverzibilní počítání . Automaty, jazyky a programování, 7. kolokvium. Noordwijkerhout, Nizozemsko: Springer Verlag. str. 632–644. DOI : 10.1007/3-540-10003-2_104 . ISBN  3-540-10003-2 . Parametry |author=a |last=vzájemně se duplikují ( nápověda )

Literatura