QuOne Lab, Centro de Investigación e Innovación Phanous, Teherán, Irán
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Se espera que las evoluciones de los hamiltonianos locales en tiempos cortos sigan siendo locales y, por lo tanto, limitadas. En este artículo, validamos esta intuición demostrando algunas limitaciones en las evoluciones a corto plazo de los hamiltonianos locales dependientes del tiempo. Mostramos que la distribución de la salida de medición de las evoluciones de tiempo corto (como mucho logarítmicas) de los hamiltonianos locales está $concentrada$ y satisface una $textit{desigualdad isoperimétrica}$. Para mostrar aplicaciones explícitas de nuestros resultados, estudiamos el problema $M$$small{AX}$$C$$small{UT}$ y concluimos que el recocido cuántico necesita al menos un tiempo de ejecución que escale logarítmicamente en el tamaño del problema para vencer a los algoritmos clásicos en $M$$small{AX}$$C$$small{UT}$. Para establecer nuestros resultados, también demostramos un límite de Lieb-Robinson que funciona para hamiltonianos dependientes del tiempo que podrían ser de interés independiente.
Imagen destacada: esta ilustración muestra la distribución de probabilidad del peso de Hamming de tres estados diferentes de $n$-qubit para $n=100$. La distribución centrada en el medio (azul) es la distribución típica para el estado inicial de un producto (p. ej., $|+rangle^{otimes n}$). La distribución que tiene un pico justo a la derecha (naranja) representa la distribución después de un corto tiempo de evolución del estado inicial descrito por el Teorema 2 del manuscrito. La distribución que tiene dos picos a cada lado del espectro (verde) es una aproximación para el estado GHZ. Esto muestra que el estado GHZ no puede generarse ni siquiera aproximadamente mediante un recocido cuántico de corta duración.
Resumen popular
► datos BibTeX
► referencias
[ 1 ] T. Kadowaki y H. Nishimori. Recocido cuántico en el modelo transversal de Ising. Revisión física E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann y M. Sipser. Computación cuántica por evolución adiabática. arXiv:0001106 [cuántico-ph] (2000).
https://doi.org/10.48550/arXiv.quant-ph/0001106
arXiv: 0001106
[ 3 ] T. Kato. Sobre el teorema adiabático de la mecánica cuántica. Revista de la Sociedad Física de Japón 5, 435–439 (1950).
https: / / doi.org/ 10.1143 / JPSJ.5.435
[ 4 ] M. Born y V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180 (1928).
https: / / doi.org/ 10.1007 / BF01343193
[ 5 ] T. Albash y DA Lidar. Computación cuántica adiabática. Reseñas de Modern Physics 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002
[ 6 ] I. Gallina y FM Spedalieri. Recocido cuántico para optimización restringida. Revisión Física Aplicada 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007
[ 7 ] S. Puri, CK Andersen, AL Grimsmo y A. Blais. Recocido cuántico con osciladores no lineales conectados todos a todos. Comunicaciones de la naturaleza 8, 15785 (2017).
https: / / doi.org/ 10.1038 / ncomms15785
[ 8 ] W. Lechner, P. Hauke y P. Zoller. Una arquitectura de recocido cuántico con conectividad de todos a todos a partir de interacciones locales. Avances científicos 1, e1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838
[ 9 ] S. Jiang, KA Britt, AJ McCaskey, TS Humble y S. Kais. Recocido cuántico para factorización prima. Informes científicos 8, 17667 (2018).
https: / / doi.org/ 10.1038 / s41598-018-36058-z
[ 10 ] RY Li, R. Di Felice, R. Rohs y DA Lidar. Recocido cuántico versus aprendizaje automático clásico aplicado a un problema de biología computacional simplificado. Información cuántica NPJ 4, 1–10 (2018).
https://doi.org/10.1038/s41534-018-0060-8
[ 11 ] L. Stella, GE Santoro y E. Tosatti. Optimización por recocido cuántico: Lecciones de casos simples. Revisión Física B 72, 014303 (2005).
https: / / doi.org/ 10.1103 / PhysRevB.72.014303
[ 12 ] O. Titiloye y A. Crispin. Recocido cuántico del problema de coloración de grafos. Optimización discreta 8, 376–384 (2011).
https:///doi.org/10.1016/j.disopt.2010.12.001
[ 13 ] A. Mott, J. Job, J.-R. Vlimant, D. Lidar y M. Spiropulu. Resolución de un problema de optimización de Higgs con recocido cuántico para el aprendizaje automático. Naturaleza 550, 375–379 (2017).
https: / / doi.org/ 10.1038 / nature24047
[ 14 ] KL Pudenz, T. Albash y D. A Lidar. Corrección de recocido cuántico para problemas aleatorios de Ising. Revisión Física A 91, 042302 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.042302
[ 15 ] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose y A. Aspuru-Guzik. Encontrar conformaciones de baja energía de modelos de proteínas reticulares mediante recocido cuántico. Informes científicos 2, 571 (2012).
https: / / doi.org/ 10.1038 / srep00571
[ 16 ] KL Pudenz, T. Albash y D. A Lidar. Recocido cuántico con corrección de errores con cientos de qubits. Comunicaciones de la naturaleza 5, 1–10 (2014).
https: / / doi.org/ 10.1038 / ncomms4243
[ 17 ] R. Martoňák, GE Santoro y E. Tosatti. Recocido cuántico del problema del viajante de comercio. Revisión física E 70, 057701 (2004).
https: / / doi.org/ 10.1103 / PhysRevE.70.057701
[ 18 ] SH Adachi y MP Henderson. Aplicación del recocido cuántico al entrenamiento de redes neuronales profundas. arXiv:1510.06356 [cuántico-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv: 1510.06356
[ 19 ] M. W. Johnson, et al. Recocido cuántico con hilados fabricados. Naturaleza 473, 194–198 (2011).
https: / / doi.org/ 10.1038 / nature10012
[ 20 ] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor y DA Lidar. Firma experimental de recocido cuántico programable. Comunicaciones de la naturaleza 4, 1–8 (2013).
https: / / doi.org/ 10.1038 / ncomms3067
[ 21 ] Rey AD, et al. Recocido cuántico coherente en una cadena Ising programable de 2000 qubits. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv: 2202.05847
[ 22 ] B. Foxen, et al. Demostración de un conjunto continuo de puertas de dos qubits para algoritmos cuánticos a corto plazo. Cartas de revisión física 125, 120504 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.120504
[ 23 ] K.Wright, et al. Evaluación comparativa de una computadora cuántica de 11 qubits. Comunicaciones de la naturaleza 10, 1–6 (2019).
https://doi.org/10.1038/s41467-019-13534-2
[ 24 ] EJ Crosson y DA Lidar. Perspectivas de mejora cuántica con recocido cuántico diabático. Nature Reviews Physics 3, 466–489 (2021).
https://doi.org/10.1038/s42254-021-00313-6
[ 25 ] E. Farhi, J. Goldstone y S. Gutmann. Un algoritmo de optimización aproximada cuántica. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028
[ 26 ] E. Farhi, D. Gamarnik y S. Gutmann. El algoritmo de optimización aproximada cuántica necesita ver el gráfico completo: ejemplos del peor de los casos. arXiv:2005.08747 [cuántico-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv: 2005.08747
[ 27 ] E. Farhi, D. Gamarnik y S. Gutmann. El algoritmo de optimización aproximada cuántica necesita ver el gráfico completo: un caso típico. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv: 2004.09002
[ 28 ] S. Bravyi, A. Kliesch, R. Koenig y E. Tang. Obstáculos para la optimización cuántica variacional de Symmetry Protection. Cartas de revisión física 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[ 29 ] S. Bravyi, D. Gosset y R. Movassagh. Algoritmos clásicos para valores medios cuánticos. Física de la naturaleza 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[ 30 ] S. Bravyi, A. Kliesch, R. Koenig y E. Tang. Algoritmos híbridos cuánticos-clásicos para la coloración aproximada de gráficos. Cuántica 6, 678 (2022).
https://doi.org/10.22331/q-2022-03-30-678
[ 31 ] L. Eldar y AW Harrow. Hamiltonianos locales cuyos estados básicos son difíciles de aproximar. En 2017, 58.º Simposio anual sobre fundamentos de la informática (FOCS) del IEEE, 427–438 (2017).
https: / / doi.org/ 10.1109 / FOCS.2017.46
[ 32 ] LT Brady, CL Baldwin, A. Bapat, Y. Kharkov y AV Gorshkov. Protocolos óptimos en Quantum Annealing y Quantum Aproximate Optimization Algorithm Problems. Cartas de revisión física 126, 070505 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.070505
[ 33 ] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov y AV Gorshkov. Comportamiento de algoritmos cuánticos analógicos. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv: 2107.01218
[ 34 ] LC Venuti, D. D'Alessandro y DA Lidar. Control Óptimo para Optimización Cuántica de Sistemas Cerrados y Abiertos. Revisión Física Aplicada 16, 054023 (2021).
https: / / doi.org/ 10.1103 / PhysRevApplied.16.054023
[ 35 ] AM Childs, Y. Su, MC Tran, N. Wiebe y S. Zhu. Teoría del error de trotón con escala del conmutador. Revisión física X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
[ 36 ] B. Nachtergaele, Y. Ogata y R. Sims. Propagación de correlaciones en sistemas reticulares cuánticos. Revista de Física Estadística 124, 1–13 (2006).
https://doi.org/10.1007/s10955-006-9143-6
[ 37 ] B. Nachtergaele y R. Sims. Límites de Lieb-Robinson en la física cuántica de muchos cuerpos. Matemáticas contemporáneas 529, 141–176 (2010).
https: / / doi.org/ 10.1090 / conm / 529/10429
[ 38 ] S. Bravyi, MB Hastings y F. Verstraete. Límites de Lieb-Robinson y generación de correlaciones y orden cuántico topológico. Cartas de Revisión Física 97, 050401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.050401
[ 39 ] C.-F. Chen y A. Lucas. Límites de crecimiento del operador a partir de la teoría de grafos. Comunicaciones en física matemática 385, páginas 1273–1323 (2021).
https://doi.org/10.1007/s00220-021-04151-6
[ 40 ] EH Lieb y DW Robinson. La velocidad de grupo finito de los sistemas de espín cuántico. Comunicaciones en Física Matemática 28, 251–257 (1972).
https: / / doi.org/ 10.1007 / BF01645779
[ 41 ] J. Haah, MB Hastings, R. Kothari y GH Low. Algoritmo cuántico para simular la evolución en tiempo real de hamiltonianos reticulares. Simposio anual número 2018 del IEEE de 59 sobre fundamentos de la informática (FOCS), 350–360 (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00041
[ 42 ] A. Lubotzky, R. Phillips y P. Sarnak. gráficos de Ramanujan. Combinatoria 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799
[ 43 ] B.Mohar. Números isoperimétricos de gráficos. Revista de Teoría Combinatoria, Serie B 47, 274–291 (1989).
https://doi.org/10.1016/0095-8956(89)90029-4
[ 44 ] AW Marcus, DA Spielman y N. Srivastava. Familias entrelazadas IV: gráficos bipartitos de Ramanujan de todos los tamaños. En 2015, 56.º Simposio anual sobre fundamentos de la informática (FOCS) del IEEE, 1358–1377 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.87
[ 45 ] AW Marcus, DA Spielman y N. Srivastava. Familias entrelazadas IV: gráficos bipartitos de Ramanujan de todos los tamaños. SIAM Journal on Computing 47, 2488–2509 (2018).
https: / / doi.org/ 10.1137 / 16M106176X
[ 46 ] C. Hall, D. Puder y WF Sawin. Recubrimientos Ramanujan de gráficos. Avances en Matemáticas 323, 367–410 (2018).
https: / / doi.org/ 10.1016 / j.aim.2017.10.042
[ 47 ] MX Goemans y DP Williamson. Algoritmos de aproximación mejorados para problemas de máximo corte y satisfacibilidad usando programación semidefinida. Diario de la ACM 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684
[ 48 ] RD Somma, D. Nagaj y M. Kieferová. Quantum Speedup por Quantum Annealing. Cartas de revisión física 109, 050501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.050501
[ 49 ] MB Hastings. El poder de la computación cuántica adiabática sin problema de signo. Cuántica 5, 597 (2021).
https://doi.org/10.22331/q-2021-12-06-597
[ 50 ] A. Gilyén, MB Hastings y U. Vazirani. Ventaja (sub)exponencial de la computación cuántica adiabática sin problema de signo. En Actas del Simposio Anual ACM sobre Teoría de la Computación (STOC), 1357–1369 (2021).
https: / / doi.org/ 10.1145 / 3406325.3451060
[ 51 ] R. Bhatia. Análisis matricial. Textos de Grado en Matemáticas. Springer Nueva York (1996).
https://doi.org/10.1007/978-1-4612-0653-8
[ 52 ] R. Bhatia. Matrices definidas positivas. Prensa de la Universidad de Princeton, (2007).
https: / / doi.org/ 10.1515 / 9781400827787
[ 53 ] BD McKay, NC Wormald y B. Wysocka. Ciclos cortos en grafos regulares aleatorios. Revista electrónica de combinatoria 11, 1–12 (2004).
https: / / doi.org/ 10.37236 / 1819
[ 54 ] F. Kardoš, D. Král y J. Volec. Cortes de borde máximos en gráficos cúbicos con gran circunferencia y en gráficos cúbicos aleatorios. Estructuras aleatorias y algoritmos 41, 506–520 (2012).
https: / / doi.org/ 10.1002 / rsa.20471
[ 55 ] D. Coppersmith, D. Gamarnik, MT Hajiaghayi y GB Sorkin. MAX SAT aleatorio, MAX CUT aleatorio y sus transiciones de fase. Estructuras aleatorias y algoritmos 24, 502–545 (2004).
https: / / doi.org/ 10.1002 / rsa.20015
[ 56 ] A. Dembo, A. Montanari y S. Sen. Cortes extremos de gráficos aleatorios dispersos. Anales de probabilidad 45, 1190–1217 (2017).
https: / / doi.org/ 10.1214 / 15-AOP1084
Citado por
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé y Daniel Stilck França, “Limitaciones de los algoritmos cuánticos variacionales: un enfoque de transporte cuántico óptimo”, arXiv: 2204.03455.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2022-07-19 03:10:09). 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-07-19 03:10:07).
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.
