Warm gestartetes QAOA mit benutzerdefinierten Mischern konvergiert nachweislich und übertrifft rechnerisch Goemans-Williamsons Max-Cut bei geringen Schaltkreistiefen

Warm gestartetes QAOA mit benutzerdefinierten Mischern konvergiert nachweislich und übertrifft rechnerisch Goemans-Williamsons Max-Cut bei geringen Schaltkreistiefen

Reuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3 und Swati Gupta4

1CCS-3 Informationswissenschaften, Los Alamos National Laboratory, Los Alamos, NM 87544, USA
2Georgia Institute of Technology, Atlanta, GA 30332, USA
3Georgia Tech Research Institute, Atlanta, GA 30332, USA
4Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02142, USA

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Wir verallgemeinern den Quantum Approximate Optimization Algorithm (QAOA) von Farhi et al. (2014), um beliebige trennbare Anfangszustände mit entsprechenden Mischern zu ermöglichen, sodass der Startzustand der am stärksten angeregte Zustand des mischenden Hamilton-Operators ist. Wir demonstrieren diese Version von QAOA, die wir $QAOA-warmest$ nennen, durch die Simulation von Max-Cut auf gewichteten Diagrammen. Wir initialisieren den Startzustand als $Warmstart$ unter Verwendung von $2$- und $3$-dimensionalen Näherungen, die wir mithilfe randomisierter Projektionen von Lösungen für das semidefinite Programm von Max-Cut erhalten, und definieren einen vom Warmstart abhängigen $Custom Mixer$. Wir zeigen, dass diese Warmstarts die QAOA-Schaltung mit konstanten Approximationen von 0.658 $ für $2-dimensionale und 0.585 $ für $3$-dimensionale Warmstarts für Graphen mit nicht negativen Kantengewichten initialisieren und damit eine Verbesserung gegenüber bisher bekannten trivialen ( d. h. $0.5$ für die Standardinitialisierung) Worst-Case-Grenzen bei $p=0$. Diese Faktoren begrenzen tatsächlich die für Max-Cut bei höheren Schaltkreistiefen erzielte Näherung nach unten, da wir auch zeigen, dass QAOA-warmest mit jedem separierbaren Anfangszustand unter der adiabatischen Grenze als $prightarrow infty$ zu Max-Cut konvergiert. Allerdings hat die Wahl der Warmstarts einen erheblichen Einfluss auf die Konvergenzrate zu Max-Cut, und wir zeigen empirisch, dass unsere Warmstarts im Vergleich zu bestehenden Ansätzen eine schnellere Konvergenz erreichen. Darüber hinaus zeigen unsere numerischen Simulationen qualitativ hochwertigere Schnitte im Vergleich zum Standard-QAOA, dem klassischen Goemans-Williamson-Algorithmus und einem warm gestarteten QAOA ohne benutzerdefinierte Mixer für eine Instanzbibliothek mit Diagrammen im Wert von 1148 $ (bis zu 11 $ Knoten) und einer Tiefe von p = 8 $. Wir zeigen weiterhin, dass QAOA-warmest das Standard-QAOA von Farhi et al. übertrifft. in Experimenten auf aktueller IBM-Q- und Quantinuum-Hardware.

Der Quantennäherungsoptimierungsalgorithmus (QAOA) ist eine hybride quantenklassische Technik zur kombinatorischen Optimierung, die leistungsfähiger zu sein verspricht als jeder klassische Optimierer. In dieser Arbeit veranschaulichen wir sein Potenzial anhand eines grundlegenden kombinatorischen Optimierungsproblems, bekannt als Max-Cut, bei dem der bestmögliche klassische Algorithmus der von Goemans und Williamson (GW) ist. Wir erreichen dies, indem wir klassisch erhaltene Warmstarts mit modifizierten Mischoperatoren in die QAOA einführen und zeigen rechnerisch, dass dies GW übertrifft. Wir modifizieren den Quantenalgorithmus entsprechend, um die Verbindung zum quantenadiabatischen Rechnen aufrechtzuerhalten; Wir diskutieren die Theorie und liefern numerische und experimentelle Beweise, die die Erfolgsaussichten unseres Ansatzes belegen.

► BibTeX-Daten

► Referenzen

[1] John Preskill. „Quantencomputing in der NISQ-Ära und darüber hinaus“. Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow und Ashley Montanaro. „Quantenberechnungsüberlegenheit“. Natur 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Edward Farhi, Jeffrey Goldstone und Sam Gutmann. „Ein Quantennäherungsoptimierungsalgorithmus“ (2014).

[4] Iain Dunning, Swati Gupta und John Silberholz. „Was funktioniert wann am besten? Eine systematische Auswertung von Heuristiken für Max-Cut und QUBO“. INFORMS Journal on Computing 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[5] Michel X Goemans und David P Williamson. „Verbesserte Approximationsalgorithmen für Maximum Cut- und Erfüllbarkeitsprobleme mithilfe semidefiniter Programmierung“. Journal of the ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[6] Samuel Burer und Renato DC Monteiro. „Ein nichtlinearer Programmieralgorithmus zum Lösen semidefiniter Programme durch Faktorisierung mit niedrigem Rang“. Mathematische Programmierung 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: Ein Open-Source-Framework für Quantencomputing“ (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard und Eugene Tang. „Ausgehend von einer guten klassischen Saite bleibt die QAOA stecken“ (2022).

[9] Daniel J. Egger, Jakub Mareček und Stefan Woerner. „Warmstartende Quantenoptimierung“. Quantum 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H. Sack, Raimel A. Medina, Richard Kueng und Maksym Serbyn. „Rekursive gierige Initialisierung des Quantennäherungsoptimierungsalgorithmus mit garantierter Verbesserung“. Physical Review A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[11] Stefan H. Sack und Maksym Serbyn. „Quantum Annealing-Initialisierung des Quantennäherungsoptimierungsalgorithmus“. Quantum 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler und Mikhail D Lukin. „Quantennäherungsoptimierungsalgorithmus: Leistung, Mechanismus und Implementierung auf kurzfristigen Geräten“. Körperliche Überprüfung X 10, 021067 (2020).
https://doi.org/ 10.1103/PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski und Travis S. Humble. „Parameterübertragung zur quantennähernden Optimierung des gewichteten Maxcut“. ACM-Transaktionen zum Quantencomputing 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[14] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev und Ilya Safro. „Übertragbarkeit optimaler QAOA-Parameter zwischen Zufallsgraphen“. Im Jahr 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Seiten 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 und Daniel J Egger. „Skalierung des Quantennäherungsoptimierungsalgorithmus auf supraleitender Qubit-basierter Hardware“. Quantum 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 und Travis S. Humble. „Skalierung der Quantennäherungsoptimierung auf kurzfristiger Hardware“. Wissenschaftliche Berichte 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

[17] Gian Giacomo Guerreschi und Anne Y Matsuura. „QAOA für Max-Cut erfordert Hunderte von Qubits für die Quantenbeschleunigung.“ Wissenschaftliche Berichte 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra und Vedran Dunjko. „Zu Quanten oder nicht zu Quanten: Auf dem Weg zur Algorithmusauswahl in der kurzfristigen Quantenoptimierung“. Quantenwissenschaft und -technologie 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell und Edward Dahl. „QAOA auf höchstem Niveau“. Im Jahr 2022 findet die 19. Internationale IEEE-Konferenz zum Software Architecture Companion (ICSA-C) statt. Seiten 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 und George Siopsis. „Auswirkungen von Graphstrukturen für QAOA auf maxcut“. Quanteninformationsverarbeitung 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​und Daniel J Egger. „Squeezing und Quantennäherungsoptimierung“ (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg und Ilya Safro. „Klassische Symmetrien und der Quantennäherungsoptimierungsalgorithmus“. Quanteninformationsverarbeitung 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz und Peter Love. „Leistungsgarantien des Maxcut-Quantennäherungsoptimierungsalgorithmus für p>1“. Physical Review A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone und Sam Gutmann. „Quantenalgorithmen für feste Qubit-Architekturen“ (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig und Eugene Tang. „Hindernisse für die Variationsquantenoptimierung durch Symmetrieschutz“. Physical Review Letters 125, 260505 (2020).
https://doi.org/ 10.1103/PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik und Sam Gutmann. „Der Quantennäherungsoptimierungsalgorithmus muss das gesamte Diagramm sehen: Ein typischer Fall“ (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig und Eugene Tang. „Hybride quantenklassische Algorithmen zur ungefähren Graphenfärbung“. Quantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B. Hastings. „Klassische und quantenbeschränkte Tiefennäherungsalgorithmen“ (2019).

[29] Kunal Marwaha. „Der lokale klassische Max-Cut-Algorithmus übertrifft $ p= 2$ QAOA bei regulären Diagrammen mit hohem Umfang.“ Quantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak und Kunal Marwaha. „Klassische Algorithmen und Quantenbeschränkungen für den maximalen Schnitt auf Graphen mit hohem Umfang“ (2021).
https: // doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler und Swati Gupta. „Überbrückung von Klassik und Quantentechnologie mit SDP-initialisierten Warmstarts für QAOA“. ACM-Transaktionen zum Quantencomputing (2022).
https: / / doi.org/ 10.1145 / 3549554

[32] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli und Rupak Biswas. „Vom Quantennäherungsoptimierungsalgorithmus zum Quantenalternierungsoperatoransatz“. Algorithmen 12 (2019).
https: // doi.org/ 10.3390 / a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy und Eleanor G. Rieffel. „$xy$-Mischer: Analytische und numerische Ergebnisse für den Quantenalternierungsoperator-Ansatz“. Physik. Rev. A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

[34] Linghua Zhu, Ho Lun Tang, George S. Barron, FA Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes und Sophia E. Economou. „Adaptiver Quantennäherungsoptimierungsalgorithmus zur Lösung kombinatorischer Probleme auf einem Quantencomputer“. Physik. Rev. Research 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Andreas Bärtschi und Stephan Eidenbenz. „Grover-Mischer für QAOA: Verlagerung der Komplexität vom Mischerdesign zur Zustandsvorbereitung“. Im Jahr 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Seiten 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G. Rieffel und Zhihui Wang. „Nahezu optimale Quantenschaltung für Grovers unstrukturierte Suche unter Verwendung eines transversalen Feldes“. Physical Review A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Lov K. Grover. „Ein schneller quantenmechanischer Algorithmus für die Datenbanksuche“. In den Proceedings des achtundzwanzigsten jährlichen ACM-Symposiums zur Theorie des Rechnens. Seiten 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Yin Zhang, Samuel Burer und Renato DC Monteiro. „Rang-2-Relaxationsheuristik für Max-Cut- und andere binäre quadratische Programme“. SIAM Journal on Optimization 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari und Roberto Imbuzeiro Oliveira. „Sdps für Synchronisations- und Maxcut-Probleme über die Grothendieck-Ungleichung lösen“. In Konferenz zur Lerntheorie. Seiten 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh und Kevin Thompson. „Eine optimale Produktzustandsnäherung für 2-lokale Quanten-Hamiltonianer mit positiven Termen“ (2022). arXiv:2206.08342.
arXiv: 2206.08342

[41] Reuben Tate und Swati Gupta. „Ci-qube“. GitHub-Repository (2021). URL: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] Howard Karloff. „Wie gut ist der Goemans-Williamson MAX-CUT-Algorithmus?“ SIAM Journal on Computing 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. „Quantennäherungsoptimierung nichtplanarer Graphenprobleme auf einem planaren supraleitenden Prozessor“. Nature Physics 17, 332–336 (2021).
https: / / doi.org/ 10.1038 / s41567-020-01105-y

[44] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay und Jay M. Gambetta. „Abschwächung von Messfehlern in Multiqubit-Experimenten“. Physik. Rev. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[45] George S. Barron und Christopher J. Wood. „Messfehlerminderung für Variationsquantenalgorithmen“ (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 und Xiaoqiang Zheng. „TensorFlow: Groß angelegtes maschinelles Lernen auf heterogenen Systemen“ (2015).

[47] Diederik P. Kingma und Jimmy Ba. „Adam: Eine Methode zur stochastischen Optimierung“ (2014).

[48] Roger Fletcher. „Praktische Methoden der Optimierung (2. Auflage)“. John Wiley und Söhne. New York, NY, USA (1987).
https: / / doi.org/ 10.1002 / 9781118723203

[49] MJD Powell. „Eine direkte Suchoptimierungsmethode, die die Ziel- und Einschränkungsfunktionen durch lineare Interpolation modelliert.“ Fortschritte in der Optimierung und numerischen Analyse 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] Alan J. Laub. „Matrixanalyse für Wissenschaftler und Ingenieure“. Band 91. Siam. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907

[51] Georg Frobenius. „Über Matrizen aus nicht negativen Elementen“. Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften, Seiten 456–477 (1912).

[52] A. Kaveh und H. Rahami. „Eine einheitliche Methode zur Eigenzerlegung von Graphprodukten“. Kommunikation in numerischen Methoden im Ingenieurwesen mit biomedizinischen Anwendungen 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Špacapan. „Konnektivität kartesischer Produkte von Graphen“. Angewandte Mathematikbriefe 21, 682–685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

[54] Jacek Gondzio und Andreas Grothey. „Lösen nichtlinearer Finanzplanungsprobleme mit 109 Entscheidungsvariablen auf massiv parallelen Architekturen“. WIT-Transaktionen zur Modellierung und Simulation 43 (2006).
https://​/​doi.org/​10.2495/​CF060101

[55] Fan RK Chung. „Spektralgraphentheorie“. Band 92. American Mathematical Soc. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] MA Nielsen und IL Chuang. „Quantenberechnung und Quanteninformation: 10-jährige Jubiläumsausgabe“. Cambridge University Press, New York. (2011).
https: / / doi.org/ 10.1017 / CBO9780511976667

[57] Vincent R. Pascuzzi, Andre He, Christian W. Bauer, Wibe A. de Jong und Benjamin Nachman. „Rechnerisch effiziente Null-Rausch-Extrapolation zur Quanten-Gate-Fehlerminderung“. Physical Review A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala und Kristan Temme. „Probabilistische Fehlerkompensation mit spärlichen Pauli-Lindblad-Modellen auf verrauschten Quantenprozessoren“. Nature PhysicsSeiten 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick und Frédéric Roupin. „BiqCrunch: Eine semidefinite Branch-and-Bound-Methode zur Lösung binärer quadratischer Probleme“. ACM-Transaktionen auf mathematischer Software 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer und Matt McGinnis. „Die kleinsten Eigenwerte von Hamming-Graphen, Johnson-Graphen und anderen abstandsregulären Graphen mit klassischen Parametern“. Journal of Combinatorial Theory, Reihe B 133, 88–121 (2018).
https: // doi.org/ 10.1016 / j.jctb.2018.04.005

[61] Donald Knuth. „Kombinatorische Matrizen“. Ausgewählte Artikel zur diskreten Mathematik (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Zitiert von

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner und Daniel J. Egger, „Skalierung des Quantennäherungsoptimierungsalgorithmus auf supraleitender Qubit-basierter Hardware“, Quantum 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun und Marco Pistoia, „Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Portfolio Optimization“, arXiv: 2305.03857, (2023).

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

[4] Andrew Vlasic, Salvatore Certo und Anh Pham, „Complement Grover's Search Algorithm: An Amplitude Suppression Implementation“, arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele und Procolo Lucignano, „Convergence of Digitalized-Counterdiabatic QAOA: Circuit Depth versus Free Parameters“, arXiv: 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble und Creston D. Herold, „Modellierung von Rauschen in globalen Mølmer-Sørensen-Wechselwirkungen angewendet auf die Quantennäherungsoptimierung“, Physische Überprüfung A 107 6, 062406 (2023).

[7] Guoming Wang, „Klassisch verstärkter Quantenoptimierungsalgorithmus“, arXiv: 2203.13936, (2022).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 09:27:01 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-09-27 01:31:17).

Zeitstempel:

Mehr von Quantenjournal