El recocido cuántico ( QA ) es una metaheurística 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 (en otras palabras, un metaprocedimiento para encontrar un procedimiento que encuentra un tamaño / longitud / costo / distancia mínimos absolutos dentro de un conjunto posiblemente muy grande, pero no obstante finito, de posibles soluciones utilizando computación basada en fluctuaciones cuánticas en lugar de computación clásica). 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 elestado fundamental de un vaso giratorio [1] o el problema del viajante . El recocido cuántico fue propuesto por primera vez en 1988 por B. Apolloni, N. Cesa Bianchi y D. De Falco. [2] [3] Fue formulado en su forma actual por T. Kadowaki y H. Nishimori ( ja ) en "Recocido cuántico en el modelo transversal de Ising" [4] aunque AB Finnila había hecho una propuesta en una forma diferente. , MA Gomez, C. Sebenik y JD Doll, en "Recocido cuántico: un nuevo método para minimizar las funciones multidimensionales". [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 natural de la mecánica cuántica 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, lo que provoca un túnel cuántico entre estados. 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 dejar el estado fundamental temporalmente pero producir una mayor probabilidad de concluir en el estado fundamental del problema final hamiltoniano, es decir, cálculo cuántico diabático. [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 al problema de optimización original. Una demostración experimental del éxito del recocido cuántico para imanes aleatorios se informó inmediatamente después de la propuesta teórica inicial. [9]
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 efecto túnel de QA. 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 fuerza del campo transversal determina la probabilidad mecánica cuántica de cambiar las amplitudes de todos los estados en paralelo. La evidencia analítica [10] y numérica [11] sugiere que el recocido cuántico supera al recocido simulado bajo ciertas condiciones (ver [12] para un análisis cuidadoso).
Mecánica cuántica: analogía y ventaja
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 una computadora utilizando el 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 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). Entonces, un término adecuado que consta de variable (s) que no conmuta (es decir, variables que tienen un conmutador distinto de cero con las variables del problema matemático original) debe introducirse artificialmente en el hamiltoniano para que desempeñe el papel del campo de efecto túnel (parte cinética ). Luego, se puede realizar la simulación con el hamiltoniano cuántico así construido (la función original + parte no conmutada) tal como se describió anteriormente. Aquí, hay una opción para seleccionar el término sin conmutación y la eficiencia del recocido puede depender de eso.
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 (costo) consiste en barreras muy altas pero delgadas que rodean mínimos locales poco profundos. [13] Dado que las probabilidades de transición térmica (proporcionales a, con la temperatura y la constante de Boltzmann ) dependen solo de la alturade las barreras, para barreras muy altas, es extremadamente difícil para las fluctuaciones térmicas sacar el sistema de tales mínimos locales. Sin embargo, como argumentaron anteriormente en 1989 Ray, Chakrabarti & Chakrabarti, [1] la probabilidad de túnel cuántico a través de la misma barrera (considerada de forma aislada) depende no solo de la altura de la barrera, sino también en su ancho y viene dado aproximadamente por , dónde es el campo de los túneles. [14] Este asa adicional a lo ancho, en presencia de túnel cuántico, 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 superficiales. Por un-vidrio giratorio, la altura de la barrera se vuelve de orden . Para valor constante de uno obtiene proporcional a para el tiempo de recocido (en lugar de proporcional a para recocido térmico), mientras que incluso puede convertirse -independiente para los casos en que disminuye a medida que . [15] [16]
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, puede 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. [17]
Cronograma para el recocido cuántico en vidrios giratorios Ising: * 1981 - Se introdujo el modelo de vidrio giratorio Ising y se estudió su comportamiento de transición; [18] * 1989- Idea propuso que las fluctuaciones cuánticas podrían ayudar a explorar paisajes de energía escarpados de los vidrios giratorios de Ising al escapar de los mínimos locales (que tienen barreras altas pero delgadas) usando túneles; [1] * 1991- Realización experimental de vidrio de giro cuántico Ising en LiHoYF; [19] * 1998- Primera simulación Monte Carlo que demuestra el recocido cuántico en sistemas de vidrio Ising; [4] * 1999- Primera demostración experimental de recocido cuántico en imanes de vidrio LiHoYF Ising; [20] * 2011- Máquina de recocido cuántico de circuito superconductor para sistemas de vidrio giratorio de Ising realizada y comercializada por D-Wave Systems. [21]
Implementaciones de D-Wave
En 2011, D-Wave Systems anunció el primer recocido cuántico comercial en el mercado con el nombre de D-Wave One y publicó un artículo en Nature sobre su desempeño. [21] La empresa afirma que este sistema utiliza un chipset de procesador de 128 qubit . [22] El 25 de mayo de 2011, D-Wave anunció que Lockheed Martin Corporation celebró un acuerdo para comprar un sistema D-Wave One. [23] El 28 de octubre 2011 USC 's Instituto de Ciencias hizo la entrega de Lockheed D-Wave One.
En mayo de 2013 se anunció que un consorcio de 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. [24] [25] Ya está disponible un estudio extenso de su desempeño como recocido cuántico, en comparación con algunos algoritmos de recocido clásicos. [26]
En junio de 2014, D-Wave anunció un nuevo ecosistema de aplicaciones cuánticas con la firma financiera computacional 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. [27] Como la primera empresa 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 con éxito que estos procesadores son adecuados para resolver aplicaciones del mundo real. [28]
Con las demostraciones de entrelazamiento publicadas, [29] la cuestión de si la máquina D-Wave puede demostrar la aceleración cuántica en 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 ha realizado sobre el rendimiento de la máquina D-Wave" [30] y "la comparación más justa hasta ahora", intentó definir y medir la cuántica acelerar. Se propusieron varias definiciones, ya que algunas pueden no ser verificables mediante pruebas empíricas, mientras que otras, aunque falsificadas, permitirían no obstante la existencia de ventajas de rendimiento. El estudio encontró que el chip D-Wave "no produjo una aceleración cuántica" y no descartó la posibilidad en futuras pruebas. [31] 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 al observar subconjuntos de las pruebas. Su trabajo ilustró "la naturaleza sutil de la cuestión de la aceleración cuántica". El trabajo posterior [32] ha avanzado la comprensión de estas métricas de prueba y su dependencia de sistemas equilibrados, por lo que se pierde cualquier señal de ventaja debido a la dinámica cuántica.
Hay muchas preguntas abiertas con respecto a 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 ocurrir una aceleración cuántica. Los investigadores de Google, LANL, USC, Texas A&M y D-Wave están trabajando arduamente para encontrar clases de problemas de este tipo. [33]
En diciembre de 2015, Google anunció que el D-Wave 2X supera tanto al recocido simulado como al Quantum Monte Carlo hasta en un factor de 100.000.000 en un conjunto de problemas de optimización difíciles. [34]
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. El algoritmo de Shor requiere una computadora cuántica universal. D-Wave afirma que solo realiza el recocido cuántico. [ cita requerida ]
"Una introducción interdisciplinaria a los algoritmos basados en el recocido cuántico" [35] presenta una introducción a los problemas de optimización combinatoria ( NP-hard ), la estructura general de los algoritmos basados en el recocido cuántico y dos ejemplos de este tipo de algoritmos para resolver instancias de los problemas max-SAT y Mínimo Multicorte, 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 continua discreta a gran escala ilustran la ventaja cuántica. [36]
Referencias
- ^ a b c Ray, P .; Chakrabarti, BK; Chakrabarti, A. (1989). "Modelo de Sherrington-Kirkpatrick en un campo transversal: ausencia de ruptura de simetría réplica debido a fluctuaciones cuánticas". Physical Review B . 39 (16): 11828-11832. Código Bibliográfico : 1989PhRvB..3911828R . doi : 10.1103 / PhysRevB.39.11828 . PMID 9948016 .
- ^ 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 Ascona-Locarno.
- ^ Apolloni, Bruno; Carvalho, Maria C .; De Falco, Diego (1989). "Optimización estocástica cuántica" . Stoc. Proc. Apl . 33 (2): 233–244. doi : 10.1016 / 0304-4149 (89) 90040-9 .
- ^ a b Kadowaki, T .; Nishimori, H. (1998). "Recocido cuántico en el modelo de Ising transversal" . 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 .
- ^ Finnila, AB; Gomez, MA; Sebenik, C .; Stenson, C .; Doll, JD (1994). "Recocido cuántico: un nuevo método para minimizar las funciones multidimensionales". Letras de física química . 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 .
- ^ 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-Complete" . Ciencia . 292 (5516): 472–5. arXiv : quant-ph / 0104129 . Código Bibliográfico : 2001Sci ... 292..472F . doi : 10.1126 / science.1057726 . PMID 11313487 . S2CID 10132718 .
- ^ E. Crosson, E. Farhi, CY-Y. Lin, HH. Lin y P. Shor, "Diferentes estrategias de optimización mediante el algoritmo adiabático cuántico" arXiv : 1401.7320
- ^ D. Muthukrishnan, T. Albash y DA Lidar, "Cuando diabático triunfa sobre el adiabático en la optimización cuántica" arXiv : 1505.01249
- ^ 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 Bibliográfico : 1999Sci ... 284..779B . doi : 10.1126 / science.284.5415.779 . PMID 10221904 . S2CID 37564720 .
- ^ 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 bibliográfico : 2008JMP .... 49l5210M . doi : 10.1063 / 1.2995837 . S2CID 13992889 .
- ^ GE Santoro y E. Tosatti, " Optimización mediante mecánica cuántica: recocido cuántico a través de la evolución adiabática " J. Phys. Un 39 , R393 (2006)
- ^ Heim, B .; Rønnow, TF; Isakov, SV; Troyer, M. (2015). "Recocido cuántico versus clásico de vidrios giratorios Ising" . Ciencia . 348 (6231): 215–217. arXiv : 1411.5693 . Código Bibliográfico : 2015Sci ... 348..215H . doi : 10.1126 / science.aaa4170 . PMID 25765071 .
- ^ "mínimos / máximos locales / globales" .
- ^ A. Das, BK Chakrabarti y RB Stinchcombe, " Recocido cuántico en un sistema con restricciones cinéticas ", Phys. Rev. E 72 art. 026701 (2005)
- ^ Véase, por ejemplo, S. Mukherjee y BK Chakrabarti "Optimización multivariable: recocido cuántico y computación", Eur. Phys. J. ST 224 págs. 17-24 (2015) arXiv : 1408.3262
- ^ Das, A .; Chakrabarti, BK (2008). "Recocido cuántico 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 .
- ^ F. Li; VY Chernyak; NA Sinitsyn (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 .
- ^ BK Chakrabarti, "Comportamiento crítico de los modelos de vidrio giratorio de Ising en un campo transversal", Phys. Rev. B 24, 4062 (1981)
- ^ W. Wu, B. Ellman, TF Rosenbaum, G. Aeppli y DH Reich, "Del clásico al vidrio cuántico", Phys. Rev. Lett. 67 de 2076 (1991)
- ^ J. Brooke, D. Bitko, TF, Rosenbaum y G. Aeppli, "Recocido cuántico de un imán desordenado", Science 284, 779-781 (1999)
- ^ a b Johnson, MW; et al. (2011). "Recocido cuántico con espines fabricados" . Naturaleza . 473 (7346): 194–8. Código bibliográfico : 2011Natur.473..194J . doi : 10.1038 / nature10012 . PMID 21562559 . S2CID 205224761 .
- ^ "Aprendiendo a programar el D-Wave One" . Consultado el 11 de mayo de 2011 .
- ^ "D-Wave Systems vende su primer sistema de computación cuántica a Lockheed Martin Corporation" . 2011-05-25 . Consultado el 30 de mayo de 2011 .
- ^ Jones, N. (2013). "Google y la NASA se apoderan de la computadora cuántica" . Nature News . doi : 10.1038 / nature.2013.12999 . S2CID 57405432 .
- ^ VN Smelyanskiy, EG Rieffel , SI Knysh, CP Williams, MW Johnson, MC Thom, WG Macready, KL Pudenz, "Un enfoque de computación cuántica a corto plazo para problemas computacionales difíciles en la exploración espacial", arXiv : 1204.2821
- ^ 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 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 .
- ^ "D-Wave Systems Building Quantum Application Ecosystem, anuncia asociaciones con DNA-SEQ Alliance y 1QBit" . Sistemas D-Wave . Consultado el 22 de junio de 2014 .
- ^ "Investigación de 1QBit" . 1QBit . Archivado desde el original el 19 de junio de 2014 . Consultado el 22 de junio de 2014 .
- ^ T. Lanting; et al. (29 de mayo de 2014). "Entrelazamiento en un procesador de recocido cuántico". Physical Review X . 4 (2): 021041. arXiv : 1401.3500 . Código Bibliográfico : 2014PhRvX ... 4b1041L . doi : 10.1103 / PhysRevX.4.021041 . S2CID 19235104 .
- ^ Helmut Katzgraber, citado en ( Cho 2014 ).
- ^ Cho, Adrian (20 de junio de 2014), "Quantum or no, controvertida computadora no acelera", Science , 344 (6190): 1330-1331, Bibcode : 2014Sci ... 344.1330C , doi : 10.1126 / science.344.6190.1330 , PMID 24948715.
- ^ Mohammad H. Amin, "Búsqueda de aceleración cuántica en templadores cuánticos cuasiestáticos" arXiv : 1503.04216
- ^ Steiger, Damian; Heim, Bettina; Rønnow, Troels; Troyer, Matthias (22 de octubre de 2015), "Performance of quantum annealing hardware", 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 , 9648 , pág. 964816, doi : 10.1117 / 12.2202661 , S2CID 57916974
- ^ "¿Cuándo puede ganar el recocido cuántico?" . Blog de investigación . Consultado el 21 de enero de 2016 .
- ^ Venegas-Andraca, SE; Cruz-Santos, W .; McGeoch, C .; Lanzagorta, M. (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 .
- ^ Ajagekar, Akshay; Humilde, Travis; Tú, Fengqi (4 de enero de 2020). "Estrategias de soluciones híbridas basadas en computación cuántica para problemas de optimización continua discreta a gran escala" . Computación e Ingeniería Química . 132 : 106630. arXiv : 1910.13045 . doi : 10.1016 / j.compchemeng.2019.106630 . ISSN 0098-1354 .
Otras lecturas
- 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-197. arXiv : 1803.03372 . Código Bib : 2018ConPh..59..174V . doi : 10.1080 / 00107514.2018.1450720 . S2CID 118974781 .
- http://iopscience.iop.org/0305-4470/39/36/R01 . Cite journal requiere
|journal=
( ayuda );Falta o vacío|title=
( ayuda ) - S. Suzuki, J.-i. Inoue & BK Chakrabarti, Fases y transiciones cuánticas de ising en modelos de ising transversal , Springer, Heidelberg (2013), Capítulo 8 sobre recocido cuántico.
- Bapst, V .; Foini, L .; Krzakala, F .; Semerjian, G .; Zamponi, F. (2013). "El algoritmo adiabático cuántico aplicado a problemas de optimización aleatoria: la perspectiva del vidrio de giro cuántico". Informes de física . 523 (3): 127-205. arXiv : 1210.0811 . Código Bibliográfico : 2013PhR ... 523..127B . doi : 10.1016 / j.physrep.2012.10.002 . S2CID 19019744 .
- Arnab Das y Bikas K Chakrabarti (Eds.), Recocido cuántico y métodos de optimización relacionados , Nota de conferencia en física, 679 , Springer, Heidelberg (2005).
- Anjan K. Chandra, Arnab Das y Bikas K Chakrabarti (Eds.), Enfriamiento cuántico, recocido y computación , Lecture Note in Physics, 802 , Springer, Heidelberg (2010).
- Li, Fuxiang; Chernyak, VY; Sinitsyn, NA (2013). "Computación y recocido cuántico: una breve nota documental". arXiv : 1310.1339 . Código bibliográfico : 2013arXiv1310.1339G . Cite journal requiere
|journal=
( ayuda ). - A. Dutta, G. Aeppli, BK Chakrabarti, U. Divakaran, TF Rosenbaum & D. Sen, "Transiciones de fase cuántica en modelos de giro de campo transversal: de la física estadística a la información cuántica , Cambridge University Press, Cambridge y Delhi (2015).
- S. Tanaka, R. Tamura & BK Chakrabarti, Gafas de giro cuántico, recocido y computación , Cambridge University Press, Cambridge y Delhi (2017).
- Asociación de Noticias Científicas de la India, Número especial de "Ciencia y cultura" sobre "Un salto cuántico en la computación" , vol. 85 (5-6), mayo-junio (2019)