Porta Toffoli
En els circuits lògics, la porta Toffoli (també la porta CCNOT), inventada per Tommaso Toffoli, és una porta lògica reversible universal, el que significa que qualsevol circuit reversible clàssic es pot construir a partir de portes Toffoli. També es coneix com la porta "controlada-no controlada", que descriu la seva acció. Té entrades i sortides de 3 bits; si els dos primers bits es posen a 1, s'inverteix el tercer bit, en cas contrari tots els bits es mantenen iguals.[1]
Una porta lògica L que consumeix entrades és reversible si compleix les condicions següents: L(x)=y és una porta on per a qualsevol sortida y, hi ha una entrada única x. La porta L és reversible si hi ha una porta L′(y)=x que mapeja y a x. A partir de les portes lògiques comunes, NOT és reversible, com es pot veure a la seva taula de veritat a continuació.[2]
| ENTRADA | SORTIDA |
|---|---|
| 0 | 1 |
| 1 | 0 |
La porta AND comuna no és reversible, perquè les entrades 00, 01 i 10 estan totes assignades a la sortida 0. Les portes reversibles s'estudien des dels anys 60. La motivació original era que les portes reversibles dissipaven menys calor (o, en principi, cap calor).[3]
La motivació més recent prové de la computació quàntica. En mecànica quàntica l'estat quàntic pot evolucionar de dues maneres, per l'equació de Schrödinger (transformacions unitàries), o pel seu col·lapse. Les operacions lògiques per a ordinadors quàntics, de les quals la porta Toffoli n'és un exemple, són transformacions unitàries i, per tant, evolucionen de manera reversible.[4]
Qualsevol porta reversible que consumeixi les seves entrades i permeti tots els càlculs d'entrada no ha de tenir més bits d'entrada que bits de sortida, segons el principi d'encasillament. Per a un bit d'entrada, hi ha dues portes reversibles possibles. Un d'ells NO ho és. L'altra és la porta d'identitat, que mapeja la seva entrada a la sortida sense canvis. Per a dos bits d'entrada, l'única porta no trivial és la porta NO controlada, que fa XOR el primer bit al segon bit i deixa el primer bit sense canvis.
|
|||||||||||||||||||||
Referències
[modifica]- ↑ «Toffoli Gate - an overview | ScienceDirect Topics» (en anglès). https://www.sciencedirect.com.+[Consulta: 20 abril 2023].
- ↑ «Toffoli gate | Prefetch» (en anglès). https://prefetch.eu.+[Consulta: 20 abril 2023].
- ↑ Landauer, R. IBM Journal of Research and Development, 5, 3, 7-1961, pàg. 183–191. DOI: 10.1147/rd.53.0183. ISSN: 0018-8646.
- ↑ Colin P. Williams. Explorations in Quantum Computing. Springer, 2011, p. 25–29,61. ISBN 978-1-84628-887-6.