En los circuitos lógicos , la puerta Toffoli (también puerta CCNOT ), inventada por Tommaso Toffoli , es una puerta lógica universal reversible , lo que significa que cualquier circuito reversible clásico puede construirse a partir de puertas Toffoli. También se conoce como puerta "controlada-controlada-no", que describe su acción. Tiene entradas y salidas de 3 bits; si los dos primeros bits se establecen en 1, invierte el tercer bit; de lo contrario, todos los bits permanecen iguales.
Fondo
Una puerta lógica L que consume entradas es reversible si cumple las siguientes condiciones: L ( x ) = y es una puerta donde para cualquier salida y , hay una entrada x única . La puerta L es reversible si hay una puerta L ′ ( y ) = x que mapea y a x . Desde las puertas lógicas comunes, NOT es reversible, como se puede ver en su tabla de verdad a continuación.
APORTE | PRODUCCIÓN |
---|---|
0 | 1 |
1 | 0 |
Sin embargo, la puerta AND común no es reversible. Las entradas 00, 01 y 10 se asignan todas a la salida 0.
Las puertas reversibles se han estudiado desde la década de 1960. La motivación original era que las puertas reversibles disipan menos calor (o, en principio, nada de calor). [1] Si pensamos que una puerta lógica consume su entrada, la información se pierde porque hay menos información en la salida que en la entrada. Esta pérdida de información pierde energía en el área circundante en forma de calor, debido a la entropía termodinámica . [ cita requerida ] Otra forma de entender esto es que las cargas en un circuito están conectadas a tierra y por lo tanto fluyen, llevándose una pequeña cantidad de energía cuando cambian de estado. Una puerta reversible solo mueve los estados y, dado que no se pierde información, se conserva la energía. [ cita requerida ]
La motivación más reciente proviene de la computación cuántica . La mecánica cuántica requiere que las transformaciones sean reversibles, porque la mecánica cuántica es teoría unitaria y las transformaciones unitarias son invertibles. Además, la mecánica cuántica permite estados de cálculo más generales que las computadoras clásicas ( superposiciones ).
Universalidad y puerta Toffoli
Cualquier puerta reversible que consuma sus entradas y permita todos los cálculos de entrada no debe tener más bits de entrada que bits de salida, según el principio de casillero . Para un bit de entrada, hay dos posibles puertas reversibles . Uno de ellos NO lo es. La otra es la puerta de identidad, que asigna su entrada a la salida sin cambios. Para dos bits de entrada, la única puerta no trivial es la puerta NOT controlada , que aplica XOR del primer bit al segundo bit y deja el primer bit sin cambios.
Mesa de la verdad | Forma de matriz de permutación | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
Desafortunadamente, hay funciones reversibles que no se pueden calcular usando solo esas puertas. En otras palabras, el conjunto que consta de puertas NOT y XOR no es universal . Para calcular una función arbitraria usando puertas reversibles, se necesita otra puerta. Una posibilidad es la puerta Toffoli , propuesta en 1980 por Toffoli. [2]
Esta puerta tiene entradas y salidas de 3 bits. Si se establecen los dos primeros bits, invierte el tercer bit. La siguiente es una tabla de bits de entrada y salida:
Mesa de la verdad | Forma de matriz de permutación | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
También se puede describir como mapeo de bits {a, b, c} a {a, b, c XOR (a AND b)}.
La puerta de Toffoli es universal; esto significa que para cualquier función booleana f ( x 1 , x 2 , ..., x m ), hay un circuito que consta de puertas Toffoli que toma x 1 , x 2 , ..., x my algunos bits extra establecidos a 0 o 1 a las salidas x 1 , x 2 , ..., x m , f ( x 1 , x 2 , ..., x m ), y algunos bits adicionales (llamados basura). Esencialmente, esto significa que se pueden usar puertas Toffoli para construir sistemas que realizarán cualquier cálculo de función booleana deseada de una manera reversible.
Puertas lógicas relacionadas
- La puerta Fredkin es una puerta universal reversible de 3 bits que intercambia los dos últimos bits si el primer bit es 1; una operación de intercambio controlado.
- La puerta Toffoli de n bits es una generalización de la puerta Toffoli. Toma n bits x 1 , x 2 , ..., x n como entradas y salidas n bits. Los primeros n −1 bits de salida son solo x 1 , ..., x n −1 . El último bit de salida es ( x 1 AND ... AND x n −1 ) XOR x n .
- La puerta de Toffoli se puede realizar mediante cinco puertas cuánticas de dos qubits , [3] pero se puede demostrar que no es posible utilizar menos de cinco. [4]
- Una puerta cuántica relacionada, la puerta Deutsch , se puede realizar mediante cinco pulsos ópticos con átomos neutros. [5] La puerta Deutsch es una puerta universal para la computación cuántica. [6]
Relación con la computación cuántica
Cualquier puerta reversible se puede implementar en una computadora cuántica y, por lo tanto, la puerta de Toffoli también es un operador cuántico . Sin embargo, la puerta de Toffoli no se puede utilizar para el cálculo cuántico universal, aunque sí significa que una computadora cuántica puede implementar todos los cálculos clásicos posibles. La puerta de Toffoli debe implementarse junto con algunas puertas inherentemente cuánticas para que sea universal para la computación cuántica. De hecho, es suficiente cualquier puerta de un solo qubit con coeficientes reales que puedan crear un estado cuántico no trivial. [7] Una puerta Toffoli basada en la mecánica cuántica se realizó con éxito en enero de 2009 en la Universidad de Innsbruck, Austria. [8] La aplicación de la interacción de muchos cuerpos podría utilizarse para la operación directa de la puerta en implementaciones de iones atrapados, átomos de Rydberg y circuitos superconductores. [9] [10] [11] [12] Mientras que la implementación de un Toffoli de n- qubit con modelo de circuito requiere 2 n puertas CNOT, [13] el límite superior más conocido se encuentra en 6 n -12 puertas CNOT. [14]
Ver también
Referencias
- ^ Landauer, R. (julio de 1961). "Irreversibilidad y Generación de Calor en el Proceso Informático". Revista de investigación y desarrollo de IBM . 5 (3): 183-191. doi : 10.1147 / rd.53.0183 . ISSN 0018-8646 .
- ^ Informe técnico MIT / LCS / TM-151 (1980) y una versión adaptada y condensada: Toffoli, Tommaso (1980). JW de Bakker y J. van Leeuwen (ed.). Computación reversible (PDF) . Autómatas, Lenguajes y Programación, Séptimo Coloquio. Noordwijkerhout, Holanda: Springer Verlag. págs. 632–644. doi : 10.1007 / 3-540-10003-2_104 . ISBN 3-540-10003-2. Archivado desde el original (PDF) el 15 de abril de 2010.
- ^ Barenco, Adriano; Bennett, Charles H .; Cleve, Richard; DiVincenzo, David P .; Margolus, normando; Shor, Peter ; Sleator, Tycho; Smolin, John A .; Weinfurter, Harald (noviembre de 1995). "Puertas elementales para la computación cuántica". Physical Review A . Sociedad Estadounidense de Física. 52 (5): 3457–3467. arXiv : quant-ph / 9503016 . Código Bibliográfico : 1995PhRvA..52.3457B . doi : 10.1103 / PhysRevA.52.3457 . PMID 9912645 . S2CID 8764584 .
- ^ Yu, Nengkun; Duan, Runyao; Ying, Mingsheng (30 de julio de 2013). "Se necesitan cinco puertas de dos qubit para implementar la puerta Toffoli". Physical Review A . 88 (1): 010304. arXiv : 1301.3372 . Código Bibliográfico : 2013PhRvA..88a0304Y . doi : 10.1103 / physreva.88.010304 . ISSN 1050-2947 . S2CID 55486826 .
- ^ Shi, Xiao-Feng (mayo de 2018). "Deutsch, Toffoli y CNOT Gates a través del bloqueo de Rydberg de átomos neutrales". Revisión física aplicada . 9 (5): 051001. arXiv : 1710.01859 . Código bibliográfico : 2018PhRvP ... 9e1001S . doi : 10.1103 / PhysRevApplied.9.051001 . S2CID 118909059 .
- ^ Deutsch, D. (1989). "Redes computacionales cuánticas". Actas de la Royal Society of London. Serie A, Ciencias Físicas y Matemáticas . 425 (1868): 73–90. Código Bibliográfico : 1989RSPSA.425 ... 73D . doi : 10.1098 / rspa.1989.0099 . ISSN 0080-4630 . JSTOR 2398494 . S2CID 123073680 .
- ^ Shi, Yaoyun (enero de 2003). "Tanto Toffoli como Controlled-NOT necesitan poca ayuda para realizar la computación cuántica universal". Computación e información cuántica . 3 (1): 84–92. arXiv : quant-ph / 0205115 . Código bibliográfico : 2002quant.ph..5115S .
- ^ Monz, T .; Kim, K .; Hänsel, W .; Riebe, M .; Villar, AS; Schindler, P .; Chwalla, M .; Hennrich, M .; Blatt, R. (enero de 2009). "Realización de la puerta cuántica de Toffoli con iones atrapados". Cartas de revisión física . Sociedad Estadounidense de Física. 102 (4): 040501. arXiv : 0804.0082 . Código Bibliográfico : 2009PhRvL.102d0501M . doi : 10.1103 / PhysRevLett.102.040501 . PMID 19257408 . S2CID 2051775 .
- ^ Arias Espinoza, Juan Diego; Groenland, Koen; Mazzanti, Matteo; Schoutens, Kareljan; Gerritsma, Rene (28 de mayo de 2021). "Método de alta fidelidad para una puerta Toffoli de un solo paso $ N $ -bit en iones atrapados" . Physical Review A . 103 (5): 052437. arXiv : 2010.08490 . doi : 10.1103 / PhysRevA.103.052437 . Consultado el 29 de mayo de 2021 .
- ^ Khazali, Mohammadsadegh; Mølmer, Klaus (11 de junio de 2020). "Fast Multiqubit Gates por evolución adiabática en la interacción de colectores de estado excitado de átomos de Rydberg y circuitos superconductores" . Physical Review X . 10 (2): 021054. Código Bibliográfico : 2020PhRvX..10b1054K . doi : 10.1103 / PhysRevX.10.021054 . ISSN 2160-3308 .
- ^ Isenhower, L .; Saffman, M .; Mølmer, K. (4 de septiembre de 2011). "Puertas cuánticas multibit CkNOT a través del bloqueo de Rydberg". Procesamiento de información cuántica . 10 (6): 755. arXiv : 1104.3916 . doi : 10.1007 / s11128-011-0292-4 . ISSN 1573-1332 . S2CID 28732092 .
- ^ Rasmussen, SE; Groenland, K .; Gerritsma, R .; Schoutens, K .; Zinner, NT (7 de febrero de 2020). "Implementación de un solo paso de puertas Toffoli de n-bit de alta fidelidad". Physical Review A . 101 (2): 022308. arXiv : 1910.07548 . Código Bibliográfico : 2020PhRvA.101b2308R . doi : 10.1103 / physreva.101.022308 . ISSN 2469-9926 . S2CID 204744044 .
- ^ Shende, Vivek V .; Markov, Igor L. (15 de marzo de 2008). "Sobre el costo CNOT de las puertas TOFFOLI". arXiv : 0803,2316 [ quant-ph ].
- ^ Maslov, Dmitri (13 de agosto de 2015). Sobre las ventajas de utilizar Toffolis de fase relativa con una aplicación de optimización de control múltiple de Toffoli ”. arXiv : 1508.03273 [ quant-ph ].
enlaces externos
- CNOT y Toffoli Gates en Multi-Qubit en el Proyecto de Demostraciones Wolfram.