1IBM Quantum, Centro de investigación IBM TJ Watson
2Escuela de Matemáticas, Universidad de Bristol
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Presentamos algoritmos clásicos y cuánticos para aproximar funciones de partición de hamiltonianos clásicos a una temperatura dada. Nuestro trabajo tiene dos contribuciones principales: primero, modificamos el algoritmo clásico de Stefankovic, Vempala y Vigoda (J. ACM, 56(3), 2009) para mejorar la complejidad de la muestra; segundo, cuantificamos este nuevo algoritmo, mejorando el algoritmo cuántico anteriormente más rápido para este problema, debido a Harrow y Wei (SODA 2020).
El enfoque convencional para estimar las funciones de partición requiere aproximar las medias de las distribuciones de Gibbs a un conjunto de temperaturas inversas que forman el llamado programa de enfriamiento. La duración del programa de enfriamiento afecta directamente la complejidad del algoritmo. Al combinar nuestra versión mejorada del algoritmo de Stefankovic, Vempala y Vigoda con el estimador de productos emparejados de Huber (Ann. Appl. Probab., 25(2), 2015), nuestro nuevo algoritmo cuántico utiliza un programa de enfriamiento más corto que el conocido anteriormente. Esta longitud coincide con la longitud óptima conjeturada por Stefankovic, Vempala y Vigoda. El algoritmo cuántico también logra una ventaja cuadrática en la cantidad de muestras cuánticas requeridas en comparación con la cantidad de muestras aleatorias extraídas.
por el mejor algoritmo clásico, y su complejidad computacional depende cuadráticamente mejor de la brecha espectral de las cadenas de Markov utilizadas para producir las muestras cuánticas.
Resumen popular
Aquí presentamos algoritmos clásicos y cuánticos para este problema. Nuestro trabajo tiene dos contribuciones principales: primero, modificamos el algoritmo clásico de Stefankovic, Vempala y Vigoda (J. ACM, 56(3), 2009) para mejorar la complejidad de la muestra; segundo, cuantificamos este nuevo algoritmo, mejorando el algoritmo cuántico anteriormente más rápido para este problema, debido a Harrow y Wei (SODA 2020).
El enfoque habitual para la estimación de funciones de partición requiere la aproximación de las medias de las distribuciones de Gibbs a un conjunto de temperaturas inversas que forman el llamado programa de enfriamiento. La duración del programa de enfriamiento afecta directamente la complejidad del algoritmo. Al combinar nuestra versión mejorada del algoritmo de Stefankovic, Vempala y Vigoda con el estimador de productos emparejados de Huber (Ann. Appl. Probab., 25(2), 2015), nuestro nuevo algoritmo cuántico utiliza un programa de enfriamiento más corto que el conocido anteriormente. Esta longitud coincide con la longitud óptima conjeturada por Stefankovic, Vempala y Vigoda. El algoritmo cuántico también logra una ventaja cuadrática en la cantidad de muestras cuánticas requeridas en comparación con la cantidad de muestras aleatorias extraídas por el mejor algoritmo clásico, y su complejidad computacional depende cuadráticamente mejor de la brecha espectral de las cadenas de Markov utilizadas para producir la cuántica. muestras
► datos BibTeX
► referencias
[ 1 ] Ivona Bezáková, Daniel Štefankovič, Vijay V Vazirani y Eric Vigoda. Recocido acelerado simulado para los problemas de conteo permanente y combinatorio. SIAM Journal on Computing, 37(5):1429–1454, 2008. doi:10.1137/050644033.
https: / / doi.org/ 10.1137 / 050644033
[ 2 ] Kurt Binder y Dieter W. Heermann. Simulación de Monte Carlo en física estadística: una introducción (textos de posgrado en física). Primavera, 2019.
[ 3 ] Gilles Brassard, Peter Hoyer, Michele Mosca y Alain Tapp. Amplificación y estimación de amplitud cuántica. Matemáticas contemporáneas, 305: 53–74, 2002.
[ 4 ] Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang y Xiaodi Wu. Algoritmo cuántico para la estimación de volúmenes de cuerpos convexos. arXiv:1908.03903, 2019.
arXiv: 1908.03903
[ 5 ] Guillaume Desjardins, Yoshua Bengio y Aaron C Courville. Sobre el seguimiento de la función de partición. En Avances en sistemas de procesamiento de información neuronal, páginas 2501–2509. Citaseer, 2011.
[ 6 ] Martin Dyer y Alan Frieze. Cálculo del volumen de cuerpos convexos: un caso donde la aleatoriedad probablemente ayuda. Combinatoria probabilística y sus aplicaciones, 44:123–170, 1991.
[ 7 ] Martin Dyer, Alan Frieze y Ravi Kannan. Un algoritmo de tiempo polinomial aleatorio para aproximar el volumen de cuerpos convexos. Revista de la ACM (JACM), 38(1):1–17, 1991. doi:10.1145/102782.102783.
https: / / doi.org/ 10.1145 / 102782.102783
[ 8 ] Andrew Gelman y Xiao-Li Meng. Simulación de constantes de normalización: desde el muestreo de importancia hasta el muestreo puente y el muestreo de ruta. Ciencia estadística, páginas 163–185, 1998. doi:10.1214/ss/1028905934.
https:///doi.org/10.1214/ss/1028905934
[ 9 ] Pablo Glasserman. Métodos Monte Carlo en ingeniería financiera, volumen 53. Springer Science & Business Media, 2013.
[ 10 ] Ian Goodfellow, Yoshua Bengio y Aaron Courville. Aprendizaje profundo. MIT Press, 2016. http://www.deeplearningbook.org.
http: / / www.deeplearningbook.org
[ 11 ] Yassine Hamoudi y Frédéric Magniez. Desigualdad y aplicaciones de Quantum Chebyshev. En 46° Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP), volumen 132, páginas 69:1–69:16, 2019. doi:10.4230/LIPIcs.ICALP.2019.69.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.69
[ 12 ] Aram W Harrow y Annie Y Wei. Recocido simulado cuántico adaptativo para inferencia bayesiana y estimación de funciones de partición. En Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos, páginas 193–212, 2020. doi:10.1137/1.9781611975994.12.
https: / / doi.org/ 10.1137 / 1.9781611975994.12
[ 13 ] Geoffrey E. Hinton, Simon Osindero y Yee- Whye Teh. Un algoritmo de aprendizaje rápido para redes de creencias profundas. Computación neuronal, 18(7):1527–1554, 2006. doi:10.1162/neco.2006.18.7.1527.
https: / / doi.org/ 10.1162 / neco.2006.18.7.1527
[ 14 ] Marco Huber. Algoritmos de aproximación para la constante de normalización de las distribuciones de Gibbs. The Annals of Applied Probability, 25(2):974–985, 2015. doi:10.1214/14-AAP1015.
https:///doi.org/10.1214/14-AAP1015
[ 15 ] Mark Huber y Sarah Schott. Uso de TPA para inferencia bayesiana. Estadística bayesiana, 9:257–282, 2010. doi:10.1093/acprof:oso/9780199694587.003.0009.
https: / / doi.org/ 10.1093 / acprof: oso / 9780199694587.003.0009
[ 16 ] Mark Jerrum y Alistair Sinclair. Aproximando lo permanente. SIAM Journal On Computing, 18(6):1149–1178, 1989. doi:10.1137/0218077.
https: / / doi.org/ 10.1137 / 0218077
[ 17 ] Mark R. Jerrum, Leslie G. Valiant y Vijay V. Vazirani. Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme. Informática Teórica, 43:169 – 188, 1986. doi:10.1016/0304-3975(86)90174-X.
https://doi.org/10.1016/0304-3975(86)90174-X
[ 18 ] Vladímir Kolmogorov. Un algoritmo de aproximación más rápido para la función de partición de Gibbs. En Proceedings of the 31st Conference On Learning Theory, volumen 75 de Proceedings of Machine Learning Research, páginas 228–249. PMLR, 2018.
[ 19 ] Qiang Liu y Alexander T. Ihler. Acotando la función de partición usando la desigualdad del titular. En Actas de la 28.ª Conferencia internacional sobre aprendizaje automático, ICML, páginas 849–856. Omnipress, 2011.
[ 20 ] F. Magniez, A. Nayak, J. Roland y M. Santha. Búsqueda a través de la caminata cuántica. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/090745854.
https: / / doi.org/ 10.1137 / 090745854
[ 21 ] Ashley Montanaro. Aceleración cuántica de los métodos de monte carlo. Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería, 471(2181):20150301, 2015.
[ 22 ] Elchanan Mossel y Allan Sly. Umbrales exactos para muestreadores de Ising-Gibbs en gráficos generales. Ana. Probab., 41(1):294–328, 01 2013. doi:10.1214/11-AOP737.
https: / / doi.org/ 10.1214 / 11-AOP737
[ 23 ] Daniel Štefankovič, Santosh Vempala y Eric Vigoda. Recocido simulado adaptativo: una conexión casi óptima entre el muestreo y el conteo. Revista de la ACM (JACM), 56(3):1–36, 2009. doi:10.1145/1516512.1516520.
https: / / doi.org/ 10.1145 / 1516512.1516520
[ 24 ] Mario Szegedy. Aceleración cuántica de algoritmos basados en cadenas de Markov. En el 45.º simposio anual del IEEE sobre fundamentos de la informática, páginas 32–41. IEEE, 2004.
[ 25 ] Tarjeta JP Valleau y DN. Estimación de Montecarlo de la energía libre mediante muestreo multietápico. Revista de Física Química, 57(12):5457–5462, 1972.
[ 26 ] Eric Vigoda. Límites mejorados para el muestreo de colorantes. Journal of Mathematical Physics, 41(3):1555–1569, 2000. doi:10.1063/1.533196.
https: / / doi.org/ 10.1063 / 1.533196
[ 27 ] Marc Vuffray, Sidhant Misra, Andrey Lokhov y Michael Chertkov. Detección de interacción: aprendizaje eficiente y óptimo de muestra de modelos ising. En Advances in Neural Information Processing Systems, páginas 2595–2603, 2016.
[ 28 ] Pawel Wocjan y Anura Abeyesinghe. Aceleración mediante muestreo cuántico. Revisión física A, 78(4):042336, 2008. doi:10.1103/PhysRevA.78.042336.
https: / / doi.org/ 10.1103 / PhysRevA.78.042336
Citado por
[1] Patrick Rall, "Algoritmos cuánticos coherentes más rápidos para la estimación de fase, energía y amplitud", arXiv: 2103.09717.
[2] Chen-Fu Chiang, Anirban Chowdhury y Pawel Wocjan, “Método de cuantificación eficiente en el espacio para cadenas de Markov reversibles”, arXiv: 2206.06886.
[3] Garrett T. Floyd, David P. Landau y Michael R. Geller, "Algoritmo cuántico para el muestreo de Wang-Landau", arXiv: 2208.09543.
[4] Pawel Wocjan y Kristan Temme, “Szegedy Walk Unitaries for Quantum Maps”, arXiv: 2107.07365.
[5] Patrick Rall y Bryce Fuller, “Estimación de amplitud a partir del procesamiento de señales cuánticas”, arXiv: 2207.08628.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2022-09-02 12:01:44). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
On Servicio citado por Crossref no se encontraron datos sobre las obras citadas (último intento 2022-09-02 12:01:43).
Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.
