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 dada sobre un conjunto dado de soluciones candidatas (estados candidatos), mediante un proceso que utiliza fluctuaciones cuánticas . El recocido cuántico se utiliza principalmente para problemas donde 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 vidrio de espín o resolver el problema del viajante de comercio . 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 una variante de tiempo imaginario sin coherencia cuántica había sido discutida por AB Finnila, MA Gomez, C. 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, realizando un paralelismo cuántico, de acuerdo con la fuerza dependiente del tiempo del campo transversal, que causa un efecto túnel cuántico entre estados o esencialmente un efecto túnel a través de picos. Si la tasa de cambio del campo transversal es lo suficientemente lenta, el sistema se mantiene cerca del estado fundamental del hamiltoniano instantáneo (ver también computación cuántica adiabática ). [6] Si la tasa de cambio del campo transversal se acelera, el sistema puede abandonar el estado fundamental temporalmente, pero produce una mayor probabilidad de concluir en el estado fundamental del hamiltoniano del problema final, es decir, computación cuántica diabática . [7] [8] Finalmente, el campo transversal 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 rápido oráculo de Grover para la aceleración de raíz cuadrada en la solució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" desempeña un papel similar a la intensidad del campo de tunelización del recocido cuántico. En el recocido simulado, la temperatura determina la probabilidad de pasar a un estado de "energía" más alta 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 en determinadas condiciones (consulte Heim et al [13] y Yan y Sinitsyn [14] para obtener un modelo totalmente solucionable de recocido cuántico para un hamiltoniano objetivo arbitrario y una comparación de diferentes enfoques de cálculo).

Mecánica cuántica: analogía y ventajas

Analogía simple que describe la diferencia entre el recocido simulado y el recocido cuántico.
El recocido cuántico (línea azul) recorre de manera eficiente los paisajes energéticos aprovechando la tunelización cuántica 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 libera el potencial para resolver problemas de optimización masivos que antes se consideraban imposibles.

El campo de efecto túnel es básicamente un término de energía cinética que no conmuta con la parte de energía potencial clásica del vidrio original. Todo el proceso se puede simular en un ordenador mediante 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 del recocido de 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 ( hamiltoniano clásico ). Luego, se debe introducir artificialmente en el hamiltoniano un término adecuado que consista en una o más variables no conmutativas (es decir, variables que tienen un conmutador distinto de cero con las variables del problema matemático original) para que desempeñen el papel del campo de tunelización (parte cinética). Luego, se puede llevar a cabo la simulación con el hamiltoniano cuántico así construido (la función original + la parte no conmutativa) tal como se describió anteriormente. Aquí, existe una opción para seleccionar el término no conmutativo y la eficiencia del recocido puede depender de eso.

Se ha demostrado experimentalmente así como teóricamente, que el recocido cuántico puede superar al recocido térmico (recocido simulado) en ciertos casos, especialmente donde el paisaje de energía potencial (costo) 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 solo de la altura de las barreras, para barreras muy altas, es extremadamente difícil que las fluctuaciones térmicas saquen al sistema de tales mínimos locales. Sin embargo, como argumentaron anteriormente en 1989 Ray, Chakrabarti y Chakrabarti, [1] la probabilidad de tunelización cuántica a través de la misma barrera (considerada de forma aislada) depende no solo de la altura de la barrera, sino también de su ancho y está dada aproximadamente por , donde es el campo de tunelización. [16] Este control adicional a través del ancho , en presencia de tunelización cuántica, 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 de espín -spin, la altura de la barrera se vuelve del orden de . Para un valor constante de uno se vuelve proporcional a para el 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 un ordenador cuántico , estas simulaciones serían mucho más eficientes y exactas que las que se hacen en un ordenador clásico, porque puede realizar la tunelización directamente, en lugar de tener que añadirla a mano. Además, puede ser capaz de hacer esto 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 exactamente solucionables. [19] [20]

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

Implementaciones de D-Wave

Fotografía de un chip construido por D-Wave Systems , montado y conectado por cable en un portamuestras. El procesador de D-Wave One está diseñado para utilizar 128 elementos lógicos superconductores que presentan un acoplamiento controlable y ajustable para realizar operaciones.

En 2011, D-Wave Systems anunció el primer recocedor cuántico comercial en el mercado con el nombre de 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 qubits . [23] El 25 de mayo de 2011, D-Wave anunció que Lockheed Martin Corporation firmó 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 Universidad del Sur de California (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 sin fines de lucro Universities Space Research Association compró una computadora cuántica adiabática de D-Wave Systems con 512 qubits. [25] [26] Hay 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 enfocarse en resolver problemas del mundo real con hardware cuántico. [28] Como la primera compañía dedicada a producir aplicaciones de software para computadoras cuánticas disponibles comercialmente, la rama de investigación y desarrollo de 1QBit se ha centrado en los procesadores de recocido cuántico de D-Wave y ha demostrado 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 aceleración cuántica sobre todas las computadoras clásicas sigue sin respuesta. Un estudio publicado en Science en junio de 2014, descrito como "probablemente el estudio más exhaustivo y preciso que se haya hecho sobre el rendimiento de la máquina D-Wave" [31] y "la comparación más justa hasta ahora", intentó definir y medir la aceleración cuántica. Se propusieron varias definiciones ya que algunas pueden ser inverificables mediante pruebas empíricas, mientras que otras, aunque refutadas, permitirían no obstante la existencia de ventajas de rendimiento. El estudio encontró que el chip D-Wave "no produjo aceleración cuántica" y no descartó la posibilidad en futuras pruebas. [32] Los investigadores, dirigidos por Matthias Troyer en el Instituto Federal Suizo de Tecnología , no encontraron "aceleración cuántica" en todo el rango de sus pruebas, y solo resultados no concluyentes al observar subconjuntos de las pruebas. Su trabajo ilustró "la naturaleza sutil de la cuestión de la aceleración cuántica". Trabajos posteriores [33] han mejorado 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.

Existen muchas preguntas abiertas en relación con la aceleración cuántica. La referencia a ETH en la sección anterior se refiere sólo a una clase de problemas de referencia. Es posible que existan otras clases de problemas en los que se pueda producir una aceleración cuántica. Los investigadores de Google, LANL, USC, Texas A&M y D-Wave están trabajando para encontrar esas clases de problemas. [34]

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

La arquitectura de D-Wave difiere de las computadoras cuánticas tradicionales. No se sabe que sea polinomialmente 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 de colinas. [ cita requerida ] 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 .

"A cross-disciplinary introduction to quantum annealing-based algorithms" [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 del problema max-SAT (maximum satisfactiable problem) y problemas Minimum Multicut, junto con una descripción general de los sistemas de recocido cuántico fabricados por D-Wave Systems. Se informaron algoritmos híbridos cuántico-clásicos para problemas de optimización discreta-continua a gran escala para ilustrar 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". Physical Review B . 39 (16): 11828–11832. Bibcode :1989PhRvB..3911828R. doi :10.1103/PhysRevB.39.11828. PMID  9948016.
  2. ^ Apolloni, 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". Phys. Rev. E . 58 (5): 5355. arXiv : cond-mat/9804280 . Código Bibliográfico :1998PhRvE..58.5355K. doi :10.1103/PhysRevE.58.5355. S2CID  36114913. Archivado desde el original el 11 de agosto de 2013.
  5. ^ Finnila, AB; Gomez, MA; Sebenik, C.; Stenson, C.; Doll, JD (1994). "Recocido cuántico: Un nuevo método para minimizar funciones multidimensionales". Chemical Physics Letters . 219 (5–6): 343–348. arXiv : chem-ph/9404003 . Código Bibliográfico :1994CPL...219..343F. doi :10.1016/0009-2614(94)00117-0. S2CID  97302385.
  6. ^ Farhi, E.; Goldstone, J.; Gutmann, S.; Lapan, J.; Ludgren, A.; Preda, D. (2001). "Un algoritmo de evolución adiabática cuántica aplicado a instancias aleatorias de un problema NP-completo". Science . 292 (5516): 472–5. arXiv : quant-ph/0104129 . Bibcode :2001Sci...292..472F. doi :10.1126/science.1057726. PMID  11313487. S2CID  10132718.
  7. ^ Crosson, Elizabeth; Farhi, Edward; Cedric Yen-Yu Lin; Lin, Han-Hsuan; Shor, Peter (2014). "Diferentes estrategias para la optimización utilizando el algoritmo adiabático cuántico". arXiv : 1401.7320 [quant-ph].
  8. ^ Muthukrishnan, Siddharth; Albash, Tameem; Lidar, Daniel A. (2015). "Cuando lo diabático triunfa sobre lo adiabático en la optimización cuántica". arXiv : 1505.01249 [quant-ph].
  9. ^ Brooke, J.; Bitko, D.; Rosenbaum, TF; Aeppli, G. (1999). "Recocido cuántico de un imán desordenado". Science . 284 (5415): 779–81. arXiv : cond-mat/0105238 . Bibcode :1999Sci...284..779B. doi :10.1126/science.284.5415.779. PMID  10221904. S2CID  37564720.
  10. ^ Sinitsyn, N.; Yan, B. (2023). "Oráculo de Grover protegido topológicamente para el problema de la partición". Physical Review 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". Journal of Mathematical Physics . 49 (12): 125210. arXiv : 0806.1859 . Bibcode :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". Journal of Physics A . 39 (36): R393–R431. Bibcode :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 de espín de Ising". Science . 348 (6231): 215–217. arXiv : 1411.5693 . Bibcode :2015Sci...348..215H. doi : 10.1126/science.aaa4170 . PMID  25765071.
  14. ^ Yan, B.; Sinitsyn, NA (2022). "Solución analítica para recocido cuántico no adiabático a hamiltoniano de espín de Ising arbitrario". Nature Communications . 13 (1): 2212. arXiv : 2110.12354 . Código Bibliográfico :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". Phys. Rev. E . 72 (2): 026701. arXiv : cond-mat/0502167 . Bibcode :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: recocido cuántico y computación". Eur. Phys. J. 224 (1): 17–24. arXiv : 1408.3262 . Código Bibliográfico : 2015EPJST.224...17M. doi : 10.1140/epjst/e2015-02339-y. S2CID  : 118525494.
  18. ^ Das, A.; Chakrabarti, BK (2008). "Annealización cuántica y computación cuántica analógica". Rev. Mod. Phys. 80 (3): 1061–1081. arXiv : 0801.2193 . Código Bibliográfico :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: perspectivas desde la integrabilidad". Physical Review Letters . 121 (19): 190601. arXiv : 1804.00371 . Código Bibliográfico :2018arXiv180400371L. doi :10.1103/PhysRevLett.121.190601. PMID  30468584. S2CID  53594139.
  20. ^ Yan, B.; Sinitsyn, NA (2022). "Solución analítica para recocido cuántico no adiabático a hamiltoniano de espín de Ising arbitrario". Nature Communications . 13 (1): 2212. arXiv : 2110.12354 . Código Bibliográfico :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". Science . 284 (5415): 779–781. arXiv : cond-mat/0105238 . Bibcode :1999Sci...284..779B. doi :10.1126/science.284.5415.779. PMID  10221904. S2CID  37564720.
  22. ^ ab Johnson, MW; Amin, MHS; Gildert, S.; et al. (2011). "Recocido cuántico con espines manufacturados". Nature . 473 (7346): 194–8. Bibcode :2011Natur.473..194J. doi :10.1038/nature10012. PMID  21562559. S2CID  205224761.
  23. ^ "Aprendiendo a programar el D-Wave One". Blog de D-Wave Systems . 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". D-Wave . 2011-05-25. Archivado desde el original el 23 de julio de 2011 . Consultado el 2011-05-30 .
  25. ^ Jones, N. (2013). "Google y la NASA compran una computadora cuántica". Nature News . doi :10.1038/nature.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 [quant-ph].
  27. ^ Boixo, 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 cúbits". Nature Physics . 10 (3): 218–224. arXiv : 1304.4595 . Código Bibliográfico :2014NatPh..10..218B. doi :10.1038/nphys2900. S2CID  8031023.
  28. ^ "D-Wave Systems construye un ecosistema de aplicaciones cuánticas y anuncia asociaciones con DNA-SEQ Alliance y 1QBit". D-Wave Systems . 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). "Entrelazamiento en un procesador de recocido cuántico". Physical Review X . 4 (2): 021041. arXiv : 1401.3500 . Bibcode :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, una controvertida computadora no produce aumento de velocidad». Science . 344 (6190): 1330–1331. Bibcode :2014Sci...344.1330C. doi : 10.1126/science.344.6190.1330 . PMID  24948715.
  33. ^ Amin, Mohammad H. (2015). "Búsqueda de aceleración cuántica en recocidos cuánticos cuasiestáticos". Physical Review A . 92 (5): 052323. arXiv : 1503.04216 . Código Bibliográfico :2015PhRvA..92e2323A. doi :10.1103/PhysRevA.92.052323. S2CID  66770023.
  34. ^ Steiger, Damian; 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.; Dusek, Miloslav; Rarity, 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 triunfar el recocido cuántico?". Blog de investigación . 8 de diciembre de 2015. Consultado el 21 de enero de 2016 .
  36. ^ D-Wave Systems (5 de octubre de 2021). "Hoja de ruta de próxima generación de D-Wave: aportando claridad a la computación cuántica práctica". Medium . Consultado el 12 de noviembre de 2021 .
  37. ^ Venegas-Andraca, Salvador E.; Cruz-Santos, William; McGeoch, Catherine; 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 Bibliográfico :2018ConPh..59..174V. doi :10.1080/00107514.2018.1450720. S2CID  118974781.
  38. ^ Ajagekar, Akshay; Humble, Travis; You, Fengqi (4 de enero de 2020). "Estrategias de soluciones híbridas basadas en computación cuántica para problemas de optimización discreta-continua a gran escala". Computers & Chemical Engineering . 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". Scientific Reports . 13 (1): 3446. Bibcode :2023NatSR..13.3446W. doi :10.1038/s41598-023-30579-y. PMC 9977923 . PMID  36859591. S2CID  257236235. 

Lectura adicional