1Centro de Sistemas Cuánticos Complejos, Universidad de Texas en Austin, Austin, TX 78712, EE. UU.
2Departamento de Ciencias de la Computación, Universidad de Texas en Austin, Austin, TX 78712, EE. UU.
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Presentamos un marco general para modificar algoritmos de optimización aproximada cuántica (QAOA) para resolver problemas de flujo de red restringido. Al explotar una analogía entre las restricciones de flujo y la ley de Gauss para el electromagnetismo, diseñamos la electrodinámica cuántica de celosía (QED), inspirada en la mezcla de hamiltonianos que preservan las restricciones de flujo a lo largo del proceso QAOA. Esto da como resultado una reducción exponencial en el tamaño del espacio de configuración que necesita ser explorado, que mostramos a través de simulaciones numéricas, produce soluciones aproximadas de mayor calidad en comparación con la rutina QAOA original. Describimos una implementación específica para problemas de ruta de borde disjunto (EDP) relacionados con la minimización de la congestión del tráfico, analizamos numéricamente el efecto de la elección del estado inicial y exploramos las compensaciones entre la complejidad del circuito y los recursos de qubit a través de un mapeo de dualidad partícula-vórtice. La comparación del efecto de los estados iniciales revela que comenzar con una superposición ergódica (insesgada) de soluciones produce un mejor rendimiento que comenzar con el estado fundamental del mezclador, lo que sugiere una desviación del mecanismo de "atajo a la adiabaticidad" que se usa a menudo para motivar QAOA.
► datos BibTeX
► referencias
[ 1 ] Supremacía cuántica utilizando un procesador superconductor programable. Nature, 574: 505–510, 2019. https: / / doi.org/ 10.1038 / s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[ 2 ] Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer y John Wright. Superar la asignación aleatoria en problemas de satisfacción de restricciones de grado acotado. CoRR, abs / 1505.03424, 2015. URL http: / / arxiv.org/ abs / 1505.03424.
arXiv: 1505.03424
[ 3 ] Richard Bellman. En un problema de enrutamiento. Trimestral de matemáticas aplicadas, 16 (1): 87–90, 1958.
[ 4 ] Dominic W. Berry, Andrew M. Childs y Robin Kothari. Simulación hamiltoniana con dependencia casi óptima de todos los parámetros. 2015º Simposio Anual de IEEE 56 sobre Fundamentos de las Ciencias de la Computación, octubre de 2015. https: / / doi.org/ 10.1109 / focs.2015.54. URL http: / / dx.doi.org/ 10.1109 / FOCS.2015.54.
https: / / doi.org/ 10.1109 / focs.2015.54
[ 5 ] Sergey Bravyi, Alexander Kliesch, Robert Koenig y Eugene Tang. Obstáculos para la optimización cuántica variacional de la protección de simetría, diciembre de 2020. URL https: / / doi.org/ 10.1103 / PhysRevLett.125.260505.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[ 6 ] Julia Chuzhoy y Shi Li. Un algoritmo de aproximación polilogarítmica para rutas de bordes disjuntos con congestión 2. En 2012 IEEE 53º Simposio Anual sobre Fundamentos de la Ciencia de la Computación, páginas 233–242, 2012. 10.1109 / FOCS.2012.54.
https: / / doi.org/ 10.1109 / FOCS.2012.54
[ 7 ] Mark de Berg, Otfried Cheong, Marc J. van Kreveld y Mark H. Overmars. Geometría computacional: algoritmos y aplicaciones, 3ª edición. Springer, 2008. ISBN 9783540779735. URL http: / / www.worldcat.org/ oclc / 227584184.
http: / / www.worldcat.org/ oclc / 227584184
[ 8 ] Edsger W Dijkstra y col. Una nota sobre dos problemas en relación con los gráficos. Numerische Mathik, 1 (1): 269-271, 1959.
[ 9 ] Shimon Even, Alon Itai y Adi Shamir. “Sobre la complejidad del calendario y los problemas de flujo de múltiples productos básicos”. En el 16º Simposio anual sobre los fundamentos de la informática (sfcs 1975), páginas 184-193. IEEE, 1975. https: / / doi.org/ 10.1137 / 0205048.
https: / / doi.org/ 10.1137 / 0205048
[ 10 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. Un algoritmo de optimización aproximada cuántica. impresiones electrónicas arXiv, art. arXiv: 1411.4028, noviembre de 2014. URL https: / / ui.adsabs.harvard.edu/ abs / 2014arXiv1411.4028F.
arXiv: 1411.4028
[ 11 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. Un algoritmo de optimización aproximada cuántica aplicado a un problema de restricción de ocurrencia acotada, 2014. URL https: / / arxiv.org/ abs / 1412.6062.
arXiv: 1412.6062
[ 12 ] Edward Farhi, David Gamarnik y Sam Gutmann. El algoritmo de optimización aproximada cuántica necesita ver el gráfico completo: peores ejemplos, 2020a. URL https: / / arxiv.org/ abs / 2005.08747.
arXiv: 2005.08747
[ 13 ] Edward Farhi, David Gamarnik y Sam Gutmann. El algoritmo de optimización aproximada cuántica necesita ver el gráfico completo: un caso típico, 2020b. URL https: / / arxiv.org/ abs / 2004.09002.
arXiv: 2004.09002
[ 14 ] Matthew PA Fisher. Capítulo 13 dualidad en teorías de campos cuánticos de baja dimensión. 2018. https: / / doi.org/ 10.1007 / 978-1-4020-3463-3_13.
https://doi.org/10.1007/978-1-4020-3463-3_13
[ 15 ] Roger Fletcher. Métodos prácticos de optimización. John Wiley e hijos, 2013.
[ 16 ] Lov K. Grover. Un algoritmo rápido de mecánica cuántica para la búsqueda de bases de datos. En Actas del Vigésimo Octavo Simposio Anual de ACM sobre Teoría de la Computación, STOC '96, páginas 212–219, Nueva York, NY, EE. UU., 1996. Association for Computing Machinery. ISBN 0897917855. 10.1145 / 237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
[ 17 ] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli y Rupak Biswas. Desde el algoritmo de optimización cuántica aproximada hasta un operador de alternancia cuántica ansatz. Algoritmos, 12 (2): 34, 2019. 10.3390 / a12020034.
https: / / doi.org/ 10.3390 / a12020034
[ 18 ] Thomas C Hales. El teorema de la curva de Jordan, formal e informalmente. The American Mathematical Monthly, 114 (10): 882–894, 2007. https: / / doi.org/ 10.1080 / 00029890.2007.11920481.
https: / / doi.org/ 10.1080 / 00029890.2007.11920481
[ 19 ] Matthew B. Hastings. Algoritmos clásicos y cuánticos de aproximación de profundidad limitada. preimpresión de arXiv arXiv: 1905.07047, 2019. https: / / doi.org/ 10.26421 / QIC19.13-14-3.
https: / / doi.org/ 10.26421 / QIC19.13-14-3
arXiv: 1905.07047
[ 20 ] KR Khadiev y LI Safina. Algoritmo cuántico para la búsqueda de la ruta más corta en un gráfico acíclico dirigido. Matemáticas computacionales y cibernética de la Universidad de Moscú, 43 (1): 47–51, 2019. https: / / doi.org/ 10.3103 / S0278641919010023.
https: / / doi.org/ 10.3103 / S0278641919010023
[ 21 ] D. Marcos, P. Widmer, E. Rico, M. Hafezi, P. Rabl, U.-J. Wiese y P. Zoller. Teorías de calibre de celosía bidimensional con circuitos cuánticos superconductores. Annals of Physics, 351: 634–654, diciembre de 2014. ISSN 0003-4916. 10.1016 / j.aop.2014.09.011.
https: / / doi.org/ 10.1016 / j.aop.2014.09.011
[ 22 ] Peter W Shor. Algoritmos de cálculo cuántico: logaritmos discretos y factorización. En Actas 35º simposio anual sobre los fundamentos de la informática, páginas 124-134. Ieee, 1994. 10.1109 / SFCS.1994.365700.
https: / / doi.org/ 10.1109 / SFCS.1994.365700
[ 23 ] Zhihui Wang, Nicholas C Rubin, Jason M Dominy y Eleanor G Rieffel. $ xy $ mezcladores: Resultados analíticos y numéricos para el operador cuántico alternante ansatz. Revisión física A, 101 (1): 012320, 2020. 10.1103 / PhysRevA.101.012320.
https: / / doi.org/ 10.1103 / PhysRevA.101.012320
Citado por
[1] Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian, Zi-Wen Liu y Seth Lloyd, "Quantum Earth Mover's Distance: A New Approach to Learning Quantum Data", arXiv: 2101.03037.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2021-07-27 13:33:47). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
No se pudo recuperar Crossref citado por datos durante el último intento 2021-07-27 13:33:45: No se pudieron obtener los datos citados por 10.22331 / q-2021-07-27-510 de Crossref. Esto es normal si el DOI se registró recientemente.
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.
PlatoAi. Web3 reinventado. Inteligencia de datos ampliada.
Haga clic aquí para acceder.
Fuente: https://quantum-journal.org/papers/q-2021-07-27-510/
