1IBM Quantum, IBM Research - Zúrich, Säumerstrasse 4, 8803 Rüschlikon, Suiza
2Universidad Técnica Checa, Karlovo nam. 13, Praga 2, República Checa
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Existe un interés creciente en los algoritmos cuánticos para problemas de programación de enteros y optimización combinatoria. Los solucionadores clásicos para tales problemas emplean relajaciones, que reemplazan las variables binarias por variables continuas, por ejemplo, en forma de problemas con valores matriciales de dimensiones superiores (programación semidefinida). Según la conjetura de los juegos únicos, estas relajaciones a menudo proporcionan las mejores relaciones de rendimiento disponibles clásicamente en tiempo polinomial. Aquí, discutimos cómo iniciar en caliente la optimización cuántica con un estado inicial correspondiente a la solución de una relajación de un problema de optimización combinatoria y cómo analizar las propiedades de los algoritmos cuánticos asociados. En particular, esto permite que el algoritmo cuántico herede las garantías de rendimiento del algoritmo clásico. Ilustramos esto en el contexto de la optimización de la cartera, donde nuestros resultados indican que el inicio en caliente del algoritmo de optimización aproximada cuántica (QAOA) es particularmente beneficioso a baja profundidad. Asimismo, QAOA recursivo para problemas MAXCUT muestra un aumento sistemático en el tamaño del corte obtenido para gráficos completamente conectados con pesos aleatorios, cuando se utiliza el redondeo aleatorio de Goemans-Williamson en un inicio en caliente. Es sencillo aplicar las mismas ideas a otros esquemas de redondeo aleatorio y problemas de optimización.
Imagen de portada: El circuito cuántico de QAOA de arranque en caliente.
Resumen popular
► datos BibTeX
► referencias
[ 1 ] Nikolaj Moll, Panagiotis Barkoutsos, Lev S. Bishop, Jerry M. Chow, Andrew Cross, Daniel J. Egger, Stefan Filipp, Andreas Fuhrer, Jay M. Gambetta, Marc Ganzhorn y otros. Optimización cuántica mediante algoritmos variacionales en dispositivos cuánticos a corto plazo. Ciencia cuántica. Technol., 3 (3): 030503, 2018. 10.1088 / 2058-9565 / aab822.
https: / / doi.org/ 10.1088 / 2058-9565 / aab822
[ 2 ] Abhinav Kandala, Kristan Temme, Antonio D. Corcoles, Antonio Mezzacapo, Jerry M. Chow y Jay M. Gambetta. La mitigación de errores extiende el alcance computacional de un procesador cuántico ruidoso. Nature, 567: 491–495, 2018. 10.1038 / s41586-019-1040-7.
https://doi.org/10.1038/s41586-019-1040-7
[ 3 ] Marc Ganzhorn, Daniel J. Egger, Panagiotis Kl. Barkoutsos, Pauline Ollitrault, Gian Salis, Nikolaj Moll, Andreas Fuhrer, Peter Mueller, Stefan Woerner, Ivano Tavernelli y Stefan Filipp. Simulación de puerta eficiente de autoestados moleculares en una computadora cuántica. Phys. Rev. Applied, 11: 044092, abril de 2019. 10.1103 / PhysRevApplied.11.044092.
https: / / doi.org/ 10.1103 / PhysRevApplied.11.044092
[ 4 ] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe y Seth Lloyd. Aprendizaje automático cuántico. Nature, 549 (7671): 195-202, 2017. 10.1038 / nature23474.
https: / / doi.org/ 10.1038 / nature23474
[ 5 ] Vojtech Havlicek, Antonio D. Corcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow y Jay M. Gambetta. Aprendizaje supervisado con espacios de funciones mejorados cuánticamente. Nature, 567: 209 - 212, 2019. 10.1038 / s41586-019-0980-2.
https://doi.org/10.1038/s41586-019-0980-2
[ 6 ] Daniel J. Egger, Claudio Gambella, Jakub Mareček, Scott McFaddin, Martin Mevissen, Rudy Raymond, Aandrea Simonetto, Sefan Woerner y Elena Yndurain. Computación cuántica para las finanzas: estado de la técnica y perspectivas de futuro. IEEE Trans. en Quantum Eng., 1: 1–24, 2020. 10.1109 / TQE.2020.3030314.
https: / / doi.org/ 10.1109 / TQE.2020.3030314
[ 7 ] Stefan Woerner y Daniel J. Egger. Análisis de riesgo cuántico. npj Quantum Inf., 5:15, 2019. 10.1038 / s41534-019-0130-6.
https://doi.org/10.1038/s41534-019-0130-6
[ 8 ] Patrick Rebentrost, Brajesh Gupt y Thomas R. Bromley. Finanzas computacionales cuánticas: fijación de precios de Monte Carlo de derivados financieros. Phys. Rev. A, 98: 022321, agosto de 2018. 10.1103 / PhysRevA.98.022321.
https: / / doi.org/ 10.1103 / PhysRevA.98.022321
[ 9 ] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen y Stefan Woerner. Fijación de precios de opciones utilizando computadoras cuánticas. Quantum, 4: 291, 2020. 10.22331 / q-2020-07-06-291.
https://doi.org/10.22331/q-2020-07-06-291
[ 10 ] Ana Martin, Bruno Candelas, Ángel Rodríguez-Rozas, José D. Martín-Guerrero, Xi Chen, Lucas Lamata, Román Orús, Enrique Solano y Mikel Sanz. Hacia la fijación de precios de derivados financieros con una computadora cuántica de IBM. Phys. Rev. Research, 3: 013167, febrero de 2021. 10.1103 / PhysRevResearch.3.013167.
https: / / doi.org/ 10.1103 / PhysRevResearch.3.013167
[ 11 ] Roman Orus, Samuel Mugel y Enrique Lizaso. Computación cuántica para las finanzas: descripción general y perspectivas. Rev. Phys., 4: 100028, 2019. 10.1016 / j.revip.2019.100028.
https: / / doi.org/ 10.1016 / j.revip.2019.100028
[ 12 ] Daniel J. Egger, Ricardo G. Gutiérrez, Jordi Cahue Mestre y Stefan Woerner. Análisis de riesgo crediticio mediante computadoras cuánticas. IEEE Trans. Comput., 1: 1–1, noviembre de 2020. 10.1109 / TC.2020.3038063.
https: / / doi.org/ 10.1109 / TC.2020.3038063
[ 13 ] Almudena Carrera Vazquez y Stefan Woerner. Preparación de estado eficiente para la estimación de amplitud cuántica. Phys. Rev. Applied, 15: 034027, marzo de 2021. 10.1103 / PhysRevApplied.15.034027.
https: / / doi.org/ 10.1103 / PhysRevApplied.15.034027
[ 14 ] Lee Braine, Daniel J. Egger, Jennifer Glick y Stefan Woerner. Algoritmos cuánticos para optimización binaria mixta aplicados a la liquidación de transacciones. IEEE Trans. en Quantum Eng., 2: 1–8, 2021. 10.1109 / TQE.2021.3063635.
https: / / doi.org/ 10.1109 / TQE.2021.3063635
[ 15 ] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli y Stefan Woerner. Mejora de la optimización cuántica variacional mediante cvar. Quantum, 4: 256, abril de 2020. 10.22331 / q-2020-04-20-256.
https://doi.org/10.22331/q-2020-04-20-256
[ 16 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. Un algoritmo de optimización de aproximación cuántica, 2014a. URL https: / / arxiv.org/ abs / 1411.4028.
arXiv: 1411.4028
[ 17 ] Edward Farhi, Jeffrey Goldstone y Sam Gutmann. Un algoritmo de optimización de aproximación cuántica aplicado a un problema de restricción de ocurrencia acotada, 2014b. URL https: / / arxiv.org/ abs / 1412.6062.
arXiv: 1412.6062
[ 18 ] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven y Claudio Chamon. Optimización de algoritmos cuánticos variacionales utilizando el principio mínimo de pontryagin. Phys. Rev. X, 7: 021027, mayo de 2017. 10.1103 / PhysRevX.7.021027.
https: / / doi.org/ 10.1103 / PhysRevX.7.021027
[ 19 ] Mark W. Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J. Berkley, Jan Johansson, Paul Bunyk y col. Recocido cuántico con espines fabricados. Nature, 473 (7346): 194-198, mayo de 2011. 10.1038 / nature10012.
https: / / doi.org/ 10.1038 / nature10012
[ 20 ] Glen Bigan Mbeng, Rosario Fazio y Giuseppe Santoro. Recocido cuántico: un viaje a través de la digitalización, el control y los esquemas híbridos de variación cuántica, 2019. URL https: / / arxiv.org/ abs / 1906.08948.
arXiv: 1906.08948
[ 21 ] Michael Juenger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi y Tobias Stollenwerk. Rendimiento de un anillador cuántico para cálculos del estado fundamental de Ising en gráficos de quimera, 2019. URL https: / / arxiv.org/ abs / 1904.11965.
arXiv: 1904.11965
[ 22 ] Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo, Urtzi Las Heras, Ryan Babbush, Austin G. Fowler, Brooks Campbell, Yu Chen y otros. Computación cuántica adiabática digitalizada con un circuito superconductor. Nature, 534 (7606): 222–226, junio de 2016. 10.1038 / nature17658.
https: / / doi.org/ 10.1038 / nature17658
[ 23 ] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt y Kristel Michielsen. Evaluación comparativa del algoritmo de optimización aproximada cuántica. Quantum Inf. Process., 19 (7): 197, junio de 2020. 10.1007 / s11128-020-02692-8.
https://doi.org/10.1007/s11128-020-02692-8
[ 24 ] Sergey Bravyi, Alexander Kliesch, Robert Koenig y Eugene Tang. Obstáculos a la optimización cuántica variacional de la protección de simetría. Phys. Rev. Lett., 125: 260505, diciembre de 2020a. 10.1103 / PhysRevLett.125.260505.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[ 25 ] Gavin E. Crooks. Rendimiento del algoritmo de optimización aproximada cuántica en el problema de corte máximo, 2018. URL https: / / arxiv.org/ abs / 1811.08419.
arXiv: 1811.08419
[ 26 ] Edward Farhi, Jeffrey Goldstone, Sam Gutmann y Hartmut Neven. Algoritmos cuánticos para arquitecturas qubit fijas, 2017. URL https: / / arxiv.org/ abs / 1703.06199.
arXiv: 1703.06199
[ 27 ] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor 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, febrero de 2019. 10.3390 / a12020034.
https: / / doi.org/ 10.3390 / a12020034
[ 28 ] Linghua Zhu, Ho Lun Tang, George S. Barron, Nicholas J. Mayhall, Edwin Barnes y Sophia E. Economou. Un algoritmo de optimización aproximada cuántica adaptativa para resolver problemas combinatorios en una computadora cuántica, 2020. URL https: / / arxiv.org/ abs / 2005.10258.
arXiv: 2005.10258
[ 29 ] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy y Eleanor G. Rieffel. Mezcladores XY: Resultados analíticos y numéricos para el operador de alternancia cuántica ansatz. Phys. Rev. A, 101: 012320, enero de 2020. 10.1103 / PhysRevA.101.012320.
https: / / doi.org/ 10.1103 / PhysRevA.101.012320
[ 30 ] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev y Prasanna Balaprakash. Aprender a optimizar circuitos cuánticos variacionales para resolver problemas combinatorios. Actas de la Conferencia AAAI sobre Inteligencia Artificial, 34 (03): 2367–2375, abril de 2020. 10.1609 / aaai.v34i03.5616.
https: / / doi.org/ 10.1609 / aaai.v34i03.5616
[ 31 ] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng y Giuseppe E. Santoro. Optimización cuántica asistida por refuerzo-aprendizaje. Phys. Rev. Research, 2: 033446, septiembre de 2020. 10.1103 / PhysRevResearch.2.033446.
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033446
[ 32 ] Ruslan Shaydulin, Ilya Safro y Jeffrey Larson. Métodos de arranque múltiple para la optimización aproximada cuántica. Conferencia de computación extrema de alto rendimiento IEEE 2019 (HPEC), páginas 1 a 8, septiembre de 2019. 10.1109 / HPEC.2019.8916288.
https: / / doi.org/ 10.1109 / HPEC.2019.8916288
[ 33 ] Ruslan Shaydulin y Yuri Alexeev. Evaluación del algoritmo de optimización aproximada cuántica: un estudio de caso. En 2019 Décima Conferencia Internacional de Computación Verde y Sostenible (IGSC), páginas 1 a 6, 2019. 10.1109 / IGSC48788.2019.8957201.
https: / / doi.org/ 10.1109 / IGSC48788.2019.8957201
[ 34 ] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim y Henry Yuen. Explorando el entrelazamiento y la optimización dentro del ansatz variacional hamiltoniano. PRX Quantum, 1: 020319, diciembre de 2020. 10.1103 / PRXQuantum.1.020319.
https: / / doi.org/ 10.1103 / PRXQuantum.1.020319
[ 35 ] Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann y Hartmut Neven. Para parámetros de control fijos, el valor de la función objetivo del algoritmo de optimización aproximada cuántica se concentra para instancias típicas, 2018. URL https: / / arxiv.org/ abs / 1812.04170.
arXiv: 1812.04170
[ 36 ] Matthew B. Hastings. Algoritmos clásicos y cuánticos de aproximación de profundidad acotada, 2019. URL https: / / arxiv.org/ abs / 1905.07047.
arXiv: 1905.07047
[ 37 ] Sergey Bravyi, Alexander Kliesch, Robert Koenig y Eugene Tang. Algoritmos híbridos cuánticos-clásicos para colorear gráficos aproximados, 2020b. URL https: // arxiv.org/ abs / 2011.13420.
arXiv: 2011.13420
[ 38 ] Mahabubul Alam, Abdullah Ash-Saki y Swaroop Ghosh. Análisis del algoritmo de optimización aproximada cuántica bajo ruido realista en qubits superconductores, 2019. URL https: / / arxiv.org/ abs / 1907.09631.
arXiv: 1907.09631
[ 39 ] Vishwanathan Akshay, Hariphan Philathong, Mauro ES Morales y Jacob D. Biamonte. Déficits de accesibilidad en la optimización de aproximación cuántica. Phys. Rev. Lett., 124: 090504, marzo de 2020a. 10.1103 / PhysRevLett.124.090504.
https: / / doi.org/ 10.1103 / PhysRevLett.124.090504
[ 40 ] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo y otros. Optimización cuántica aproximada de problemas de gráficos no planos en un procesador superconductor plano. Nat. Phys., 17 (3): 332–336, marzo de 2021. 10.1038 / s41567-020-01105-y.
https: / / doi.org/ 10.1038 / s41567-020-01105-y
[ 41 ] Yulong Dong, Xiang Meng, Lin Lin, Robert Kosut y K. Birgitta Whaley. Optimización de control robusto para algoritmos de optimización aproximada cuántica. IFAC-PapersOnLine, 53 (2): 242–249, 2020. 10.1016 / j.ifacol.2020.12.130. 21º Congreso Mundial de IFAC.
https: / / doi.org/ 10.1016 / j.ifacol.2020.12.130
[ 42 ] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo y otros. Mejora del rendimiento de los algoritmos de optimización cuántica profunda con conjuntos de puertas continuas. PRX Quantum, 1: 110304, octubre de 2020. 10.1103 / PRXQuantum.1.020304.
https: / / doi.org/ 10.1103 / PRXQuantum.1.020304
[ 43 ] Nathan Earnest, Caroline Tornow y Daniel J. Egger. Transpilación de circuitos de pulso eficiente para aplicaciones cuánticas en hardware basado en resonancia cruzada, 2021. URL https: / / arxiv.org/ abs / 2105.01063.
arXiv: 2105.01063
[ 44 ] Pranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, Yunong Shi y Frederic T. Chong. Compilación cuántica optimizada para algoritmos a corto plazo con openpulse, 2020. URL https: / / www.microarch.org/ micro53 / papers / 738300a186.pdf. 10.1109 / MICRO50266.2020.00027.
https: / / doi.org/ 10.1109 / MICRO50266.2020.00027
https: / / www.microarch.org/ micro53 / papers / 738300a186.pdf
[ 45 ] David C. McKay, Thomas Alexander, Luciano Bello, Michael J. Biercuk, Lev Bishop, Jiayin Chen, Jerry M. Chow, Antonio D. Córcoles, Daniel J. Egger, Stefan Filipp y otros. Especificaciones de backend de Qiskit para experimentos OpenQASM y OpenPulse, 2018. URL https: / / arxiv.org/ abs / 1809.03452.
arXiv: 1809.03452
[ 46 ] Thomas Alexander, Naoki Kanazawa, Daniel J. Egger, Lauren Capelluto, Christopher J. Wood, Ali Javadi-Abhari y David C. McKay. Qiskit pulse: programación de ordenadores cuánticos a través de la nube con pulsos. Ciencia cuántica. Technol., 5 (4): 044006, agosto de 2020. 10.1088 / 2058-9565 / aba404.
https: / / doi.org/ 10.1088 / 2058-9565 / aba404
[ 47 ] Anirudha Majumdar, Georgina Hall y Amir Ali Ahmadi. Mejoras de escalabilidad recientes para programación semidefinida con aplicaciones en aprendizaje automático, control y robótica. Annu. Rev. Robot de control. Auton. Syst., 3: 331–360, 2020. 10.1146 / annurev-control-091819-074326.
https: / / doi.org/ 10.1146 / annurev-control-091819-074326
[ 48 ] Miguel F. Anjos y Jean B. Lasserre. Manual sobre optimización semidefinida, cónica y polinomial, volumen 166. Springer Science & Business Media, 2011. 10.1007 / 978-1-4614-0769-0.
https://doi.org/10.1007/978-1-4614-0769-0
[ 49 ] Lenore Blum, Felipe Cucker, Michael Shub y Steve Smale. Complejidad y computación real. Springer Science & Business Media, 2012. 10.1007 / 978-1-4612-0701-6.
https://doi.org/10.1007/978-1-4612-0701-6
[ 50 ] Lorant Porkolab y Leonid Khachiyan. Sobre la complejidad de los programas semidefinidos. J. Glob. Optim., 10 (4): 351–365, 1997. 10.1023 / A: 1008203903341.
https: / / doi.org/ 10.1023 / A: 1008203903341
[ 51 ] Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell y Volkan Cevher. Programación semidefinida escalable. SIAM J. Math. Data Sci., 3 (1): 171-200, 2021. 10.1137 / 19M1305045.
https: / / doi.org/ 10.1137 / 19M1305045
[ 52 ] Prabhakar Raghavan y Clark D. Tompson. Redondeo aleatorio: una técnica para demostrar buenos algoritmos y pruebas algorítmicas. Combinatorica, 7 (4): 365–374, diciembre de 1987. 10.1007 / BF02579324.
https: / / doi.org/ 10.1007 / BF02579324
[ 53 ] Michel X. Goemans y David P. Williamson. Algoritmos de aproximación mejorados para problemas de máxima capacidad de corte y satisfacción mediante programación semidefinida. J. ACM, 42 (6): 1115-1145, noviembre de 1995. 10.1145 / 227683.227684.
https: / / doi.org/ 10.1145 / 227683.227684
[ 54 ] Howard Karloff. ¿Qué tan bueno es el algoritmo MAX CUT de Goemans – Williamson? SIAM J. Comput., 29 (1): 336-350, 1999. 10.1137 / S0097539797321481.
https: / / doi.org/ 10.1137 / S0097539797321481
[ 55 ] Subhash Khot, Guy Kindler, Elchanan Mossel y Ryan O'Donnell. ¿Resultados óptimos de inapropiabilidad para MAX-CUT y otros CSP de 2 variables? SIAM J. Comput., 37 (1): 319–357, 2007. 10.1137 / S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372
[ 56 ] Subhas Khot. Sobre la conjetura de los juegos únicos (encuesta invitada). En 2012 IEEE 27th Conference on Computational Complexity, páginas 99–121, Los Alamitos, CA, EE. UU., Junio de 2010. IEEE Computer Society. 10.1109 / CCC.2010.19.
https: / / doi.org/ 10.1109 / CCC.2010.19
[ 57 ] Subhash A. Khot y Nisheeth K. Vishnoi. La conjetura de juegos únicos, la brecha de integralidad para los problemas de corte y la capacidad de integración de métricas de tipo negativo en l1. J. ACM, 62 (1): 1–39, 2015. 10.1145 / 2629614.
https: / / doi.org/ 10.1145 / 2629614
[ 58 ] Kunal Marwaha. El algoritmo MAX-CUT clásico local supera a $ p = 2 $ QAOA en gráficos regulares de gran circunferencia. Quantum, 5: 437, abril de 2021. 10.22331 / q-2021-04-20-437.
https://doi.org/10.22331/q-2021-04-20-437
[ 59 ] Peter L. Hammer y Sergiu Rudeanu. Métodos booleanos en investigación de operaciones y áreas relacionadas. Springer Science & Business Media, 1968. 10.1007 / 978-3-642-85823-9.
https://doi.org/10.1007/978-3-642-85823-9
[ 60 ] Jean B. Lasserre. Una formulación MAX-CUT de programas 0/1. Oper. Res. Lett., 44 (2): 158 - 164, 2016. 10.1016 / j.orl.2015.12.014.
https: / / doi.org/ 10.1016 / j.orl.2015.12.014
[ 61 ] Panos M. Pardalos y Georg Schnitger. Verificar la optimalidad local en la programación cuadrática restringida es np-difícil. Oper. Res. Lett., 7 (1): 33–35, 1988. 10.1016 / 0167-6377 (88) 90049-1.
https://doi.org/10.1016/0167-6377(88)90049-1
[ 62 ] Kim Allemand, Komei Fukuda, Thomas M Liebling y Erich Steiner. Un caso polinomial de optimización cuadrática cero-uno sin restricciones. Matemáticas. Program., 91 (1): 49–52, 2001. 10.1007 / s101070100233.
https: / / doi.org/ 10.1007 / s101070100233
[ 63 ] Milan Hladík, Michal Černý y Miroslav Rada. Una nueva clase polinomialmente resoluble de problemas de optimización cuadrática con restricciones de caja. arXiv: 1911.10877, 2019. URL https: / / arxiv.org/ abs / 1911.10877.
arXiv: 1911.10877
[ 64 ] Jacek Gondzio y Andreas Grothey. Resolver problemas de planificación financiera no lineal con variables de decisión de $ 10 ^ 9 $ en arquitecturas masivamente paralelas. WIT Trans Modeling Simul., 43: 11, 2006. 10.2495 / CF060101.
https: / / doi.org/ 10.2495 / CF060101
[ 65 ] Svatopluk Poljak, Franz Rendl y Henry Wolkowicz. Una receta para la relajación semidefinida para la programación cuadrática (0, 1). J. Glob. Optim., 7 (1): 51–73, 1995. 10.1007 / BF01100205.
https: / / doi.org/ 10.1007 / BF01100205
[ 66 ] Joran Van Apeldoorn, András Gilyén, Sander Gribling y Ronald de Wolf. Solucionadores cuánticos de SDP: mejores límites superior e inferior. Quantum, 4: 230, 2020. 10.22331 / q-2020-02-14-230.
https://doi.org/10.22331/q-2020-02-14-230
[ 67 ] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore y Xiaodi Wu. Solucionadores Quantum SDP: grandes aceleraciones, optimización y aplicaciones para el aprendizaje cuántico. En el 46o Coloquio Internacional sobre Autómatas, Idiomas y Programación (ICALP 2019), volumen 132 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 27: 1–27: 14, Dagstuhl, Alemania, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-109-2. 10.4230 / LIPIcs.ICALP.2019.27.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
[ 68 ] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin y Chunhao Wang. Algoritmo sublineal de inspiración cuántica para resolver programación semidefinita de bajo rango. En el 45º Simposio Internacional sobre Fundamentos Matemáticos de la Ciencia de la Computación (MFCS 2020), volumen 170 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 23: 1–23: 15, Dagstuhl, Alemania, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik . ISBN 978-3-95977-159-7. 10.4230 / LIPIcs.MFCS.2020.23.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.23
[ 69 ] Jacek Gondzio. Inicio cálido del método primal-dual aplicado en el esquema del plano de corte. Matemáticas. Program., 83 (1-3): 125-143, 1998. 10.1007 / BF02680554.
https: / / doi.org/ 10.1007 / BF02680554
[ 70 ] Andrew Lucas. Ising formulaciones de muchos problemas NP. Parte delantera. Phys., 2: 5, 2014. 10.3389 / fphy.2014.00005.
https: / / doi.org/ 10.3389 / fphy.2014.00005
[ 71 ] Bas Lodewijks. Asignación de problemas de optimización np-hard y NP-complete a problemas de optimización binaria cuadráticos no restringidos. arXiv: 1911.08043, 2019. URL https: / / arxiv.org/ abs / 1911.08043.
arXiv: 1911.08043
[ 72 ] Jean B. Lasserre. Optimización global con polinomios y el problema de los momentos. SIAM J. Optim., 11 (3): 796–817, 2001. 10.1137 / S1052623400366802.
https: / / doi.org/ 10.1137 / S1052623400366802
[ 73 ] Jean B. Lasserre. Relajaciones SDP convergentes en optimización polinomial con escasez. SIAM J. Optim., 17 (3): 822–843, 2006. 10.1137 / 05064504X.
https: / / doi.org/ 10.1137 / 05064504X
[ 74 ] Bissan Ghaddar, Juan C. Vera y Miguel F. Anjos. Relajaciones de cono de segundo orden para programas polinomiales cuadráticos binarios. SIAM J. Optim., 21 (1): 391–414, 2011. 10.1137 / 100802190.
https: / / doi.org/ 10.1137 / 100802190
[ 75 ] Moses Charikar y Anthony Wirth. Maximizar programas cuadráticos: extender la desigualdad de Grothendieck. En el 45º Simposio anual del IEEE sobre fundamentos de la informática, páginas 54–60. IEEE, 2004. 10.1109 / FOCS.2004.39.
https: / / doi.org/ 10.1109 / FOCS.2004.39
[ 76 ] Mikhail Krechetov, Jakub Mareček, Yury Maximov y Martin Takáč. Programación semidefinida penalizada por entropía. En Actas de la Vigésima Octava Conferencia Conjunta Internacional sobre Inteligencia Artificial, 2019. 10.24963 / ijcai.2019 / 157.
https: / / doi.org/ 10.24963 / ijcai.2019 / 157
[ 77 ] Sartaj Sahni y Teófilo González. P-problemas de aproximación completa. J. ACM, 23 (3): 555-565, 1976. 10.1145 / 321958.321975. Ver el lema A2.
https: / / doi.org/ 10.1145 / 321958.321975
[ 78 ] Michael Mitzenmacher y Eli Upfal. Probabilidad y computación: Aleatorización y técnicas probabilísticas en algoritmos y análisis de datos. Prensa de la universidad de Cambridge, 2017.
[ 79 ] Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz y Mohit Singh. Redondeo browniano pegajoso y sus aplicaciones para restringir los problemas de satisfacción. En Actas del decimocuarto simposio anual ACM-SIAM sobre algoritmos discretos, páginas 854–873. SIAM, 2020. 10.1137 / 1.9781611975994.52.
https: / / doi.org/ 10.1137 / 1.9781611975994.52
[ 80 ] Ronen Eldan y Assaf Naor. Las difusiones de Krivine alcanzan la relación de aproximación de goemans-williamson. arXiv: 1906.10615, 2019. URL https: / / arxiv.org/ abs / 1906.10615.
arXiv: 1906.10615
[ 81 ] Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tantipongpipat y Santosh Vempala. Reducción justa de la dimensionalidad y redondeo iterativo para los SDP. arXiv: 1902.11281, 2019. URL https: / / arxiv.org/ abs / 1902.11281v1.
arXiv: 1902.11281
[ 82 ] Samuel Karlin y Howard E. Taylor. Un segundo curso en procesos estocásticos. Elsevier, 1981. pág. 257 y siguientes.
[ 83 ] Julia Kempe, Oded Regev y Ben Toner. La conjetura de los juegos únicos con probadores entrelazados es falsa. En Métodos algebraicos en complejidad computacional, 2007.
[ 84 ] Julia Kempe, Oded Regev y Ben Toner. Los juegos únicos con probadores enredados son fáciles. SIAM J. Comput., 39 (7): 3207–3229, 2010. 10.1137 / 090772885.
https: / / doi.org/ 10.1137 / 090772885
[ 85 ] Charles H. Bennett, Ethan Bernstein, Gilles Brassard y Umesh Vazirani. Fortalezas y debilidades de la computación cuántica. SIAM J. Comput., 26 (5): 1510-1523, 1997. 10.1137 / S0097539796300933.
https: / / doi.org/ 10.1137 / S0097539796300933
[ 86 ] Harry Markowitz. Selección de cartera. J. Finance, 7 (1): 77–91, 1952. 10.2307 / 2975974.
https: / / doi.org/ 10.2307 / 2975974
[ 87 ] H. Abraham y col. Qiskit: un marco de código abierto para la computación cuántica, 2019. URL https: / / doi.org/ 10.5281 / zenodo.2562111.
https: / / doi.org/ 10.5281 / zenodo.2562111
[ 88 ] Johan Håstad. Algunos resultados óptimos de inaproximación. J. ACM, 48 (4): 798–859, 2001. 10.1145 / 502090.502098.
https: / / doi.org/ 10.1145 / 502090.502098
[ 89 ] Vishwanathan Akshay, Hariphan Philathong, Igor Zacharov y Jacob D. Biamonte. Déficits de accesibilidad implícitos en la optimización aproximada cuántica de problemas de gráficos de Google, 2020b. URL https: / / arxiv.org/ abs / 2007.09148.
arXiv: 2007.09148
[ 90 ] Rebekah Herrman, James Ostrowski, Travis S. Humble y George Siopsis. Límites inferiores en la profundidad del circuito del algoritmo de optimización aproximada cuántica. Quantum Inf. Process., 20 (2): 59, febrero de 2021. 10.1007 / s11128-021-03001-7.
https://doi.org/10.1007/s11128-021-03001-7
[ 91 ] Zhihui Wang, Stuart Hadfield, Zhang Jiang y Eleanor G. Rieffel. Algoritmo de optimización aproximada cuántica para maxcut: una vista fermiónica. Phys. Rev. A, 97: 022304, febrero de 2018. 10.1103 / PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
[ 92 ] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler y Mikhail D. Lukin. Algoritmo de optimización aproximada cuántica: rendimiento, mecanismo e implementación en dispositivos a corto plazo. Phys. Rev. X, 10: 021067, junio de 2020. 10.1103 / PhysRevX.10.021067.
https: / / doi.org/ 10.1103 / PhysRevX.10.021067
[ 93 ] Jason Larkin, Matías Jonsson, Daniel Justice y Gian Giacomo Guerreschi. Evaluación del algoritmo de optimización aproximada cuántica basado en la relación de aproximación de muestras individuales, 2020. URL https: / / arxiv.org/ abs / 2006.04831.
arXiv: 2006.04831
[ 94 ] qiskit-optimización. https: / / github.com/ Qiskit / qiskit-optimization. Consultado: 25.
https: / / github.com/ Qiskit / qiskit-optimization
[ 95 ] Andreas Bärtschi y Stephan Eidenbenz. Mezcladores Grover para qaoa: Cambiando la complejidad del diseño del mezclador a la preparación del estado. En 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), páginas 72–82, 2020. 10.1109 / QCE49297.2020.00020.
https: / / doi.org/ 10.1109 / QCE49297.2020.00020
[ 96 ] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler y Swati Gupta. Uniendo lo clásico y lo cuántico con SDP inicializados en caliente para QAOA, 2020. URL https: / / arxiv.org/ abs / 2010.14021.
arXiv: 2010.14021
[ 97 ] Iain Dunning, Swati Gupta y John Silberholz. ¿Qué funciona mejor cuando? una evaluación sistemática de heurísticas para Max-Cut y QUBO. INFORMA J. Comput., 30 (3): 608–624, 2018. 10.1287 / ijoc.2017.0798.
https: / / doi.org/ 10.1287 / ijoc.2017.0798
[ 98 ] Panagiotis Kl. Barkoutsos, Jerome F. Gonthier, Igor Sokolov, Nikolaj Moll, Gian Salis, Andreas Fuhrer, Marc Ganzhorn, Daniel J. Egger, Matthias Troyer, Antonio Mezzacapo y otros. Algoritmos cuánticos para cálculos de estructuras electrónicas: expansiones de función de onda optimizadas y hamiltonianas de agujeros de partículas Phys. Rev. A, 98: 022322, agosto de 2018. 10.1103 / PhysRevA.98.022322.
https: / / doi.org/ 10.1103 / PhysRevA.98.022322
[ 99 ] Sanjeev Arora y Shmuel Safra. Comprobación probabilística de demostraciones: una nueva caracterización de np. J. ACM, 45 (1): 70-122, 1998. 10.1145 / 273865.273901.
https: / / doi.org/ 10.1145 / 273865.273901
[ 100 ] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan y Mario Szegedy. Comprobación de pruebas y dureza de problemas de aproximación. J. ACM, 45 (3): 501–555, 1998. 10.1145 / 278298.278306.
https: / / doi.org/ 10.1145 / 278298.278306
[ 101 ] Irit Dinur. El teorema de PCP por amplificación de gap. J. ACM, 54 (3): 12 – es, junio de 2007. 10.1145 / 1236457.1236459.
https: / / doi.org/ 10.1145 / 1236457.1236459
[ 102 ] Sanjeev Arora y Boaz Barak. Complejidad computacional: un enfoque moderno. Prensa de la Universidad de Cambridge, 2009.
[ 103 ] Subhash Khot. Sobre el poder de los juegos únicos de 2 pruebas y 1 ronda. En Actas del Trigésimo Cuarto Simposio Anual de ACM sobre Teoría de la Computación, STOC '02, páginas 767–775, Nueva York, NY, EE. UU., 2002. Association for Computing Machinery. 10.1145 / 509907.510017.
https: / / doi.org/ 10.1145 / 509907.510017
[ 104 ] Prasad Raghavendra. ¿Algoritmos óptimos y resultados inapropiados para cada CSP? En Actas del cuadragésimo simposio anual de ACM sobre teoría de la computación, páginas 245–254, 2008. 10.1145 / 1374376.1374414.
https: / / doi.org/ 10.1145 / 1374376.1374414
[ 105 ] Prasad Raghavendra y David Steurer. Cómo redondear cualquier CSP. En 2009, 50º Simposio Anual del IEEE sobre los fundamentos de la informática, páginas 586–594, 2009. 10.1109 / FOCS.2009.74.
https: / / doi.org/ 10.1109 / FOCS.2009.74
[ 106 ] Subhash Khot, Dor Minzer y Muli Safra. Los conjuntos pseudoaleatorios en el gráfico de Grassmann tienen una expansión casi perfecta. En Actas del quincuagésimo noveno Simposio anual sobre los fundamentos de la informática (FOCS), páginas 592–601, 2018. 10.1109 / FOCS.2018.00062.
https: / / doi.org/ 10.1109 / FOCS.2018.00062
[ 107 ] Boaz Barak, Prasad Raghavendra y David Steurer. Redondeo de jerarquías de programación semidefinidas mediante correlación global. En Actas del quincuagésimo segundo simposio anual sobre los fundamentos de la informática, páginas 472–481. IEEE, 2011. 10.1109 / FOCS.2011.95.
https: / / doi.org/ 10.1109 / FOCS.2011.95
[ 108 ] Samuel B. Hopkins, Tselil Schramm y Luca Trevisan. Los LPs subexponenciales se aproximan al corte máximo. En Actas del sexagésimo primer Simposio anual sobre fundamentos de la informática (FOCS), páginas 943–953. IEEE, 2020. 10.1109 / FOCS46700.2020.00092.
https: / / doi.org/ 10.1109 / FOCS46700.2020.00092
[ 109 ] Albert Einstein, Boris Podolsky y Nathan Rosen. ¿Se puede considerar completa la descripción de la mecánica cuántica de la realidad física? Phys. Rev., 47 (10): 777, 1935. 10.1103 / PhysRev.47.777.
https: / / doi.org/ 10.1103 / PhysRev.47.777
[ 110 ] Boris S. Cirel'son. Generalizaciones cuánticas de la desigualdad de Bell. Letón. Matemáticas. Phys., 4 (2): 93-100, 1980. 10.1007 / BF00417500.
https: / / doi.org/ 10.1007 / BF00417500
[ 111 ] A. Natarajan y T. Vidick. Pruebas de bajo grado para estados cuánticos y un PCP de juegos entrelazados cuánticos para QMA. En Actas del quincuagésimo noveno Simposio anual sobre fundamentos de la informática (FOCS), páginas 731–742, 2018. 10.1109 / FOCS.2018.00075.
https: / / doi.org/ 10.1109 / FOCS.2018.00075
[ 112 ] Dorit Aharonov, Itai Arad, Zeph Landau y Umesh Vazirani. El lema de detectabilidad y la amplificación de la brecha cuántica. En Actas del cuadragésimo primer simposio anual de ACM sobre teoría de la computación, STOC '09, páginas 417–426, Nueva York, NY, EE. UU., 2009. Association for Computing Machinery. ISBN 9781605585062. 10.1145 / 1536414.1536472.
https: / / doi.org/ 10.1145 / 1536414.1536472
[ 113 ] Moses Charikar, Konstantin Makarychev y Yury Makarychev. Algoritmos casi óptimos para juegos únicos. En Actas del trigésimo octavo simposio anual de ACM sobre teoría de la computación, páginas 205–214, 2006. 10.1145 / 1132516.1132547.
https: / / doi.org/ 10.1145 / 1132516.1132547
[ 114 ] Dimitris Achlioptas, Assaf Naor y Yuval Peres. Ubicación rigurosa de las transiciones de fase en problemas de optimización difíciles. Nature, 435 (7043): 759–764, 2005. 10.1038 / nature03602.
https: / / doi.org/ 10.1038 / nature03602
[ 115 ] Don Coppersmith, David Gamarnik, Mohammad T. Hajiaghayi y Gregory B. Sorkin. MAX SAT aleatorio, MAX CUT aleatorio y sus transiciones de fase. Estructura aleatoria. Algoritmos, 24 (4): 502-545, 2004. 10.1002 / rsa.20015.
https: / / doi.org/ 10.1002 / rsa.20015
Citado por
[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong- Chuan Kwek y Alán Aspuru-Guzik, “Algoritmos cuánticos ruidosos de escala intermedia (NISQ)”, arXiv: 2101.08448.
[2] Austin Gilliam, Stefan Woerner y Constantin Gonciulea, "Búsqueda adaptativa de Grover para la optimización binaria polinómica restringida", arXiv: 1912.04088.
[3] Sergey Bravyi, Alexander Kliesch, Robert Koenig y Eugene Tang, "Algoritmos clásicos cuánticos híbridos para colorear gráficos aproximados", arXiv: 2011.13420.
[4] Amir M Aghaei, Bela Bauer, Kirill Shtengel y Ryan V. Mishmash, "Preparación eficiente de la matriz-producto-estado de los estados de prueba altamente entrelazados: aisladores Mott débiles en la celosía triangular revisados", arXiv: 2009.12435.
[5] Stefan H. Sack y Maksym Serbyn, "Inicialización de recocido cuántico del algoritmo de optimización aproximada cuántica", arXiv: 2101.05742.
[6] M. Werninghaus, DJ Egger y S. Filipp, "Calibración y caracterización de alta velocidad de procesadores cuánticos superconductores sin reinicio de Qubit", PRX Cuántico 2 2, 020324 (2021).
[7] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron y Margarita Veshchezerova, “Calificando enfoques cuánticos para problemas difíciles de optimización industrial. Un caso de estudio en el campo de la carga inteligente de vehículos eléctricos ”, arXiv: 2012.14859.
[8] Sami Boulebnane, "Mejora del algoritmo de optimización aproximada cuántica con postselección", arXiv: 2011.05425.
[9] Stuart M. Harwood, Dimitar Trenev, Spencer T. Stober, Panagiotis Barkoutsos, Tanvi P. Gujarati y Sarah Mostame, "Mejorando el eigensolver cuántico variacional usando computación cuántica adiabática variacional", arXiv: 2102.02875.
[10] Johanna Barzen, "De las humanidades digitales a las humanidades cuánticas: potenciales y aplicaciones", arXiv: 2103.11825.
[11] Jonathan Wurtz y Peter Love, "Algoritmos cuánticos variacionales óptimos clásicos", arXiv: 2103.17065.
[12] Ioannis Kolotouros y Petros Wallden, "Una función objetivo en evolución para mejorar la optimización cuántica variacional", arXiv: 2105.11766.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2021-06-17 13:56:21). 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-06-17 13:56:19: No se pudieron obtener los datos citados por 10.22331 / q-2021-06-17-479 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.
Coinsmart. Mejor Bitcoin-Börse en Europa
Fuente: https://quantum-journal.org/papers/q-2021-06-17-479/
