Puerta lógica reversible universal, aplicada en computación cuántica
En los circuitos lógicos , la puerta de Toffoli (también puerta CCNOT ), inventada por Tommaso Toffoli , es una puerta lógica reversible universal , lo que significa que cualquier circuito reversible clásico puede construirse a partir de puertas de Toffoli. También se la conoce como puerta "controlado-controlado-no", que describe su acción. Dispone de entradas y salidas de 3 bits; si los dos primeros bits están configurados en 1, se 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 única x . La puerta L es reversible si hay una puerta L ´( y ) = x que asigna y a x , para todo y . Desde las puertas lógicas comunes, NOT es reversible, como se puede ver en la siguiente tabla de verdad:
La puerta AND común no es reversible porque las entradas 00, 01 y 10 están asignadas a la salida 0.
Las puertas reversibles se estudian desde los años 60. La motivación original fue que las puertas reversibles disipan menos calor (o, en principio, nada de calor). [1]
La motivación más reciente proviene de la computación cuántica . En mecánica cuántica el estado cuántico puede evolucionar de dos maneras: mediante la ecuación de Schrödinger ( transformaciones unitarias ), o mediante su colapso . Las operaciones lógicas para computadoras cuánticas, de las cuales la puerta de Toffoli es un ejemplo, son transformaciones unitarias y, por lo tanto, evolucionan de manera reversible. [2]
La universalidad y la puerta de 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 del 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 (en adelante CNOT), que aplica XOR del primer bit al segundo bit y deja el primer bit sin cambios.
Desafortunadamente, hay funciones reversibles que no se pueden calcular usando sólo esas puertas. En otras palabras, el conjunto formado por las puertas NOT y XOR no es universal . Para calcular una función arbitraria utilizando puertas reversibles, se necesita otra puerta. Una posibilidad es la puerta de Toffoli , propuesta en 1980 por Toffoli. [3]
Esta puerta tiene entradas y salidas de 3 bits. Si los dos primeros bits están configurados, invierte el tercer bit. La siguiente es una tabla de los bits de entrada y salida:
También se puede describir como asignar bits { a , b , c } a { a , b , c XOR ( a AND b )}. Esto también puede entenderse como una operación de módulo en el bit c : { a , b , c } → { a , b , ( c + ab ) mod 2}, a menudo escrito como { a , b , c } → { a , b , c ⨁ ab } [4]
La puerta 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 de Toffoli que toma x 1 , x 2 , ..., x m y algunos bits adicionales 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). Una puerta NOT, por ejemplo, se puede construir a partir de una puerta Toffoli estableciendo los tres bits de entrada en { a , 1, 1}, haciendo que el tercer bit de salida (1 XOR ( a AND 1)) = NOT a ; ( a AND b ) es el tercer bit de salida de { a , b , 0}. Básicamente, esto significa que se pueden utilizar puertas de Toffoli para construir sistemas que realicen cualquier cálculo de función booleana deseada de forma reversible.
Puertas lógicas relacionadas
La puerta Toffoli se puede construir a partir de puertas T y Hadamard de un solo qubit , y un mínimo de seis CNOT .
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 de Toffoli de n bits es una generalización de la puerta de 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 puede realizarse mediante cinco puertas cuánticas de dos qubits , [5] pero se puede demostrar que no es posible utilizar menos de cinco. [6]
Una puerta cuántica relacionada, la puerta Deutsch , se puede realizar mediante cinco pulsos ópticos con átomos neutros. [7] La puerta Deutsch es una puerta universal para la computación cuántica. [8]
La puerta de Margolus (llamada así por Norman Margolus ), también llamada Toffoli simplificada, es una puerta de lógica cuántica muy similar a una puerta de Toffoli pero con un −1 en la diagonal: RCCX = diag(1, 1, 1, 1, 1, −1 , X ). La puerta Margolus también es universal para circuitos reversibles y actúa de manera muy similar a una puerta Toffoli, con la ventaja de que puede construirse con aproximadamente la mitad de CNOT en comparación con la puerta Toffoli. [9]
La puerta iToffoli se implementó en qubits superconductores con acoplamiento por pares mediante la aplicación simultánea de operaciones sin conmutación. [10]
Relación con la computación cuántica
Cualquier puerta reversible puede implementarse en una computadora cuántica y, por tanto, la puerta de Toffoli es también 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, cualquier puerta de un solo qubit con coeficientes reales que pueda crear un estado cuántico no trivial es suficiente. [11] En enero de 2009 se realizó con éxito
una puerta de Toffoli basada en la mecánica cuántica en la Universidad de Innsbruck, Austria. [12] Si bien la implementación de un n -qubit Toffoli con modelo de circuito requiere 2 n puertas CNOT, [13] el límite superior más conocido se sitúa en 6 n − 12 puertas CNOT. [14] Se ha sugerido que las computadoras Ion Quantum atrapadas pueden implementar una puerta Toffoli de n -qubit directamente. [15] La aplicación de la interacción de muchos cuerpos podría usarse para la operación directa de la puerta en iones atrapados, átomos de Rydberg e implementaciones de circuitos superconductores. [16] [17] [18] [19] [20] [21] Siguiendo la variedad de estado oscuro, la puerta Khazali-Mølmer C n -NOT [17] opera con solo tres pulsos, apartándose del paradigma del modelo de circuito. La puerta iToffoli se implementó en un solo paso utilizando tres qubits superconductores con acoplamiento por pares. [22]
^ Landauer, R. (julio de 1961). "Irreversibilidad y generación de calor en el proceso informático". Revista IBM de investigación y desarrollo . 5 (3): 183-191. doi :10.1147/rd.53.0183. ISSN 0018-8646.
^ Colin P. Williams (2011). Exploraciones en Computación Cuántica . Saltador . págs. 25-29, 61. ISBN978-1-84628-887-6.
^ Informe técnico MIT/LCS/TM-151 (1980) y 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, Países Bajos: 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.
^ Nielsen, Michael L.; Chuang, Isaac L. (2010). Computación cuántica e información cuántica (10ª ed.). Prensa de la Universidad de Cambridge. pag. 29.ISBN9781107002173.
^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, normando; Corto, Peter ; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (noviembre de 1995). "Puertas elementales para la computación cuántica". Revisión física A. 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 qubits para implementar la puerta Toffoli". Revisión física A. 88 (1): 010304. arXiv : 1301.3372 . Código Bib : 2013PhRvA..88a0304Y. doi :10.1103/physreva.88.010304. ISSN 1050-2947. S2CID 55486826.
^ Shi, Xiao-Feng (mayo de 2018). "Puertas Deutsch, Toffoli y CNOT a través del bloqueo de átomos neutrales de Rydberg". Revisión Física Aplicada . 9 (5): 051001. arXiv : 1710.01859 . Código Bib : 2018PhRvP...9e1001S. doi : 10.1103/PhysRevApplied.9.051001. S2CID 118909059.
^ Alemán, D. (1989). "Redes computacionales cuánticas". Actas de la Royal Society de Londres. Serie A, Ciencias Matemáticas y Físicas . 425 (1868): 73–90. Código Bib : 1989RSPSA.425...73D. doi :10.1098/rspa.1989.0099. ISSN 0080-4630. JSTOR 2398494. S2CID 123073680.
^ Máslov, Dmitri (10 de febrero de 2016). "Ventajas del uso de puertas Toffoli de fase relativa con una aplicación para la optimización de Toffoli de control múltiple". Revisión física A. 93 (2): 022311. arXiv : 1508.03273 . Código Bib : 2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311 . ISSN 2469-9926.
^ Kim, Y.; Morvan, A.; Nguyen, LB; Naik, RK; Jünger, C.; Chen, L.; Kreikebaum, JM; Santiago, DI; Siddiqi, I. (2 de mayo de 2022). "Puerta iToffoli de tres qubits de alta fidelidad para qubits superconductores de frecuencia fija". Física de la Naturaleza . 18 (5): 783–788. arXiv : 2108.10288 . Código Bib : 2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .
^ Shi, Yaoyun (enero de 2003). "Tanto Toffoli como Controlled-NOT necesitan poca ayuda para realizar cálculos cuánticos universales". Información y computación cuánticas . 3 (1): 84–92. arXiv : quant-ph/0205115 . Código Bib : 2002quant.ph..5115S. doi :10.26421/QIC3.1-7.
^ 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 . 102 (4): 040501. arXiv : 0804.0082 . Código bibliográfico : 2009PhRvL.102d0501M. doi : 10.1103/PhysRevLett.102.040501. PMID 19257408. S2CID 2051775.
^ Shende, Vivek V.; Markov, Igor L. (15 de marzo de 2008). "Sobre el coste CNOT de las puertas TOFFOLI". arXiv : 0803.2316 [cuántico-ph].
^ Máslov, Dmitri (2016). "Ventajas del uso de puertas Toffoli de fase relativa con una aplicación para la optimización de Toffoli de control múltiple". Revisión física A. 93 (2): 022311. arXiv : 1508.03273 . Código Bib : 2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311. S2CID 5226873.
^ Katz, o; Cetina, Marko; Monroe, Christopher (8 de febrero de 2022). " -Interacciones corporales entre Qubits de iones atrapados mediante compresión dependiente del giro". Cartas de revisión física . 129 (6): 063603. arXiv : 2202.04230 . doi : 10.1103/PhysRevLett.129.063603. PMID 36018637. S2CID 246679905.
^ Arias Espinoza, Juan Diego; Groenlandia, Koen; Mazzanti, Matteo; Schoutens, Kareljan; Gerritsma, René (28 de mayo de 2021). "Método de alta fidelidad para una puerta Toffoli de N bits de un solo paso en iones atrapados". Revisión física A. 103 (5): 052437. arXiv : 2010.08490 . Código bibliográfico : 2021PhRvA.103e2437E. doi :10.1103/PhysRevA.103.052437. S2CID 223953418.
^ ab Khazali, Mohammadsadegh; Mølmer, Klaus (11 de junio de 2020). "Puertas rápidas multiqubit por evolución adiabática en colectores de estado excitado interactivos de átomos de Rydberg y circuitos superconductores". Revisión física X. 10 (2): 021054. arXiv : 2006.07035 . Código Bib : 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 mediante 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 en un solo paso de puertas Toffoli de n bits de alta fidelidad". Revisión física A. 101 (2): 022308. arXiv : 1910.07548 . Código Bib : 2020PhRvA.101b2308R. doi :10.1103/physreva.101.022308. ISSN 2469-9926. S2CID 204744044.
^ Nguyen, LB; Kim, Y.; Hashim, A.; Goss, N.; Marinelli, B.; Bhandari, B.; Das, D.; Naik, RK; Kreikebaum, JM; Jordán, A.; Santiago, DI; Siddiqi, I. (16 de enero de 2024). "Interacciones programables de Heisenberg entre qubits de Floquet". Física de la Naturaleza . 20 (1): 240–246. arXiv : 2211.10383 . Código Bib : 2024NatPh..20..240N. doi : 10.1038/s41567-023-02326-7 .
^ Nguyen, largo B.; Goss, Noé; Siva, Karthik; Kim, Yosep; Younis, Ed; Qing, Bingcheng; Hashim, Akel; Santiago, David I.; Siddiqi, Irfan (29 de diciembre de 2023). "Potenciar la computación cuántica de alta dimensión atravesando la escalera bosónica dual". arXiv.org . Consultado el 8 de abril de 2024 .
^ Kim, Y.; Morvan, A.; Nguyen, LB; Naik, RK; Jünger, C.; Chen, L.; Kreikebaum, JM; Santiago, DI; Siddiqi, I. (2 de mayo de 2022). "Puerta iToffoli de tres qubits de alta fidelidad para qubits superconductores de frecuencia fija". Física de la Naturaleza . 18 (5): 783–788. arXiv : 2108.10288 . Código Bib : 2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .
enlaces externos
CNOT y Toffoli Gates en configuración Multi-Qubit en el Proyecto de Demostraciones Wolfram.
