stringtranslate.com

Puerta de Toffoli

En circuitos lógicos , la compuerta Toffoli , también conocida como compuerta CCNOT (“controlada-controlada-no”), inventada por Tommaso Toffoli , es una compuerta CNOT con dos cúbits de control y un cúbit objetivo. Es decir, el cúbit objetivo (tercer cúbit) se invertirá si el primer y el segundo cúbit son ambos 1. Se trata de una compuerta lógica reversible universal, lo que significa que se puede construir cualquier circuito reversible clásico a partir de compuertas Toffoli.

La tabla de verdad y la matriz son las siguientes:

Fondo

Una puerta lógica que consume entradas L es reversible si cumple las siguientes condiciones: (1) L ( x ) = y es una puerta donde para cualquier salida y , hay una entrada única x ; (2) La puerta L es reversible si hay una puerta L ´( y ) = x que asigna y a x , para todo y .

Un ejemplo de una puerta lógica reversible es una NOT , que puede describirse a partir de su tabla de verdad a continuación:

La puerta AND común no es reversible, porque las entradas 00, 01 y 10 están todas asignadas a la salida 0.

Las puertas reversibles se han estudiado desde la década de 1960. La motivación original fue que las puertas reversibles disipan menos calor (o, en principio, ningún calor). [1]

Una 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: por la ecuación de Schrödinger ( transformaciones unitarias ), o por 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]

Descripción del hardware

La puerta Toffoli clásica se implementa en un lenguaje de descripción de hardware como Verilog:

módulo toffoli_gate ( entrada u1 , entrada u2 , entrada in , salida v1 , salida v2 , salida out ); siempre @( * ) begin v1 = u1 ; v2 = u2 ; out = in ^ u1 && u2 ; end endmodule

Universalidad y puerta Toffoli

Cualquier puerta reversible que consume sus entradas y permite todos los cálculos de entrada no debe tener más bits de entrada que bits de salida, según el principio del palomar . Para un bit de entrada, hay dos puertas reversibles posibles . Una de ellas es NOT. La otra es la puerta 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 (CNOT), que realiza una operación XOR del primer bit al segundo bit y deja el primer bit sin cambios.

Desafortunadamente, hay funciones reversibles que no se pueden calcular utilizando sólo esas puertas. Por ejemplo, AND no se puede lograr con esas puertas. En otras palabras, el conjunto que consiste en puertas NOT y XOR no es universal . Para calcular una función arbitraria utilizando puertas reversibles, la puerta Toffoli, propuesta en 1980 por Toffoli, puede lograr el objetivo. [3] También se puede describir como el mapeo de los bits { a , b , c } a { a , b , c XOR ( a AND b )}. Esto también se puede entender como una operación 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 compuerta Toffoli es universal; esto significa que para cualquier función booleana f ( x 1 , x 2 , ..., x m ), hay un circuito que consta de compuertas Toffoli que toma x 1 , x 2 , ..., x m y algunos bits adicionales establecidos en 0 o 1 para generar x 1 , x 2 , ..., x m , f ( x 1 , x 2 , ..., x m ), y algunos bits adicionales (llamados basura). Una compuerta NOT, por ejemplo, se puede construir a partir de una compuerta 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}. Esencialmente, esto significa que uno puede usar compuertas Toffoli para construir sistemas que realizarán cualquier cálculo de función booleana deseado de manera reversible.

Puertas lógicas relacionadas

La puerta de Fredkin
La puerta Toffoli se puede construir a partir de puertas T y Hadamard de un solo qubit y un mínimo de seis CNOT .

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 Toffoli también es un operador cuántico . Sin embargo, la puerta Toffoli no se puede usar para computación cuántica universal, aunque significa que una computadora cuántica puede implementar todos los cálculos clásicos posibles. La puerta Toffoli tiene que implementarse junto con alguna puerta inherentemente cuántica para ser universal para la computación cuántica. De hecho, cualquier puerta de un solo cúbit con coeficientes reales que pueda crear un estado cuántico no trivial es suficiente. [11] Una puerta Toffoli basada en la mecánica cuántica se realizó con éxito en enero de 2009 en la Universidad de Innsbruck, Austria. [12] Si bien la implementación de un Toffoli de n -cúbits 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] Se ha sugerido que las computadoras cuánticas de iones atrapados pueden implementar una puerta Toffoli de n -cúbits directamente. [15] La aplicación de la interacción de muchos cuerpos podría utilizarse para la operación directa de la compuerta en iones atrapados, átomos de Rydberg e implementaciones de circuitos superconductores. [16] [17] [18] [19] [20] [21] Siguiendo la variedad de estado oscuro, la compuerta C n -NOT de Khazali-Mølmer [17] opera con solo tres pulsos, alejándose del paradigma del modelo de circuito. La compuerta iToffoli se implementó en un solo paso utilizando tres qubits superconductores con acoplamiento por pares. [22]

Véase también

Referencias

  1. ^ Landauer, R. (julio de 1961). "Irreversibilidad y generación de calor en el proceso computacional". Revista IBM de Investigación y Desarrollo . 5 (3): 183–191. doi :10.1147/rd.53.0183. ISSN  0018-8646.
  2. ^ Colin P. Williams (2011). Exploraciones en computación cuántica . Springer . Págs. 25-29, 61. ISBN. 978-1-84628-887-6.
  3. ^ 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) . Automata, Languages ​​and Programming, Séptimo Coloquio. Noordwijkerhout, Países Bajos: Springer Verlag. pp. 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.
  4. ^ Nielsen, Michael L.; Chuang, Isaac L. (2010). Computación cuántica e información cuántica (10.ª ed.). Cambridge University Press. pág. 29. ISBN 9781107002173.
  5. ^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter ; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (noviembre de 1995). "Puertas elementales para computación cuántica". Physical Review 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.
  6. ^ Yu, Nengkun; Duan, Runyao; Ying, Mingsheng (30 de julio de 2013). "Se necesitan cinco puertas de dos cúbits 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.
  7. ^ Shi, Xiao-Feng (mayo de 2018). "Puertas Deutsch, Toffoli y CNOT mediante el bloqueo de Rydberg de átomos neutros". Physical Review Applied . 9 (5): 051001. arXiv : 1710.01859 . Código Bibliográfico :2018PhRvP...9e1001S. doi :10.1103/PhysRevApplied.9.051001. S2CID  118909059.
  8. ^ Deutsch, 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. Bibcode :1989RSPSA.425...73D. doi :10.1098/rspa.1989.0099. ISSN  0080-4630. JSTOR  2398494. S2CID  123073680.
  9. ^ Maslov, Dmitri (10 de febrero de 2016). "Ventajas del uso de puertas Toffoli de fase relativa con una aplicación a la optimización de Toffoli de control múltiple". Physical Review A . 93 (2): 022311. arXiv : 1508.03273 . Bibcode :2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311 . ISSN  2469-9926.
  10. ^ 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 cúbits de alta fidelidad para cúbits superconductores de frecuencia fija". Nature Physics . 18 (5): 783–788. arXiv : 2108.10288 . Código Bibliográfico :2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .
  11. ^ Shi, Yaoyun (enero de 2003). "Tanto Toffoli como Controlled-NOT necesitan poca ayuda para realizar computación cuántica universal". Información y computación cuántica . 3 (1): 84–92. arXiv : quant-ph/0205115 . Código Bibliográfico :2002quant.ph..5115S. doi :10.26421/QIC3.1-7.
  12. ^ 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 Toffoli cuántica con iones atrapados". Physical Review Letters . 102 (4): 040501. arXiv : 0804.0082 . Código Bibliográfico :2009PhRvL.102d0501M. doi :10.1103/PhysRevLett.102.040501. PMID  19257408. S2CID  2051775.
  13. ^ Shende, Vivek V.; Markov, Igor L. (15 de marzo de 2008). "Sobre el coste CNOT de las puertas TOFFOLI". arXiv : 0803.2316 [quant-ph].
  14. ^ Maslov, Dmitri (2016). "Ventajas del uso de puertas Toffoli de fase relativa con una aplicación a la optimización de Toffoli de control múltiple". Physical Review A . 93 (2): 022311. arXiv : 1508.03273 . Bibcode :2016PhRvA..93b2311M. doi :10.1103/PhysRevA.93.022311. S2CID  5226873.
  15. ^ Katz, Or; Cetina, Marko; Monroe, Christopher (8 de febrero de 2022). " Interacciones de cuerpos-cuerpo entre cúbits de iones atrapados mediante compresión dependiente del espín". Physical Review Letters . 129 (6): 063603. arXiv : 2202.04230 . doi :10.1103/PhysRevLett.129.063603. PMID  36018637. S2CID  246679905.
  16. ^ 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.
  17. ^ ab Khazali, Mohammadsadegh; Mølmer, Klaus (11 de junio de 2020). "Puertas multiqubit rápidas por evolución adiabática en variedades de estados excitados en interacción de átomos de Rydberg y circuitos superconductores". Physical Review X . 10 (2): 021054. arXiv : 2006.07035 . Código Bibliográfico :2020PhRvX..10b1054K. doi : 10.1103/PhysRevX.10.021054 . ISSN  2160-3308.
  18. ^ Isenhower, L.; Saffman, M.; Mølmer, K. (4 de septiembre de 2011). "Puertas cuánticas CkNOT multibit 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.
  19. ^ Rasmussen, SE; Groenlandia, K.; Gerritsma, R.; Schoutens, K.; Zinner, NT (7 de febrero de 2020). "Implementación de un solo paso de puertas Toffoli de n bits 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.
  20. ^ Nguyen, LB; Kim, Y.; Hashim, A.; Goss, N.; Marinelli, B.; Bhandari, B.; Das, D.; Naik, RK; Kreikebaum, JM; Jordan, A.; Santiago, DI; Siddiqi, I. (16 de enero de 2024). "Interacciones programables de Heisenberg entre qubits de Floquet". Nature Physics . 20 (1): 240–246. arXiv : 2211.10383 . Código Bibliográfico :2024NatPh..20..240N. doi : 10.1038/s41567-023-02326-7 .
  21. ^ Nguyen, Long B.; Goss, Noah; Siva, Karthik; Kim, Yosep; Younis, Ed; Qing, Bingcheng; Hashim, Akel; Santiago, David I.; Siddiqi, Irfan (29 de diciembre de 2023). "Potenciando la computación cuántica de alta dimensión recorriendo la escalera bosónica dual". arXiv.org . Consultado el 8 de abril de 2024 .
  22. ^ 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 cúbits de alta fidelidad para cúbits superconductores de frecuencia fija". Nature Physics . 18 (5): 783–788. arXiv : 2108.10288 . Código Bibliográfico :2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .

Enlaces externos