Toffoli-venttiili

Toffoli-portti ( CCNOT ) on Thomas Toffolin vuonna 1980 ehdottama universaali ohjattu käännettävä portti , jossa on kolme tuloa ja lähtöä . On todistettu, että pelkästään tätä porttia käyttämällä voidaan rakentaa mikä tahansa palautuva logiikkapiiri , kuten aritmeettinen yksikkö tai prosessori. Se on myös suosittu kvanttiportti käännettävien piirien rakentamisessa kvanttitietokoneissa .

Toffoli-venttiili on periaatteessa samanlainen kuin CNOT . Siinä on kolme tuloa ja kolme lähtöä, jos kaksi ensimmäistä tuloa ovat yhtä suuret kuin yksi, viimeisen bitin arvo käännetään. Muuten kaikki tulot syötetään lähtöön muuttumattomina. CCNOT:n totuustaulukko ja matriisi näyttää tältä:

totuustaulukko Muunna matriisi
INPUT POISTU
 0   0   0   0   0   0 
0 0 yksi 0 0 yksi
0 yksi 0 0 yksi 0
0 yksi yksi 0 yksi yksi
yksi 0 0 yksi 0 0
yksi 0 yksi yksi 0 yksi
yksi yksi 0 yksi yksi yksi
yksi yksi yksi yksi yksi 0

Osoittakaamme, että venttiili on universaali. Jos jaamme kvantti-Toffoli-portin yksinkertaisiksi Boolen operaatioiksi, voimme nähdä, että ensimmäinen ja toinen kubitti ovat aina yhtä suuret tulossa ja lähdössä, ja lähdön kolmas kubitti on muotoa C = C XOR (A JA B) , jossa A, B ja C ovat venttiilien sisään- ja ulostuloaukkoja. Voidaan nähdä, että portti on universaali, koska se suorittaa minkä tahansa toiminnon ( NOT , AND , XOR ja FANOUT ) tuloarvoista riippuen.

On toinenkin tunnettu universaali käännettävä kolmitieportti - Fredkin- portti , CSWAP [1] .

Muistiinpanot

  1. 1 2 Tekninen raportti MIT/LCS/TM-151 Arkistoitu 4. tammikuuta 2015 Wayback Machinessa (1980) ja muunnelmassa: Toffoli, Tommaso (1980). JW de Bakker ja J. van Leeuwen , toim. Käännettävä laskenta . Automaatit, kielet ja ohjelmointi, seitsemäs kollokvio. Noordwijkerhout, Alankomaat: Springer Verlag. s. 632–644. DOI : 10.1007/3-540-10003-2_104 . ISBN  3-540-10003-2 . Parametrit |author=ja |last=toistaa toisiaan ( ohje )

Kirjallisuus