QAOA iniciado en caliente con mezcladores personalizados probablemente converge y supera computacionalmente el corte máximo de Goemans-Williamson en profundidades de circuito bajas

QAOA iniciado en caliente con mezcladores personalizados probablemente converge y supera computacionalmente el corte máximo de Goemans-Williamson en profundidades de circuito bajas

Sello de tiempo: 26 de septiembre de 2023 9:22 a.m.

Rubén Tate1, Jai Moondra2, Bryan Gard3, Greg Möhler3y Swati Gupta4

1CCS-3 Ciencias de la Información, Laboratorio Nacional de Los Álamos, Los Álamos, NM 87544, EE. UU.
2Instituto de Tecnología de Georgia, Atlanta, GA 30332, EE. UU.
3Instituto de Investigación Tecnológica de Georgia, Atlanta, GA 30332, EE. UU.
4Sloan School of Management, Instituto de Tecnología de Massachusetts, Cambridge, MA 02142, EE. UU.

¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.

Resumen

Generalizamos el algoritmo de optimización cuántica aproximada (QAOA) de Farhi et al. (2014) para permitir estados iniciales separables arbitrarios con mezcladores correspondientes de modo que el estado inicial sea el estado más excitado del hamiltoniano de mezcla. Demostramos esta versión de QAOA, que llamamos $QAOA-warmest$, simulando Max-Cut en gráficos ponderados. Inicializamos el estado inicial como un $inicio en caliente$ usando aproximaciones dimensionales $2$ y $3$ obtenidas usando proyecciones aleatorias de soluciones al programa semidefinido de Max-Cut, y definimos un $mezclador personalizado$ dependiente del inicio en caliente. Mostramos que estos arranques en caliente inicializan el circuito QAOA con aproximaciones de factor constante de $ 0.658 $ para $ 2 $ - dimensionales y $ 0.585 $ para $ 3 $ - arranques en caliente dimensionales para gráficos con pesos de borde no negativos, mejorando los triviales previamente conocidos ( es decir, $0.5$ para inicialización estándar) límites del peor de los casos en $p=0$. De hecho, estos factores limitan por debajo la aproximación lograda para Max-Cut en profundidades de circuito más altas, ya que también mostramos que QAOA-más cálido con cualquier estado inicial separable converge a Max-Cut bajo el límite adiabático como $prightarrow infty$. Sin embargo, la elección de los arranques en caliente afecta significativamente la tasa de convergencia a Max-Cut, y demostramos empíricamente que nuestros arranques en caliente logran una convergencia más rápida en comparación con los enfoques existentes. Además, nuestras simulaciones numéricas muestran cortes de mayor calidad en comparación con el QAOA estándar, el algoritmo clásico de Goemans-Williamson y un QAOA iniciado en caliente sin mezcladores personalizados para una biblioteca de instancias de $1148$ gráficos (hasta $11$ nodos) y profundidad $p=8 ps Además, demostramos que el QAOA más cálido supera al QAOA estándar de Farhi et al. en experimentos con hardware IBM-Q y Quantinuum actuales.

QAOA iniciado en caliente con mezcladores personalizados probablemente converge y supera computacionalmente el corte máximo de Goemans-Williamson en profundidades de circuito bajas PlatoBlockchain Data Intelligence. Búsqueda vertical. Ai.

Imagen de portada: Rendimiento de QAOA más cálido (con arranques en caliente) y QAOA estándar en función de la profundidad de QAOA para una simulación ideal (discontinua) y ruidosa (punteada). Para el gráfico de 20 nodos elegido, GW logra una relación de aproximación de 0.912, mientras que en el caso ideal, QAOA-warmest supera a GW por $p geq 2$, mientras que QAOA estándar requiere $p > 4$. La simulación de ruido se basa en datos de calibración del dispositivo Guadalupe de IBM-Q.

Resumen popular

El algoritmo de optimización cuántica aproximada (QAOA) es una técnica híbrida cuántica-clásica para la optimización combinatoria que promete ser más poderosa que cualquier optimizador clásico. En este trabajo, ejemplificamos su potencial en un problema de optimización combinatoria fundamental, conocido como Max-Cut, donde el mejor algoritmo clásico posible es el de Goemans y Williamson (GW). Logramos esto introduciendo arranques en caliente obtenidos clásicamente en QAOA, con operadores de mezcla modificados, y demostramos computacionalmente que esto supera a GW. Modificamos el algoritmo cuántico adecuadamente para mantener la conexión con la computación adiabática cuántica; Discutimos la teoría y proporcionamos evidencia numérica y experimental que muestra la promesa de nuestro enfoque.

► datos BibTeX

► referencias

[ 1 ] Juan Preskill. “Computación cuántica en la era NISQ y más allá”. Cuántica 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[ 2 ] Aram W. Harrow y Ashley Montanaro. “Supremacía computacional cuántica”. Naturaleza 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[ 3 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. “Un algoritmo de optimización cuántica aproximada” (2014).

[ 4 ] Iain Dunning, Swati Gupta y John Silberholz. “¿Qué funciona mejor y cuándo? Una evaluación sistemática de heurísticas para Max-Cut y QUBO”. Revista INFORMA de Computación 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[ 5 ] Michel X Goemans y David P Williamson. “Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando programación semidefinida”. Revista de la ACM (JACM) 42, 1115-1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[ 6 ] Samuel Burer y Renato DC Monteiro. "Un algoritmo de programación no lineal para resolver programas semidefinidos mediante factorización de rango bajo". Programación matemática 95, 329–357 (2003).
https:/​/​doi.org/​10.1007/​s10107-002-0352-8

[ 7 ] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, et al. “Qiskit: un marco de código abierto para la computación cuántica” (2019).

[ 8 ] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard y Eugene Tang. “La QAOA se atasca a partir de una buena cuerda clásica” (2022).

[ 9 ] Daniel J. Egger, Jakub Mareček y Stefan Woerner. "Optimización cuántica de arranque en caliente". Cuántico 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[ 10 ] Stefan H Sack, Raimel A Medina, Richard Kueng y Maksym Serbyn. “Inicialización recursiva y codiciosa del algoritmo de optimización cuántica aproximada con mejora garantizada”. Revisión física A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[ 11 ] Stefan H. Sack y Maksym Serbyn. “Inicialización del recocido cuántico del algoritmo de optimización cuántica aproximada”. cuántico 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[ 12 ] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler y Mikhail D. Lukin. "Algoritmo de optimización cuántica aproximada: rendimiento, mecanismo e implementación en dispositivos a corto plazo". Revisión Física X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[ 13 ] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski y Travis S Humble. "Transferencia de parámetros para la optimización cuántica aproximada de maxcut ponderado". Transacciones ACM sobre computación cuántica 4, 1-15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[ 14 ] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev e Ilya Safro. "Transferibilidad de parámetros QAOA óptimos entre gráficos aleatorios". En 2021, Conferencia Internacional IEEE sobre Ingeniería y Computación Cuántica (QCE). Páginas 171–180. IEEE (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00034

[ 15 ] Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner y Daniel J Egger. "Escalado del algoritmo de optimización cuántica aproximada en hardware superconductor basado en qubits". Cuántico 6, 870 (2022).
https:/​/​doi.org/​10.22331/​q-2022-12-07-870

[ 16 ] Phillip C Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis y Travis S Humble. "Escalado de optimización aproximada cuántica en hardware a corto plazo". Informes científicos 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

[ 17 ] Gian Giacomo Guerreschi y Anne Y Matsuura. "QAOA para corte máximo requiere cientos de qubits para aceleración cuántica". Informes científicos 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[ 18 ] Charles Moussa, Henri Calandra y Vedran Dunjko. “Cuántico o no cuántico: hacia la selección de algoritmos en la optimización cuántica a corto plazo”. Ciencia y Tecnología Cuánticas 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[ 19 ] Colin Campbell y Edward Dahl. “QAOA del más alto nivel”. En 2022, IEEE 19.ª Conferencia internacional sobre arquitectura de software complementaria (ICSA-C). Páginas 141–146. IEEE (2022).
https:/​/​doi.org/​10.1109/​ICSA-C54293.2022.00035

[ 20 ] Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble y George Siopsis. "Impacto de las estructuras gráficas para QAOA en maxcut". Procesamiento de información cuántica 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[ 21 ] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​y Daniel J Egger. “Expresión y optimización aproximada cuántica” (2022).

[ 22 ] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg e Ilya Safro. “Las simetrías clásicas y el algoritmo de optimización cuántica aproximada”. Procesamiento de información cuántica 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[ 23 ] Jonathan Wurtz y Peter Love. “Garantías de rendimiento del algoritmo de optimización aproximada cuántica Maxcut para p>1”. Revisión física A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[ 24 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. “Algoritmos cuánticos para arquitecturas de qubit fijos” (2017).

[ 25 ] Sergey Bravyi, Alexander Kliesch, Robert Koenig y Eugene Tang. "Obstáculos para la optimización cuántica variacional a partir de la protección de la simetría". Cartas de revisión física 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[ 26 ] Edward Farhi, David Gamarnik y Sam Gutmann. “El algoritmo de optimización cuántica aproximada necesita ver el gráfico completo: un caso típico” (2020).

[ 27 ] Sergey Bravyi, Alexander Kliesch, Robert Koenig y Eugene Tang. "Algoritmos híbridos cuánticos-clásicos para coloración aproximada de gráficos". Cuántico 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[ 28 ] Mateo B. Hastings. “Algoritmos de aproximación de profundidad acotados clásicos y cuánticos” (2019).

[ 29 ] Kunal Marwaha. "El algoritmo local clásico de corte máximo supera a $ p = 2 $ QAOA en gráficos regulares de gran circunferencia". Cuántico 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[ 30 ] Boaz Barak y Kunal Marwaha. “Algoritmos clásicos y limitaciones cuánticas para un corte máximo en gráficos de alta circunferencia” (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[ 31 ] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler y Swati Gupta. "Uniendo lo clásico y lo cuántico con arranques en caliente inicializados por SDP para QAOA". Transacciones ACM sobre computación cuántica (2022).
https: / / doi.org/ 10.1145 / 3549554

[ 32 ] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli y Rupak Biswas. “Del algoritmo de optimización cuántica aproximada a un operador cuántico alterno ansatz”. Algoritmos 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

[ 33 ] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy y Eleanor G. Rieffel. “Mezcladores $xy$: resultados analíticos y numéricos para el operador cuántico alterno ansatz”. Física. Rev.A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

[ 34 ] Linghua Zhu, Ho Lun Tang, George S. Barron, FA Calderón-Vargas, Nicholas J. Mayhall, Edwin Barnes y Sophia E. Economou. “Algoritmo de optimización aproximada cuántica adaptativa para la resolución de problemas combinatorios en una computadora cuántica”. Física. Rev. Investigación 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[ 35 ] Andreas Bärtschi y Stephan Eidenbenz. "Mezcladores Grover para QAOA: cambio de complejidad del diseño del mezclador a la preparación del estado". En 2020 Conferencia Internacional IEEE sobre Ingeniería y Computación Cuántica (QCE). Páginas 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[ 36 ] Zhang Jiang, Eleanor G Rieffel y Zhihui Wang. "Circuito cuántico casi óptimo para la búsqueda no estructurada de Grover utilizando un campo transversal". Revisión física A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[ 37 ] 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. Páginas 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[ 38 ] Yin Zhang, Samuel Burer y Renato DC Monteiro. "Heurísticas de relajación de rango 2 para programas cuadráticos binarios de corte máximo y otros". Revista SIAM sobre optimización 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[ 39 ] Song Mei, Theodor Misiakiewicz, Andrea Montanari y Roberto Imbuzeiro Oliveira. “Resolución de problemas de sdps para sincronización y maxcut mediante la desigualdad de Grothendieck”. En Congreso sobre teoría del aprendizaje. Páginas 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[ 40 ] Ojas Parekh y Kevin Thompson. “Una aproximación óptima del estado del producto para hamiltonianos cuánticos bilocales con términos positivos” (2). arXiv:2022.
arXiv: 2206.08342

[ 41 ] Rubén Tate y Swati Gupta. “Ci-qube”. Repositorio de GitHub (2021). URL: https://​/​github.com/​swati1729/​CI-QuBe.
https:/​/​github.com/​swati1729/​CI-QuBe

[ 42 ] Howard Karloff. "¿Qué tan bueno es el algoritmo MAX-CUT de Goemans-Williamson?". Revista SIAM de Computación 29, 336–350 (1999).
https: / / doi.org/ 10.1137 / S0097539797321481

[ 43 ] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. "Optimización cuántica aproximada de problemas de gráficos no planos en un procesador superconductor plano". Física de la naturaleza 17, 332–336 (2021).
https: / / doi.org/ 10.1038 / s41567-020-01105-y

[ 44 ] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay y Jay M. Gambetta. "Mitigación de errores de medición en experimentos multiqubit". Física. Rev. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[ 45 ] George S. Barron y Christopher J. Wood. “Mitigación de errores de medición para algoritmos cuánticos variacionales” (2020).

[ 46 ] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan , Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu y Xiaoqiang Zheng. “TensorFlow: aprendizaje automático a gran escala en sistemas heterogéneos” (2015).

[ 47 ] Diederik P. Kingma y Jimmy Ba. “Adam: un método para la optimización estocástica” (2014).

[ 48 ] Roger Fletcher. “Métodos prácticos de optimización (2ª edición)”. John Wiley e hijos. Nueva York, NY, Estados Unidos (1987).
https: / / doi.org/ 10.1002 / 9781118723203

[ 49 ] MJD Powell. "Un método de optimización de búsqueda directa que modela las funciones objetivo y de restricción mediante interpolación lineal". Avances en optimización y análisis numérico 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[ 50 ] Alan J. Laub. “Análisis matricial para científicos e ingenieros”. Volumen 91. Siam. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907

[ 51 ] Georg Frobenius. “Ueber matrizen aus nicht negativon elementen”. Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften Páginas 456–477 (1912).

[ 52 ] A. Kaveh y H. Rahami. "Un método unificado para la descomposición propia de productos gráficos". Comunicaciones en métodos numéricos en ingeniería con aplicaciones biomédicas 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[ 53 ] Simón Špacapan. “Conectividad de productos cartesianos de grafos”. Cartas de Matemáticas Aplicadas 21, 682–685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

[ 54 ] Jacek Gondzio y Andreas Grothey. "Resolver problemas de planificación financiera no lineal con 109 variables de decisión en arquitecturas masivamente paralelas". Transacciones WIT sobre modelado y simulación 43 (2006).
https: / / doi.org/ 10.2495 / CF060101

[ 55 ] Fan RK Chung. “Teoría de grafos espectrales”. Volumen 92. Sociedad Matemática Estadounidense. (1997).
https: / / doi.org/ 10.1090 / cbms / 092

[ 56 ] MA Nielsen e IL Chuang. “Computación cuántica e información cuántica: edición del décimo aniversario”. Cambridge University Press, Nueva York. (10).
https: / / doi.org/ 10.1017 / CBO9780511976667

[ 57 ] Vincent R. Pascuzzi, Andre He, Christian W. Bauer, Wibe A. de Jong y Benjamin Nachman. "Extrapolación de ruido cero computacionalmente eficiente para la mitigación de errores de puerta cuántica". Revisión física A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[ 58 ] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala y Kristan Temme. "Cancelación de errores probabilísticos con modelos dispersos de Pauli-Lindblad en procesadores cuánticos ruidosos". Física de la naturaleza, páginas 1 a 6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[ 59 ] Nathan Krislock, Jérôme Malick y Frédéric Roupin. "BiqCrunch: un método semidefinido de ramificación y unión para resolver problemas cuadráticos binarios". Transacciones ACM sobre software matemático 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[ 60 ] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer y Matt McGinnis. "Los valores propios más pequeños de gráficos de Hamming, gráficos de Johnson y otros gráficos de distancia regular con parámetros clásicos". Revista de teoría combinatoria, Serie B 133, 88-121 (2018).
https: / / doi.org/ 10.1016 / j.jctb.2018.04.005

[ 61 ] Donald Knuth. “Matrices combinatorias”. Artículos seleccionados sobre matemáticas discretas (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Citado por

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner y Daniel J. Egger, "Escalado del algoritmo de optimización cuántica aproximada en hardware basado en qubits superconductores", Cuántica 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun y Marco Pistoia, “La alineación entre el estado inicial y el mezclador mejora el rendimiento de QAOA para la optimización de cartera restringida”, arXiv: 2305.03857, (2023).

[3] V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad y Ping Koy Lam, “An Expressive Ansatz for Low-Depth Quantum Optimisation”, arXiv: 2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo y Anh Pham, "Complementar el algoritmo de búsqueda de Grover: una implementación de supresión de amplitud", arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele y Procolo Lucignano, “Convergencia de QAOA digitalizado-contradiabático: profundidad del circuito versus parámetros libres”, arXiv: 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble y Creston D. Herold, “Modelado de ruido en interacciones globales Mølmer-Sørensen aplicado a la optimización cuántica aproximada”, Revisión física A 107 6, 062406 (2023).

[7] Guoming Wang, “Algoritmo de optimización cuántica impulsado clásicamente”, arXiv: 2203.13936, (2022).

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2023-09-27 01:31:19). 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 2023-09-27 01:31:17).

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.

Sello de tiempo:

Mas de Diario cuántico