stringtranslate.com

recocido cuántico

El recocido cuántico ( QA ) es un proceso de optimización para encontrar el mínimo global de una función objetivo determinada sobre un conjunto determinado de soluciones candidatas (estados candidatos), mediante un proceso que utiliza fluctuaciones cuánticas . El recocido cuántico se utiliza principalmente para problemas en los que el espacio de búsqueda es discreto ( problemas de optimización combinatoria ) con muchos mínimos locales ; como encontrar [1] el estado fundamental de un vaso giratorio o el problema del viajante . El término "recocido cuántico" fue propuesto por primera vez en 1988 por B. Apolloni, N. Cesa Bianchi y D. De Falco como un algoritmo clásico de inspiración cuántica. [2] [3] Fue formulado en su forma actual por T. Kadowaki y H. Nishimori (ja) en 1998 [4] aunque AB Finnila, MA Gomez, C. habían discutido una variante de tiempo imaginario sin coherencia cuántica. Sebenik y JD Doll en 1994. [5]

El recocido cuántico comienza a partir de una superposición mecánico-cuántica de todos los estados posibles (estados candidatos) con pesos iguales. Luego, el sistema evoluciona siguiendo la ecuación de Schrödinger dependiente del tiempo , una evolución mecánico-cuántica natural de los sistemas físicos. Las amplitudes de todos los estados candidatos siguen cambiando, logrando un paralelismo cuántico, de acuerdo con la fuerza del campo transversal dependiente del tiempo, lo que provoca un túnel cuántico entre estados o esencialmente un túnel a través de picos. Si la tasa de cambio del campo transversal es lo suficientemente lenta, el sistema permanece cerca del estado fundamental del hamiltoniano instantáneo (ver también cálculo cuántico adiabático ). [6] Si se acelera la tasa de cambio del campo transversal, el sistema puede abandonar el estado fundamental temporalmente pero producirá una mayor probabilidad de concluir en el estado fundamental del problema final hamiltoniano , es decir, de computación cuántica diabática . [7] [8] El campo transversal finalmente se apaga y se espera que el sistema haya alcanzado el estado fundamental del modelo clásico de Ising que corresponde a la solución del problema de optimización original. Inmediatamente después de la propuesta teórica inicial se informó sobre una demostración experimental del éxito del recocido cuántico para imanes aleatorios. [9] También se ha demostrado que el recocido cuántico proporciona un oráculo de Grover rápido para acelerar la raíz cuadrada en la resolución de muchos problemas NP completos. [10]

Comparación con el recocido simulado

El recocido cuántico se puede comparar con el recocido simulado , cuyo parámetro de "temperatura" juega un papel similar a la intensidad del campo de tunelización del control de calidad. En el recocido simulado, la temperatura determina la probabilidad de pasar a un estado de mayor "energía" desde un único estado actual. En el recocido cuántico, la intensidad del campo transversal determina la probabilidad mecánico-cuántica de cambiar las amplitudes de todos los estados en paralelo. La evidencia analítica [11] y numérica [12] sugiere que el recocido cuántico supera al recocido simulado bajo ciertas condiciones (consulte [13] para un análisis cuidadoso y [14] para un modelo totalmente solucionable de recocido cuántico con un hamiltoniano objetivo arbitrario y una comparación de diferentes enfoques de cálculo).

Mecánica cuántica: analogía y ventaja.

Analogía simple que describe la diferencia entre recocido simulado y recocido cuántico.
Quantum Annealing (línea azul) atraviesa eficientemente paisajes energéticos aprovechando el túnel cuántico para encontrar el mínimo global. El recocido cuántico ofrece una importante ventaja de rendimiento sobre el recocido simulado (línea magenta), lo que abre el potencial para resolver problemas de optimización masivos que antes se consideraban imposibles.

El campo de túnel es básicamente un término de energía cinética que no conmuta con la parte clásica de energía potencial del vidrio original. Todo el proceso se puede simular en una computadora utilizando Monte Carlo cuántico (u otra técnica estocástica) y así obtener un algoritmo heurístico para encontrar el estado fundamental del vidrio clásico.

En el caso de recocer una función objetivo puramente matemática , se pueden considerar las variables del problema como grados de libertad clásicos y las funciones de costo como la función de energía potencial (Hamiltoniana clásica). Luego, se debe introducir artificialmente en el hamiltoniano un término adecuado que consista en variables no conmutantes (es decir, variables que tienen un conmutador distinto de cero con las variables del problema matemático original) para que desempeñe el papel del campo de túnel (parte cinética). ). Entonces se puede llevar a cabo la simulación con el hamiltoniano cuántico así construido (la función original + la parte no conmutadora) tal como se describe anteriormente. Aquí, existe la opción de seleccionar el término no conmutable y la eficiencia del recocido puede depender de ello.

Se ha demostrado tanto experimental como teóricamente que el recocido cuántico puede superar al recocido térmico (recocido simulado) en ciertos casos, especialmente cuando el paisaje de energía potencial (coste) consiste en barreras muy altas pero delgadas que rodean mínimos locales poco profundos. [15] Dado que las probabilidades de transición térmica (proporcionales a , con la temperatura y la constante de Boltzmann ) dependen únicamente de la altura de las barreras, para barreras muy altas, es extremadamente difícil que las fluctuaciones térmicas saquen el sistema de tales mínimos locales. Sin embargo, como argumentaron anteriormente en 1989 Ray, Chakrabarti y Chakrabarti, [1] la probabilidad de túnel cuántico a través de la misma barrera (considerada de forma aislada) depende no sólo de la altura de la barrera, sino también de su ancho y está dada aproximadamente por , donde está el campo de túneles. [16] Este control adicional a lo ancho , en presencia de túneles cuánticos, puede ser de gran ayuda: si las barreras son lo suficientemente delgadas (es decir ), las fluctuaciones cuánticas seguramente pueden sacar al sistema de los mínimos locales poco profundos. Para un vidrio giratorio, la altura de la barrera es del orden . Para un valor constante de uno se vuelve proporcional al tiempo de recocido (en lugar de proporcional a para el recocido térmico), mientras que puede incluso volverse independiente para los casos en los que disminuye como . [17] [18]

Se especula que en una computadora cuántica , tales simulaciones serían mucho más eficientes y exactas que las realizadas en una computadora clásica, porque puede realizar el túnel directamente, en lugar de tener que agregarlo a mano. Además, es posible que pueda hacerlo sin los estrictos controles de error necesarios para aprovechar el entrelazamiento cuántico utilizado en los algoritmos cuánticos más tradicionales. Alguna confirmación de esto se encuentra en modelos que tienen solución exacta. [19] [20]

Cronología de ideas relacionadas con el recocido cuántico en vasos de espín Ising:

Implementaciones de D-Wave

Fotografía de un chip construido por D-Wave Systems , montado y unido con cables en un portamuestras. El procesador del D-Wave One está diseñado para utilizar 128 elementos lógicos superconductores que exhiben un acoplamiento controlable y sintonizable para realizar operaciones.

En 2011, D-Wave Systems anunció el primer recocido cuántico comercial del mercado con el nombre D-Wave One y publicó un artículo en Nature sobre su rendimiento. [22] La compañía afirma que este sistema utiliza un chipset de procesador de 128 qubit . [23] El 25 de mayo de 2011, D-Wave anunció que Lockheed Martin Corporation celebró un acuerdo para comprar un sistema D-Wave One. [24] El 28 de octubre de 2011, el Instituto de Ciencias de la Información de la USC recibió el D-Wave One de Lockheed.

En mayo de 2013 se anunció que un consorcio formado por Google , NASA Ames y la Asociación Universitaria de Investigación Espacial sin fines de lucro compró una computadora cuántica adiabática de D-Wave Systems con 512 qubits. [25] [26] Ya está disponible un estudio extenso de su desempeño como recocido cuántico, en comparación con algunos algoritmos de recocido clásicos. [27]

En junio de 2014, D-Wave anunció un nuevo ecosistema de aplicaciones cuánticas con la firma de finanzas computacionales 1QB Information Technologies (1QBit) y el grupo de investigación del cáncer DNA-SEQ para centrarse en resolver problemas del mundo real con hardware cuántico. [28] Como la primera empresa dedicada a producir aplicaciones de software para computadoras cuánticas disponibles comercialmente, el brazo de investigación y desarrollo de 1QBit se ha centrado en los procesadores de recocido cuántico de D-Wave y ha demostrado con éxito que estos procesadores son adecuados para resolver aplicaciones del mundo real. [29]

Con las demostraciones de entrelazamiento publicadas, [30] la pregunta de si la máquina D-Wave puede o no demostrar una aceleración cuántica en comparación con todas las computadoras clásicas sigue sin respuesta. Un estudio publicado en Science en junio de 2014, descrito como "probablemente el estudio más completo y preciso que se haya realizado sobre el rendimiento de la máquina D-Wave" [31] y "la comparación más justa hasta ahora", intentó definir y medir la energía cuántica. acelerar. Se propusieron varias definiciones, ya que algunas pueden no ser verificables mediante pruebas empíricas, mientras que otras, aunque refutadas, permitirían la existencia de ventajas de rendimiento. El estudio encontró que el chip D-Wave "no produjo ninguna aceleración cuántica" y no descartó esa posibilidad en futuras pruebas. [32] Los investigadores, dirigidos por Matthias Troyer en el Instituto Federal Suizo de Tecnología , no encontraron "ninguna aceleración cuántica" en todo el rango de sus pruebas, y sólo resultados no concluyentes cuando observaron subconjuntos de las pruebas. Su trabajo ilustró "la naturaleza sutil de la cuestión de la aceleración cuántica". Trabajos posteriores [33] han avanzado en la comprensión de estas métricas de prueba y su dependencia de sistemas equilibrados, perdiendo así cualquier señal de ventaja debido a la dinámica cuántica.

Hay muchas preguntas abiertas sobre la aceleración cuántica. La referencia de ETH en la sección anterior es solo para una clase de problemas de referencia. Potencialmente, puede haber otras clases de problemas en los que podría producirse una aceleración cuántica. Investigadores de Google, LANL, USC, Texas A&M y D-Wave están trabajando para encontrar este tipo de clases de problemas. [34]

En diciembre de 2015, Google anunció que el D-Wave 2X supera tanto al recocido simulado como a Quantum Monte Carlo en hasta un factor de 100.000.000 en un conjunto de problemas de optimización estrictos. [35]

La arquitectura de D-Wave difiere de las computadoras cuánticas tradicionales. No se sabe que sea polinómicamente equivalente a una computadora cuántica universal y, en particular, no puede ejecutar el algoritmo de Shor porque el algoritmo de Shor no es un proceso de escalada. [ cita necesaria ] El algoritmo de Shor requiere una computadora cuántica universal. Durante la conferencia Qubits 2021 celebrada por D-Wave, se anunció [36] que la compañía está desarrollando sus primeras computadoras cuánticas universales, capaces de ejecutar el algoritmo de Shor además de otros algoritmos de modelo de puerta como QAOA y VQE.

"Una introducción interdisciplinaria a los algoritmos basados ​​en recocido cuántico" [37] presenta una introducción a los problemas de optimización combinatoria ( NP-hard ), la estructura general de los algoritmos basados ​​en recocido cuántico y dos ejemplos de este tipo de algoritmos para resolver instancias de los problemas max-SAT y Maximum Multicut, junto con una descripción general de los sistemas de recocido cuántico fabricados por D-Wave Systems. Se informó que los algoritmos híbridos cuánticos-clásicos para problemas de optimización continuos discretos a gran escala ilustran la ventaja cuántica. [38] [39]

Referencias

  1. ^ abc Ray, P.; Chakrabarti, BK; Chakrabarti, A. (1989). "Modelo de Sherrington-Kirkpatrick en un campo transversal: ausencia de ruptura de simetría de réplica debido a fluctuaciones cuánticas". Revisión física B. 39 (16): 11828–11832. Código bibliográfico : 1989PhRvB..3911828R. doi : 10.1103/PhysRevB.39.11828. PMID  9948016.
  2. ^ Apoloni, Bruno; Cesa-Bianchi, Nicolo; De Falco, Diego (julio de 1988). "Una implementación numérica del recocido cuántico". Procesos estocásticos, física y geometría, actas de la conferencia de Ascona-Locarno.
  3. ^ Apoloni, Bruno; Carvalho, María C.; De Falcó, Diego (1989). "Optimización estocástica cuántica". estoc. Proc. Aplica. 33 (2): 233–244. doi : 10.1016/0304-4149(89)90040-9 .
  4. ^ ab Kadowaki, T.; Nishimori, H. (1998). "Recocido cuántico en el modelo transversal de Ising". Física. Rev. E. 58 (5): 5355. arXiv : cond-mat/9804280 . Código Bib : 1998PhRvE..58.5355K. doi : 10.1103/PhysRevE.58.5355. S2CID  36114913. Archivado desde el original el 11 de agosto de 2013.
  5. ^ Finnila, AB; Gómez, MA; Sebenik, C.; Stenson, C.; Muñeca, JD (1994). "Recocido cuántico: un nuevo método para minimizar funciones multidimensionales". Letras de Física Química . 219 (5–6): 343–348. arXiv : chem-ph/9404003 . Código Bib : 1994CPL...219..343F. doi :10.1016/0009-2614(94)00117-0. S2CID  97302385.
  6. ^ Farhi, E.; Goldstone, J.; Gutmann, S.; Lapán, J.; Ludgren, A.; Preda, D. (2001). "Un algoritmo de evolución adiabática cuántica aplicado a instancias aleatorias de un problema NP-completo". Ciencia . 292 (5516): 472–5. arXiv : quant-ph/0104129 . Código bibliográfico : 2001 Ciencia... 292..472F. doi : 10.1126/ciencia.1057726. PMID  11313487. S2CID  10132718.
  7. ^ Crosson, Isabel; Farhi, Eduardo; Cedric Yen-Yu Lin; Lin, Han-Hsuan; Corto, Peter (2014). "Diferentes estrategias de optimización mediante el algoritmo adiabático cuántico". arXiv : 1401.7320 [cuántico-ph].
  8. ^ Muthukrishnan, Siddharth; Albash, Tameem; Lidar, Daniel A. (2015). "Cuando la diabática triunfa sobre la adiabática en la optimización cuántica". arXiv : 1505.01249 [cuántico-ph].
  9. ^ Brooke, J.; Bitko, D.; Rosenbaum, TF; Aeppli, G. (1999). "Recocido cuántico de un imán desordenado". Ciencia . 284 (5415): 779–81. arXiv : cond-mat/0105238 . Código Bib : 1999 Ciencia... 284..779B. doi : 10.1126/ciencia.284.5415.779. PMID  10221904. S2CID  37564720.
  10. ^ Sinitsyn, N.; Yan, B. (2023). "El oráculo de Grover topológicamente protegido para el problema de la partición". Revisión física A. 108 (2): 022412. arXiv : 2304.10488 . Código bibliográfico : 2023PhRvA.108b2412S. doi : 10.1103/PhysRevA.108.022412. S2CID  258236417.
  11. ^ Morita, Satoshi; Nishimori, Hidetoshi (2008). "Fundamento matemático del recocido cuántico". Revista de Física Matemática . 49 (12): 125210. arXiv : 0806.1859 . Código Bib : 2008JMP....49l5210M. doi : 10.1063/1.2995837. S2CID  13992889.
  12. ^ Santoro, Giuseppe E. y Tosatti, Erio (18 de agosto de 2006). "Optimización mediante mecánica cuántica: recocido cuántico mediante evolución adiabática". Revista de Física A. 39 (36): R393–R431. Código Bib : 2006JPhA...39R.393S. doi :10.1088/0305-4470/39/36/R01. S2CID  116931586.
  13. ^ Heim, B.; Rønnow, TF; Isakov, SV; Troyer, M. (2015). "Recocido cuántico versus clásico de vidrios giratorios de Ising". Ciencia . 348 (6231): 215–217. arXiv : 1411.5693 . Código Bib : 2015 Ciencia... 348.. 215H. doi : 10.1126/ciencia.aaa4170 . PMID  25765071.
  14. ^ Yan, B.; Sinitsyn, NA (2022). "Solución analítica para el recocido cuántico no adiabático a un hamiltoniano de espín de Ising arbitrario". Comunicaciones de la naturaleza . 13 (1): 2212. arXiv : 2110.12354 . Código Bib : 2022NatCo..13.2212Y. doi :10.1038/s41467-022-29887-0. PMC 9038765 . PMID  35468917. S2CID  248389790. 
  15. ^ "Máximos y mínimos locales, y máximos y mínimos absolutos". Mathonline .
  16. ^ Das, A.; Chakrabarti, BK y Stinchcombe, RB (2005). "Recocido cuántico en un sistema cinéticamente restringido". Física. Rev. E. 72 (2): 026701. arXiv : cond-mat/0502167 . Código bibliográfico : 2005PhRvE..72b6701D. doi : 10.1103/PhysRevE.72.026701. PMID  16196745. S2CID  16466621. Archivado desde el original el 13 de enero de 2014.
  17. ^ Véase, por ejemplo, Mukherjee, S. y Chakrabarti, BK (2015). "Optimización multivariable: cálculo y recocido cuántico". EUR. Física. J. 224 (1): 17–24. arXiv : 1408.3262 . Código Bib : 2015EPJST.224...17M. doi :10.1140/epjst/e2015-02339-y. S2CID  118525494.
  18. ^ Das, A.; Chakrabarti, BK (2008). "Recocido cuántico y computación cuántica analógica". Mod. Rev. Física. 80 (3): 1061–1081. arXiv : 0801.2193 . Código Bib : 2008RvMP...80.1061D. CiteSeerX 10.1.1.563.9990 . doi :10.1103/RevModPhys.80.1061. S2CID  14255125.  
  19. ^ Li, F.; Chernyak, VY y Sinitsyn, NA (2018). "Recocido cuántico y termalización: conocimientos de la integrabilidad". Cartas de revisión física . 121 (19): 190601. arXiv : 1804.00371 . Código Bib : 2018arXiv180400371L. doi : 10.1103/PhysRevLett.121.190601. PMID  30468584. S2CID  53594139.
  20. ^ Yan, B.; Sinitsyn, NA (2022). "Solución analítica para el recocido cuántico no adiabático a un hamiltoniano de espín de Ising arbitrario". Comunicaciones de la naturaleza . 13 (1): 2212. arXiv : 2110.12354 . Código Bib : 2022NatCo..13.2212Y. doi :10.1038/s41467-022-29887-0. PMC 9038765 . PMID  35468917. S2CID  248389790. 
  21. ^ Brooke, J.; Bitko, D.; Rosenbaum, TF y Aeppli, G. (30 de abril de 1999). "Recocido cuántico de un imán desordenado". Ciencia . 284 (5415): 779–781. arXiv : cond-mat/0105238 . Código Bib : 1999 Ciencia... 284..779B. doi : 10.1126/ciencia.284.5415.779. PMID  10221904. S2CID  37564720.
  22. ^ ab Johnson, MW; Amin, MHS; Gildert, S.; et al. (2011). "Recocido cuántico con espines fabricados". Naturaleza . 473 (7346): 194–8. Código Bib :2011Natur.473..194J. doi : 10.1038/naturaleza10012. PMID  21562559. S2CID  205224761.
  23. ^ "Aprendiendo a programar el D-Wave One". Blog de sistemas D-Wave . Archivado desde el original el 23 de julio de 2011 . Consultado el 11 de mayo de 2011 .
  24. ^ "D-Wave Systems vende su primer sistema de computación cuántica a Lockheed Martin Corporation". Onda D. 25 de mayo de 2011. Archivado desde el original el 23 de julio de 2011 . Consultado el 30 de mayo de 2011 .
  25. ^ Jones, N. (2013). "Google y la NASA adquieren una computadora cuántica". Noticias de la naturaleza . doi :10.1038/naturaleza.2013.12999. S2CID  57405432.
  26. ^ Smelyanskiy, Vadim N.; Rieffel, Eleanor G.; Knysh, Sergey I.; Williams, Colin P.; Johnson, Mark W.; Thom, Murray C.; Macready, William G.; Pudenz, Kristen L. (2012). "Un enfoque de computación cuántica a corto plazo para problemas computacionales difíciles en la exploración espacial". arXiv : 1204.2821 [cuántico-ph].
  27. ^ Boixó, S.; Rønnow, TF; Isakov, SV; Wang, Z.; Wecker, D.; Lidar, DA; Martinis, JM; Troyer, M. (2014). "Evidencia de recocido cuántico con más de cien qubits". Física de la Naturaleza . 10 (3): 218–224. arXiv : 1304.4595 . Código bibliográfico : 2014NatPh..10..218B. doi :10.1038/nphys2900. S2CID  8031023.
  28. ^ "D-Wave Systems crea un ecosistema de aplicaciones cuánticas y anuncia asociaciones con DNA-SEQ Alliance y 1QBit". Sistemas D-Wave . Archivado desde el original el 31 de diciembre de 2019 . Consultado el 22 de junio de 2014 .
  29. ^ "Investigación de 1QBit". 1QBit . Archivado desde el original el 19 de junio de 2014 . Consultado el 22 de junio de 2014 .
  30. ^ Lanting, T.; Przybysz, AJ; Smirnov, A. Yu.; Spedalieri, FM; et al. (29 de mayo de 2014). "Enredo en un procesador de recocido cuántico". Revisión física X. 4 (2): 021041. arXiv : 1401.3500 . Código Bib : 2014PhRvX...4b1041L. doi : 10.1103/PhysRevX.4.021041. S2CID  19235104.
  31. ^ Helmut Katzgraber, citado en (Cho 2014).
  32. ^ Cho, Adrian (20 de junio de 2014). "Cuántica o no, la controvertida computadora no acelera". Ciencia . 344 (6190): 1330–1331. Código Bib : 2014 Ciencia... 344.1330C. doi : 10.1126/ciencia.344.6190.1330 . PMID  24948715.
  33. ^ Amin, Mohammad H. (2015). "Búsqueda de aceleración cuántica en recocedores cuánticos cuasiestáticos". Revisión física A. 92 (5): 052323. arXiv : 1503.04216 . Código Bib : 2015PhRvA..92e2323A. doi :10.1103/PhysRevA.92.052323. S2CID  66770023.
  34. ^ Steiger, Damián; Heim, Bettina; Rønnow, Troels; Troyer, Matthias (22 de octubre de 2015). "Rendimiento del hardware de recocido cuántico". En Huckridge, David A.; Ebert, Reinhard; Gruneisen, Mark T.; Dušek, Miloslav; Rareza, John G. (eds.). Sistemas electroópticos e infrarrojos: tecnología y aplicaciones XII; y Ciencia y Tecnología de la Información Cuántica . vol. 9648. pág. 964816. Código bibliográfico : 2015SPIE.9648E..16S. doi :10.1117/12.2202661. S2CID  57916974.
  35. ^ "¿Cuándo puede ganar Quantum Annealing?". Blog de investigación . 8 de diciembre de 2015 . Consultado el 21 de enero de 2016 .
  36. ^ Sistemas D-Wave (5 de octubre de 2021). "Hoja de ruta de próxima generación de D-Wave: aportar claridad a la computación cuántica práctica". Medio . Consultado el 12 de noviembre de 2021 .
  37. ^ Venegas-Andraca, Salvador E.; Cruz-Santos, William; McGeoch, Catalina; Lanzagorta, Marco (2018). "Una introducción interdisciplinaria a los algoritmos basados ​​en recocido cuántico". Física Contemporánea . 59 (2): 174-196. arXiv : 1803.03372 . Código Bib : 2018ConPh..59..174V. doi :10.1080/00107514.2018.1450720. S2CID  118974781.
  38. ^ Ajagekar, Akshay; Humilde, Travis; Tú, Fengqi (04/01/2020). "Estrategias de soluciones híbridas basadas en computación cuántica para problemas de optimización continua y discreta a gran escala". Informática e Ingeniería Química . 132 : 106630. arXiv : 1910.13045 . doi : 10.1016/j.compchemeng.2019.106630 . ISSN  0098-1354.
  39. ^ Wierzbiński, M.; Falo-Roget, J.; Crimi, A. (2023). "Detección de comunidades en conectomas cerebrales con computación cuántica híbrida". Informes científicos . 13 (1): 3446. Código bibliográfico : 2023NatSR..13.3446W. doi :10.1038/s41598-023-30579-y. PMC 9977923 . PMID  36859591. S2CID  257236235. 

Otras lecturas