Varmstartet QAOA med brugerdefinerede mixere konvergerer beviseligt og slår beregningsmæssigt Goemans-Williamsons Max-Cut ved lave kredsløbsdybder

Varmstartet QAOA med brugerdefinerede mixere konvergerer beviseligt og slår beregningsmæssigt Goemans-Williamsons Max-Cut ved lave kredsløbsdybder

Tidsstempel: 26. september 2023 kl. 9

Ruben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3og 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

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Vi generaliserer Quantum Approximate Optimization Algorithm (QAOA) fra Farhi et al. (2014) for at tillade vilkårlige adskillelige begyndelsestilstande med tilsvarende blandere, således at starttilstanden er den mest exciterede tilstand af den blandende Hamiltonian. Vi demonstrerer denne version af QAOA, som vi kalder $QAOA-warmest$, ved at simulere Max-Cut på vægtede grafer. Vi initialiserer starttilstanden som en $warm-start$ ved hjælp af $2$ og $3$-dimensionelle tilnærmelser opnået ved hjælp af randomiserede projektioner af løsninger til Max-Cuts semi-definite program, og definerer en varmstartafhængig $custom mixer$. Vi viser, at disse varmestarter initialiserer QAOA-kredsløbet med konstant-faktor-tilnærmelser på $0.658$ for $2$-dimensionelle og $0.585$ for $3$-dimensionelle varmestarter for grafer med ikke-negative kantvægte, hvilket forbedrer i forhold til tidligere kendte trivielle ( dvs. $0.5$ for standardinitialisering) worst case-grænser ved $p=0$. Disse faktorer sænker faktisk den tilnærmelse, der opnås for Max-Cut ved højere kredsløbsdybder, da vi også viser, at QAOA-varmest med en hvilken som helst adskillelig starttilstand konvergerer til Max-Cut under den adiabatiske grænse som $prightarrow infty$. Valget af varmestarter påvirker dog hastigheden af ​​konvergens til Max-Cut markant, og vi viser empirisk, at vores varmestarter opnår en hurtigere konvergens sammenlignet med eksisterende tilgange. Derudover viser vores numeriske simuleringer skæringer i højere kvalitet sammenlignet med standard QAOA, den klassiske Goemans-Williamson algoritme og en varmstartet QAOA uden brugerdefinerede mixere for et instansbibliotek med $1148$ grafer (op til $11$ noder) og dybde $p=8 $. Vi viser yderligere, at QAOA-varmest overgår standard QAOA fra Farhi et al. i eksperimenter på nuværende IBM-Q og Quantinuum hardware.

Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Udvalgt billede: Ydeevne af QAOA-varmest (med varmestarter) og standard QAOA som funktion af QAOA-dybde for en ideel (stiplet) og støjende simulering (punkteret). For den valgte 20-node graf opnår GW et tilnærmelsesforhold på 0.912, mens QAOA-varmest i det ideelle tilfælde overgår GW for $p geq 2$, mens standard QAOA kræver $p > 4$. Støjsimuleringen er baseret på kalibreringsdata fra IBM-Qs Guadalupe-enhed.

Populært resumé

Quantum approximate optimization algorithm (QAOA) er en hybrid kvante-klassisk teknik til kombinatorisk optimering, der lover at være mere kraftfuld end nogen klassisk optimering. I dette arbejde eksemplificerer vi dets potentiale på et grundlæggende kombinatorisk optimeringsproblem, kendt som Max-Cut, hvor den bedst mulige klassiske algoritme er den af ​​Goemans og Williamson (GW). Vi opnår dette ved at introducere klassisk opnåede varmstarter til QAOA med modificerede blandeoperatorer og viser beregningsmæssigt, at dette overgår GW. Vi modificerer kvantealgoritmen passende for at opretholde forbindelsen til kvanteadiabatisk databehandling; vi diskuterer teori og giver numerisk og eksperimentel dokumentation, der viser løftet om vores tilgang.

► BibTeX-data

► Referencer

[1] John Preskill. "Quantum computing i NISQ-æraen og derefter". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow og Ashley Montanaro. "Kvanteberegningsoverherredømme". Nature 549, 203-209 (2017).
https://​/​doi.org/​10.1038/​nature23458

[3] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. "En omtrentlig kvanteoptimeringsalgoritme" (2014).

[4] Iain Dunning, Swati Gupta og John Silberholz. "Hvad fungerer bedst hvornår? En systematisk evaluering af heuristik for Max-Cut og QUBO”. INFORMERER Journal on Computing 30 (2018).
https://​/​doi.org/​10.1287/​ijoc.2017.0798

[5] Michel X Goemans og David P Williamson. "Forbedrede tilnærmelsesalgoritmer til maksimal snit- og tilfredshedsproblemer ved hjælp af semidefinite programmering". Journal of the ACM (JACM) 42, 1115-1145 (1995).
https://​/​doi.org/​10.1145/​227683.227684

[6] Samuel Burer og Renato DC Monteiro. "En ikke-lineær programmeringsalgoritme til løsning af semidefinite programmer via lav-rang 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: En open source-ramme til kvanteberegning" (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard og Eugene Tang. "QAOA'en sætter sig fast med udgangspunkt i en god klassisk streng" (2022).

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

[10] Stefan H Sack, Raimel A Medina, Richard Kueng og Maksym Serbyn. "Rekursiv grådig initialisering af den kvantetilnærmede optimeringsalgoritme med garanteret forbedring". Physical Review A 107, 062404 (2023).
https://​/​doi.org/​10.1103/​PhysRevA.107.062404

[11] Stefan H Sack og Maksym Serbyn. "Kvanteudglødningsinitialisering af den omtrentlige kvanteoptimeringsalgoritme". quantum 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler og Mikhail D Lukin. "Quantum omtrentlig optimeringsalgoritme: Ydeevne, mekanisme og implementering på enheder på kort sigt". Fysisk gennemgang X 10, 021067 (2020).
https://​/​doi.org/​10.1103/​PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski og Travis S Humble. "Parameteroverførsel til omtrentlig kvanteoptimering af vægtet 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 og Ilya Safro. "Overførsel af optimale QAOA-parametre mellem tilfældige grafer". I 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Side 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 og Daniel J Egger. "Skalering af den omtrentlige kvanteoptimeringsalgoritme på superledende qubit-baseret 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 og Travis S Humble. "Skalering af omtrentlig kvanteoptimering på hardware på kort sigt". Scientific Reports 12, 12388 (2022).
https://​/​doi.org/​10.1038/​s41598-022-14767-w

[17] Gian Giacomo Guerreschi og Anne Y Matsuura. "QAOA for max-cut kræver hundredvis af qubits for kvantehastigheden". Videnskabelige rapporter 9, 1-7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra og Vedran Dunjko. "Til kvante eller ej til kvante: mod algoritmevalg i kortsigtet kvanteoptimering". Quantum Science and Technology 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell og Edward Dahl. "QAOA af højeste orden". I 2022 IEEE 19. International Conference on Software Architecture Companion (ICSA-C). Side 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 og George Siopsis. "Konsekvens af grafstrukturer for 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 ​​og Daniel J Egger. "Squeezing and quantum approximate optimization" (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg og Ilya Safro. "Klassiske symmetrier og den omtrentlige kvanteoptimeringsalgoritme". Quantum Information Processing 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz og Peter Love. "Maxcut kvante omtrentlig optimeringsalgoritme ydeevne garanterer for p> 1". Physical Review A 103, 042612 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. "Kvantealgoritmer til faste qubit-arkitekturer" (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang. "Forhindringer for variationsmæssig kvanteoptimering fra symmetribeskyttelse". Physical Review Letters 125, 260505 (2020).
https://​/​doi.org/​10.1103/​PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik og Sam Gutmann. "Den omtrentlige kvanteoptimeringsalgoritme skal se hele grafen: Et typisk tilfælde" (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang. "Hybride kvante-klassiske algoritmer til omtrentlig graffarvning". Quantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. "Klassiske og kvantegrænsede dybdetilnærmelsesalgoritmer" (2019).

[29] Kunal Marwaha. "Lokal klassisk max-cut algoritme overgår $ p= 2$ QAOA på regulære grafer med høj omkreds". Quantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak og Kunal Marwaha. "Klassiske algoritmer og kvantebegrænsninger for maksimal skæring på grafer med høj omkreds" (2021).
https://​/​doi.org/​10.4230/​LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler og Swati Gupta. "Bruger klassisk og kvante med SDP initialiserede varmestarter til 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 og Rupak Biswas. "Fra den omtrentlige kvanteoptimeringsalgoritme til en kvante alternerende operatøransatz". Algoritmer 12 (2019).
https://​/​doi.org/​10.3390/​a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy og Eleanor G. Rieffel. "$xy$ mixere: Analytiske og numeriske resultater for kvante alternerende operatøransatz". 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 og Sophia E. Economou. "Adaptiv kvantetilnærmet optimeringsalgoritme til løsning af kombinatoriske problemer på en kvantecomputer". Phys. Rev. Research 4, 033029 (2022).
https://​/​doi.org/​10.1103/​PhysRevResearch.4.033029

[35] Andreas Bärtschi og Stephan Eidenbenz. "Grover-mixere til QAOA: Skift kompleksitet fra mixerdesign til tilstandsforberedelse". I 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Side 72-82. IEEE (2020).
https://​/​doi.org/​10.1109/​QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel og Zhihui Wang. "Næsten optimalt kvantekredsløb til Grovers ustrukturerede søgning ved hjælp af et tværgående felt". Fysisk anmeldelse A 95, 062317 (2017).
https://​/​doi.org/​10.1103/​PhysRevA.95.062317

[37] Lov K Grover. "En hurtig kvantemekanisk algoritme til databasesøgning". I Proceedings af det otteogtyvende årlige ACM-symposium om teori om computing. Side 212–219. (1996).
https://​/​doi.org/​10.1145/​237814.237866

[38] Yin Zhang, Samuel Burer og Renato DC Monteiro. "Rank-2 afslapningsheuristik for max-cut og andre binære kvadratiske programmer". SIAM Journal on Optimization 12, 503––521 (2001).
https://​/​doi.org/​10.1137/​S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari og Roberto Imbuzeiro Oliveira. "Løser sdps for synkronisering og maxcut-problemer via grothendieck-uligheden". I konference om læringsteori. Side 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh og Kevin Thompson. "En optimal produkt-tilstand tilnærmelse for 2-lokale kvantehamiltonianere med positive udtryk" (2022). arXiv:2206.08342.
arXiv: 2206.08342

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

[42] Howard Karloff. "Hvor god er 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. "Kvante omtrentlig optimering af ikke-plane grafproblemer på en plan superledende 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 og Jay M. Gambetta. "Afhjælpning af målefejl i multiqubit-eksperimenter". Phys. Rev. A 103, 042605 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042605

[45] George S. Barron og Christopher J. Wood. "Reduktion af målefejl for variationskvantealgoritmer" (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 og Xiaoqiang Zheng. "TensorFlow: Maskinlæring i stor skala på heterogene systemer" (2015).

[47] Diederik P. Kingma og Jimmy Ba. "Adam: En metode til stokastisk optimering" (2014).

[48] Roger Fletcher. "Praktiske metoder til optimering (2. udgave)". John Wiley og sønner. New York, NY, USA (1987).
https://​/​doi.org/​10.1002/​9781118723203

[49] MJD Powell. "En direkte søgeoptimeringsmetode, der modellerer mål- og begrænsningsfunktionerne ved lineæ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. "Matrixanalyse for forskere og ingeniører". Bind 91. Siam. (2005).
https://​/​doi.org/​10.1137/​1.9780898717907

[51] Georg Frobenius. "Ueber matrizen aus ikke negative elementer". Sitzungsberichte der Königlich Preussischen Akademie der WissenschaftenSide 456–477 (1912).

[52] A. Kaveh og H. Rahami. "En samlet metode til egennedbrydning af grafprodukter". Communications in Numerical Methods in Engineering with Biomedical Applications 21, 377–388 (2005).
https://doi.org/​10.1002/​cnm.753

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

[54] Jacek Gondzio og Andreas Grothey. "Løsning af ikke-lineære økonomiske planlægningsproblemer med 109 beslutningsvariable på massivt parallelle arkitekturer". WIT-transaktioner om modellering og simulering 43 (2006).
https://doi.org/​10.2495/​CF060101

[55] Fan RK Chung. "Spektralgrafteori". Bind 92. American Mathematical Soc. (1997).
https://doi.org/​10.1090/​cbms/​092

[56] MA Nielsen og IL Chuang. "Kvanteberegning og kvanteinformation: 10-års jubilæumsudgave". 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 og Benjamin Nachman. "Beregningseffektiv nul-støj-ekstrapolation til dæmpning af kvante-gate-fejl". Physical Review A 105, 042406 (2022).
https://​/​doi.org/​10.1103/​PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala og Kristan Temme. "Sandsynlighedsfejlannullering med sparsomme pauli-lindblad-modeller på støjende kvanteprocessorer". NaturfysikSide 1-6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick og Frédéric Roupin. "BiqCrunch: En semibestemt gren-og-bundet metode til løsning af binære kvadratiske problemer". ACM-transaktioner på matematisk software 43 (2017).
https://​/​doi.org/​10.1145/​3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer og Matt McGinnis. "De mindste egenværdier af hamming-grafer, johnson-grafer og andre afstandsregulære grafer med klassiske parametre". Journal of Combinatorial Theory, Serie B 133, 88–121 (2018).
https://​/​doi.org/​10.1016/​j.jctb.2018.04.005

[61] Donald Knuth. "Kombinatoriske matricer". Udvalgte artikler om diskret matematik (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Citeret af

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

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

[4] Andrew Vlasic, Salvatore Certo og Anh Pham, "Suppler Grovers søgealgoritme: Implementering af amplitudeundertrykkelse", arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele og 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 og Creston D. Herold, "Modling noise in global Mølmer-Sørensen interactions used to quantum approximate optimization", Fysisk anmeldelse A 107 6, 062406 (2023).

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

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-09-27 01:31:19). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2023-09-27 01:31:17).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

Tidsstempel:

Mere fra Quantum Journal