Varmstartad QAOA med anpassade mixers konvergerar bevisligen och beräkningsmässigt slår Goemans-Williamsons Max-Cut vid låga kretsdjup

Varmstartad QAOA med anpassade mixers konvergerar bevisligen och beräkningsmässigt slår Goemans-Williamsons Max-Cut vid låga kretsdjup

Tidsstämpel: 26 september, 2023 9:22

Reuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3och Swati Gupta4

1CCS-3 Information Sciences, 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

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Vi generaliserar Quantum Approximate Optimization Algorithm (QAOA) av Farhi et al. (2014) för att tillåta godtyckliga separerbara initiala tillstånd med motsvarande blandare så att starttillståndet är det mest exciterade tillståndet för den blandade Hamiltonian. Vi demonstrerar denna version av QAOA, som vi kallar $QAOA-warmest$, genom att simulera Max-Cut på viktade grafer. Vi initierar starttillståndet som en $warm-start$ med hjälp av $2$ och $3$-dimensionella approximationer erhållna med hjälp av randomiserade projektioner av lösningar till Max-Cuts semi-definita program, och definierar en varmstartberoende $custom mixer$. Vi visar att dessa varmstarter initierar QAOA-kretsen med konstantfaktoruppskattningar på $0.658$ för $2$-dimensionella och $0.585$ för $3$-dimensionella varmstarter för grafer med icke-negativa kantvikter, vilket förbättras jämfört med tidigare kända triviala ( dvs $0.5$ för standardinitiering) gränser i värsta fall till $p=0$. Dessa faktorer sänker faktiskt den approximation som uppnås för Max-Cut vid högre kretsdjup, eftersom vi också visar att QAOA-varmaste med något separerbart initialtillstånd konvergerar till Max-Cut under den adiabatiska gränsen som $prightarrow infty$. Valet av varmstarter påverkar dock avsevärt graden av konvergens till Max-Cut, och vi visar empiriskt att våra varmstarter uppnår en snabbare konvergens jämfört med befintliga tillvägagångssätt. Dessutom visar våra numeriska simuleringar högre kvalitetssnitt jämfört med standard QAOA, den klassiska Goemans-Williamson-algoritmen och en varmstartad QAOA utan anpassade mixers för ett instansbibliotek med $1148$-grafer (upp till $11$-noder) och djup $p=8 $. Vi visar vidare att QAOA-varmast överträffar standard QAOA från Farhi et al. i experiment på nuvarande IBM-Q och Quantinuum hårdvara.

Varmstartad QAOA med anpassade mixers konvergerar bevisligen och beräkningsmässigt slår Goemans-Williamsons Max-Cut vid låga kretsdjup PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Utvald bild: Prestanda för QAOA-varmaste (med varmstarter) och standard QAOA som funktion av QAOA-djup för en idealisk (streckad) och bullrig simulering (prickad). För den valda 20-nodsgrafen uppnår GW ett approximationsförhållande på 0.912, medan QAOA-varmaste i det ideala fallet överträffar GW för $p geq 2$ medan standard QAOA kräver $p > 4$. Brussimuleringen är baserad på kalibreringsdata från IBM-Qs Guadalupe-enhet.

Populär sammanfattning

Quantum approximate optimization algorithm (QAOA) är en hybrid kvantklassisk teknik för kombinatorisk optimering som lovar att vara mer kraftfull än någon klassisk optimerare. I detta arbete exemplifierar vi dess potential på ett grundläggande kombinatoriskt optimeringsproblem, känt som Max-Cut, där den bästa möjliga klassiska algoritmen är den av Goemans och Williamson (GW). Vi uppnår detta genom att introducera klassiskt erhållna varmstarter till QAOA, med modifierade blandningsoperatorer, och visar beräkningsmässigt att detta överträffar GW. Vi modifierar kvantalgoritmen på lämpligt sätt för att upprätthålla kopplingen till kvantadiabatisk beräkning; vi diskuterar teori och tillhandahåller numeriska och experimentella bevis som visar löftet med vårt tillvägagångssätt.

► BibTeX-data

► Referenser

[1] John Preskill. "Quantum computing i NISQ-eran och därefter". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow och Ashley Montanaro. "Kvantberäkningsöverlägsenhet". Nature 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Edward Farhi, Jeffrey Goldstone och Sam Gutmann. "En ungefärlig kvantoptimeringsalgoritm" (2014).

[4] Iain Dunning, Swati Gupta och John Silberholz. "Vad fungerar bäst när? En systematisk utvärdering av heuristik för Max-Cut och QUBO”. INFORMERAR Journal on Computing 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[5] Michel X Goemans och David P Williamson. "Förbättrade approximationsalgoritmer för maximalt skärande och tillfredsställande problem med semidefinite programmering". Journal of the ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[6] Samuel Burer och Renato DC Monteiro. "En icke-linjär programmeringsalgoritm för att lösa semidefinita program via låggradig faktorisering". Matematisk programmering 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: Ett ramverk med öppen källkod för kvantberäkning" (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard och Eugene Tang. "QAOA fastnar med början från en bra klassisk sträng" (2022).

[9] Daniel J. Egger, Jakub Mareček och Stefan Woerner. "Varmstartande kvantoptimering". Quantum 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack, Raimel A Medina, Richard Kueng och Maksym Serbyn. "Rekursiv girig initiering av den ungefärliga kvantoptimeringsalgoritmen med garanterad förbättring". Physical Review A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[11] Stefan H Sack och Maksym Serbyn. "Kvantglödgningsinitiering av den ungefärliga kvantoptimeringsalgoritmen". quantum 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler och Mikhail D Lukin. "Quantum approximativ optimeringsalgoritm: Prestanda, mekanism och implementering på kortsiktiga enheter". Fysisk granskning X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski och Travis S Humble. "Parameteröverföring för ungefärlig kvantoptimering av vägd maxcut". ACM Transactions on Quantum Computing 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[14] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev och Ilya Safro. "Överförbarhet av optimala QAOA-parametrar mellan slumpmässiga grafer". 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Sidorna 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 och Daniel J Egger. "Skalning av den ungefärliga kvantoptimeringsalgoritmen på supraledande qubitbaserad hårdvara". 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 och Travis S Humble. "Skala ungefärlig kvantoptimering på hårdvara på kort sikt". Scientific Reports 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

[17] Gian Giacomo Guerreschi och Anne Y Matsuura. "QAOA för max-cut kräver hundratals qubits för kvanthastighet". Vetenskapliga rapporter 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra och Vedran Dunjko. "Att kvant eller inte till kvant: mot algoritmval i kortsiktig kvantoptimering". Quantum Science and Technology 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell och Edward Dahl. "QAOA av högsta klass". 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C). Sidorna 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 och George Siopsis. "Inverkan av grafstrukturer för QAOA på maxcut". Quantum Information Processing 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santa, Fred Jendrzejewski, Philipp Hauke ​​och Daniel J Egger. "Klämning och ungefärlig kvantoptimering" (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg och Ilya Safro. "Klassiska symmetrier och den ungefärliga kvantoptimeringsalgoritmen". Quantum Information Processing 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz och Peter Love. "Maxcut kvant ungefärlig optimeringsalgoritm prestandagarantier för p> 1". Physical Review A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone och Sam Gutmann. "Kvantalgoritmer för fasta qubit-arkitekturer" (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig och Eugene Tang. "Hinder för variationsmässig kvantoptimering från symmetriskydd". Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik och Sam Gutmann. "Den ungefärliga kvantoptimeringsalgoritmen behöver se hela grafen: Ett typiskt fall" (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig och Eugene Tang. "Hybrid kvantklassiska algoritmer för ungefärlig graffärgning". Quantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. "Klassiska och kvantbegränsade djupapproximationsalgoritmer" (2019).

[29] Kunal Marwaha. "Lokal klassisk max-cut-algoritm överträffar $ p= 2$ QAOA på vanliga grafer med hög omkrets". Quantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak och Kunal Marwaha. "Klassiska algoritmer och kvantbegränsningar för maximal skärning på grafer med hög omkrets" (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler och Swati Gupta. "Överbrygga klassiskt och kvantum med SDP-initierade varmstarter för QAOA". ACM Transactions on Quantum Computing (2022).
https: / / doi.org/ 10.1145 / 3549554

[32] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli och Rupak Biswas. "Från den ungefärliga kvantoptimeringsalgoritmen till en kvantalternerande operatoransatz". Algoritmer 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy och Eleanor G. Rieffel. "$xy$ mixers: Analytiska och numeriska resultat för kvantalternerande operatoransatz". Phys. 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 och Sophia E. Economou. "Adaptiv kvantapproximativ optimeringsalgoritm för att lösa kombinatoriska problem på en kvantdator". Phys. Rev. Research 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Andreas Bärtschi och Stephan Eidenbenz. "Grover-blandare för QAOA: skiftande komplexitet från mixerdesign till tillståndsberedning". 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Sidorna 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel och Zhihui Wang. "Nästan optimal kvantkrets för Grovers ostrukturerade sökning med hjälp av ett tvärfält". Physical Review A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Lov K Grover. "En snabb kvantmekanisk algoritm för databassökning". I Proceedings av det tjugoåttonde årliga ACM-symposiet om datorteori. Sidorna 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Yin Zhang, Samuel Burer och Renato DC Monteiro. "Rank-2 avslappningsheuristik för max-cut och andra binära kvadratiska program". SIAM Journal on Optimization 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari och Roberto Imbuzeiro Oliveira. "Lösa sdps för synkronisering och maxcut-problem via grothendieck-ojämlikheten". I konferens om lärandeteori. Sidorna 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh och Kevin Thompson. "En optimal uppskattning av produkt-tillstånd för 2-lokala kvanthamiltonianer med positiva termer" (2022). arXiv:2206.08342.
arXiv: 2206.08342

[41] Reuben Tate och Swati Gupta. "Ci-qube". GitHub-arkiv (2021). URL: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] Howard Karloff. "Hur bra är Goemans–Williamson MAX-CUT-algoritmen?". 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. "Quantum approximativ optimering av icke-planära grafproblem på en plan supraledande processor". 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 och Jay M. Gambetta. "Lättande mätfel i multiqubit-experiment". Phys. Rev. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[45] George S. Barron och Christopher J. Wood. "Mätningsfelsreducering för variationskvantalgoritmer" (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 och Xiaoqiang Zheng. "TensorFlow: Storskalig maskininlärning på heterogena system" (2015).

[47] Diederik P. Kingma och Jimmy Ba. "Adam: En metod för stokastisk optimering" (2014).

[48] Roger Fletcher. "Praktiska metoder för optimering (2:a upplagan)". John Wiley och söner. New York, NY, USA (1987).
https: / / doi.org/ 10.1002 / 9781118723203

[49] MJD Powell. "En direkt sökoptimeringsmetod som modellerar mål- och begränsningsfunktionerna genom linjär interpolation". Advances in Optimization and Numerical Analysis 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] Alan J. Laub. "Matrisanalys för forskare och ingenjörer". Volym 91. Siam. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907

[51] Georg Frobenius. "Ueber matrizen aus nicht negativen element". Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften Sidorna 456–477 (1912).

[52] A. Kaveh och H. Rahami. "En enhetlig metod för egennedbrytning av grafprodukter". Communications in Numerical Methods in Engineering with Biomedical Applications 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Špacapan. "Anslutning av kartesiska produkter av grafer". Applied Mathematics Letters 21, 682–685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

[54] Jacek Gondzio och Andreas Grothey. "Lösa icke-linjära ekonomiska planeringsproblem med 109 beslutsvariabler på massivt parallella arkitekturer". WIT Transactions on Modeling and Simulation 43 (2006).
https: / / doi.org/ 10.2495 / CF060101

[55] Fläkt RK Chung. "Spektralgrafteori". Volym 92. American Mathematical Soc. (1997).
https: / / doi.org/ 10.1090 / cbms / 092

[56] MA Nielsen och IL Chuang. "Kvantberäkning och kvantinformation: 10-årsjubileumsutgåva". 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 och Benjamin Nachman. "Beräkningseffektiv nollbrusextrapolering för begränsning av kvantgrindfel". Physical Review A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala och Kristan Temme. "Probabilistisk felavstängning med glesa pauli–lindblad-modeller på bullriga kvantprocessorer". Naturfysik Sidorna 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick och Frédéric Roupin. "BiqCrunch: En semidefinitiv gren-och-bunden metod för att lösa binära kvadratiska problem". ACM Transactions on Mathematical Software 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer och Matt McGinnis. "De minsta egenvärdena för hamming-grafer, johnson-grafer och andra avstånds-reguljära grafer med klassiska parametrar". Journal of Combinatorial Theory, Series B 133, 88–121 (2018).
https: / / doi.org/ 10.1016 / j.jctb.2018.04.005

[61] Donald Knuth. "Kombinatoriska matriser". Utvalda artiklar om diskret matematik (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Citerad av

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner och Daniel J. Egger, "Scaling of the quantum approximate optimization algorithm on supraconducting qubit based hardware", Quantum 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun och 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 och Ping Koy Lam, "An Expressive Ansatz for Low-Depth Quantum Optimization", arXiv: 2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo och Anh Pham, "Komplettera Grovers sökalgoritm: Implementering av amplitudsuppression", arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele och 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 och Creston D. Herold, "Modellering av brus i globala Mølmer-Sørensen-interaktioner som tillämpas på quantum approximative optimization", Fysisk granskning A 107 6, 062406 (2023).

[7] Guoming Wang, "Classically-Boosted Quantum Optimization Algorithm", arXiv: 2203.13936, (2022).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-09-27 01:31:19). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2023-09-27 01:31:17).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal