Porta Toffoli

In informatica , il cancello di Toffoli è un cancello logico . È reversibile e universale, il che significa che qualsiasi circuito reversibile può essere costruito dai cancelli Toffoli. Agisce come una porta NOT a doppio controllo, da cui il nome viene anche dato "porta controllata-controllata-non" (CCNOT).

Si deve a Tommaso Toffoli .

Definizione

La porta Toffoli è una porta logica con 3 bit di ingresso e 3 bit di uscita. Se i primi due bit sono uguali a 1, il terzo bit viene invertito, come mostrato nelle seguenti rappresentazioni:

Tabella della verità Matrice di permutazione
INGRESSO USCITA
 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

In altre parole, per tre bit di ingresso a, b, e c otteniamo in uscita a, b e (c XOR (a AND b)).

Reversibilità

Definizione

Una porta logica L è reversibile se, per una qualsiasi uscita y , esiste un solo ingresso x tale che L (x) = y . Se una porta L è reversibile, esiste una porta inversa L ' per la quale L' (y) = x . Ad esempio, la porta NOT è reversibile, come mostrato nella sua tabella di verità:

INGRESSO USCITA
0 1
1 0

D'altra parte, la porta AND non è reversibile, gli ingressi 00, 01 e 10 hanno tutti e tre per l'uscita 0.

Importanza

Ci siamo interessati alle porte logiche reversibili negli anni '60 , perché le porte reversibili dissipano meno calore di altre (in linea di principio potrebbero addirittura non dissiparne nessuno). In un gate tradizionale, gli stati di input non sono conservati sistematicamente e generalmente si ottengono meno informazioni in uscita che in ingresso. Questa perdita porta anche a una perdita di energia, sotto forma di calore, secondo il principio dell'entropia in termodinamica. In altre parole, ci vuole energia per consentire la trasformazione dei bit di informazione. Un gate reversibile cambia solo lo stato dei bit senza perdita di informazioni, quindi l'energia viene conservata.

Più recentemente, l'interesse è venuto dal calcolo quantistico. La fisica quantistica richiede l'uso di trasformazioni reversibili, ma in cambio consente di lavorare con stati più grandi per eseguire calcoli utilizzando il principio di sovrapposizione . Le porte reversibili formano un sottoinsieme delle porte consentite dal calcolo quantistico .

Universalità e Porta di Toffoli

Secondo il principio del cassetto , qualsiasi porta reversibile deve avere lo stesso numero di bit di ingresso e di uscita.

Tabella della verità Matrice di permutazione
INGRESSO PRODUZIONE
 0   0   0   0 
0 1 0 1
1 0 1 1
1 1 1 0

Sfortunatamente, ci sono funzioni reversibili che non possono essere realizzate utilizzando solo queste porte. In altre parole, l'insieme di porte composto da NOT e XOR non è universale (vedi insieme funzionale ). Se vogliamo svolgere qualsiasi funzione utilizzando porte reversibili, abbiamo bisogno di un'altra porta. Il cancello Toffoli, proposto nel 1980 da Tommaso Toffoli , è una soluzione.

La porta di Toffoli è universale, il che significa che qualunque sia la funzione booleana f ( x 1 , x 2 , ..., x m ), esiste un circuito costituito dalle porte di Toffoli che

Possiamo quindi costruire con Toffoli sistemi di porte che eseguiranno qualsiasi funzione booleana in modo reversibile.

Collegamenti al calcolo quantistico

Qualsiasi gate reversibile può essere impiantato su un computer quantistico . La porta di Toffoli è quindi anche un operatore quantistico. Ma non è un operatore quantistico universale, anche se è vero che il computer quantistico può eseguire tutti i calcoli classici

È stato realizzato un cancello Toffoli gennaio 2009presso l' Università di Innsbruck in Austria.

Porte simili

Riferimenti

  1. Vedi il principio a cui Rolf Landauer ha dato il suo nome.
  2. ( Barenco et al. 1982 )
  3. ( Toffoli 1980 )
  4. ( Fredkin e Toffoli 1982 )
  5. ( Monz et al. )
  6. Quantum Fredkin Gate
  7. ( Barenco et al.1995 )
  8. Vedi in: Billiard-ball computer nella Wikipedia in inglese.

Bibliografia

Vedi anche