Varmstartet QAOA med tilpassede miksere konvergerer beviselig og slår Goemans-Williamsons Max-Cut ved lave kretsdybder.

Publisert av Platon

Følgere: 0

Ruben Tate¹, Jai Moondra², Bryan Gard³, Greg Mohler³og Swati Gupta⁴

¹CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87544, USA
²Georgia Institute of Technology, Atlanta, GA 30332, USA
³Georgia Tech Research Institute, Atlanta, GA 30332, USA
⁴Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02142, USA

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Vi generaliserer Quantum Approximate Optimization Algorithm (QAOA) til Farhi et al. (2014) for å tillate vilkårlige separerbare starttilstander med tilsvarende miksere slik at starttilstanden er den mest eksiterte tilstanden til den blandende Hamiltonian. Vi demonstrerer denne versjonen av QAOA, som vi kaller $QAOA-warmest$, ved å simulere Max-Cut på vektede grafer. Vi initialiserer starttilstanden som en $warm-start$ ved å bruke $2$ og $3$-dimensjonale tilnærminger oppnådd ved bruk av randomiserte projeksjoner av løsninger til Max-Cuts semi-definite program, og definerer en varmstartavhengig $custom mixer$. Vi viser at disse varmestartene initialiserer QAOA-kretsen med konstantfaktortilnærmelser på $0.658$ for $2$-dimensjonale og $0.585$ for $3$-dimensjonale varmestarter for grafer med ikke-negative kantvekter, og forbedrer i forhold til tidligere kjente trivielle ( dvs. $0.5$ for standard initialisering) grenser i verste fall ved $p=0$. Disse faktorene senker faktisk tilnærmingen oppnådd for Max-Cut ved høyere kretsdybder, siden vi også viser at QAOA-varmest med noen separerbar starttilstand konvergerer til Max-Cut under den adiabatiske grensen som $prightarrow infty$. Valget av varmstarter påvirker imidlertid konvergenshastigheten til Max-Cut betydelig, og vi viser empirisk at våre varmestarter oppnår en raskere konvergens sammenlignet med eksisterende tilnærminger. I tillegg viser våre numeriske simuleringer kutt av høyere kvalitet sammenlignet med standard QAOA, den klassiske Goemans-Williamson-algoritmen og en varmstartet QAOA uten tilpassede miksere for et instansbibliotek med $1148$-grafer (opptil $11$-noder) og dybde $p=8 $. Vi viser videre at QAOA-varmest overgår standard QAOA til Farhi et al. i eksperimenter på gjeldende IBM-Q og Quantinuum maskinvare.

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.

Utvalgt bilde: Ytelse av QAOA-varmest (med varmestarter) og standard QAOA som funksjon av QAOA-dybde for en ideell (stiplet) og støyende simulering (prikket). For den valgte 20-node grafen oppnår GW et tilnærmingsforhold på 0.912, mens i det ideelle tilfellet overgår QAOA-varmest GW for $p geq 2$ mens standard QAOA krever $p > 4$. Støysimuleringen er basert på kalibreringsdata fra IBM-Qs Guadalupe-enhet.

Populært sammendrag

Quantum approximate optimization algorithm (QAOA) er en hybrid kvante-klassisk teknikk for kombinatorisk optimalisering som lover å være kraftigere enn noen klassisk optimizer. I dette arbeidet eksemplifiserer vi potensialet på et grunnleggende kombinatorisk optimaliseringsproblem, kjent som Max-Cut, der den best mulige klassiske algoritmen er den av Goemans og Williamson (GW). Vi oppnår dette ved å introdusere klassisk oppnådde varmstarter til QAOA, med modifiserte blandeoperatører, og viser beregningsmessig at dette overgår GW. Vi modifiserer kvantealgoritmen på riktig måte for å opprettholde forbindelsen til kvanteadiabatisk databehandling; vi diskuterer teori og gir numeriske og eksperimentelle bevis som viser løftet til vår tilnærming.

► BibTeX-data

@article{Tate2023warmstartedqaoa, doi = {10.22331/q-2023-09-26-1121}, url = {https://doi.org/10.22331/q-2023-09-26-1121}, tittel = {Warm- {S}startet {QAOA} med {C}tilpassede {M}ixers {P}bevegelig {C}konvergerer og {C}beregningsmessig {B}spiser {G}oemans-{W}illiamson's {M}ax-{C} ut ved {L}ow {C}ircuit {D}epths}, forfatter = {Tate, Reuben og Moondra, Jai og Gard, Bryan og Mohler, Greg og Gupta, Swati}, journal = {{Quantum}}, issn = {2521-327X}, utgiver = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volum = {7}, sider = {1121}, måned = sep, år = {2023 } }

► Referanser

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

[2] Aram W. Harrow og Ashley Montanaro. "Kvanteberegningsoverlegenhet". Nature 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

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

[4] Iain Dunning, Swati Gupta og John Silberholz. «Hva fungerer best når? En systematisk evaluering av heuristikk for Max-Cut og QUBO”. INFORMER Journal on Computing 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[5] Michel X Goemans og David P Williamson. "Forbedrede tilnærmingsalgoritmer for maksimal kutt- og tilfredshetsproblemer ved bruk av semidefinit 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 for å løse semidefinite programmer via lav-rangs 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: Et rammeverk med åpen kildekode for kvanteberegning" (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard og Eugene Tang. "QAOA blir sittende fast med utgangspunkt i en god klassisk streng" (2022).

[9] Daniel J. Egger, Jakub Mareček og Stefan Woerner. "Varmstartende kvanteoptimalisering". 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 av den omtrentlige kvanteoptimaliseringsalgoritmen med garantert forbedring". Physical Review A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[11] Stefan H Sack og Maksym Serbyn. "Kvanteutglødningsinitialisering av den omtrentlige kvanteoptimaliseringsalgoritmen". 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. "Omtrentlig kvanteoptimaliseringsalgoritme: Ytelse, mekanisme og implementering på enheter på kort sikt". Fysisk gjennomgang 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øring for omtrentlig kvanteoptimalisering av vektet 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ørbarhet av optimale QAOA-parametere mellom tilfeldige 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 av den omtrentlige kvanteoptimaliseringsalgoritmen på superledende qubit-basert maskinvare". 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 av omtrentlig kvanteoptimalisering på maskinvare på kort sikt". 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 krever hundrevis av qubits for kvantehastighet". Vitenskapelige 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 ikke til kvante: mot algoritmevalg i kortsiktig kvanteoptimalisering". Quantum Science and Technology 5, 044009 (2020).
https://doi.org/10.1088/2058-9565/abb8e5

[19] Colin Campbell og Edward Dahl. "QAOA av høyeste orden". I 2022 IEEE 19th 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 av 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. "Klemning og omtrentlig kvanteoptimalisering" (2022).

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

[23] Jonathan Wurtz og Peter Love. "Maxcut quantum approximative optimization algoritme ytelsesgarantier 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 for faste qubit-arkitekturer" (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang. "Hindringer for variasjonskvanteoptimalisering 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 kvanteoptimaliseringsalgoritmen trenger å se hele grafen: Et typisk tilfelle" (2020).

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

[28] Matthew B Hastings. "Klassiske og kvantebegrensede dybdetilnærmingsalgoritmer" (2019).

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

[30] Boaz Barak og Kunal Marwaha. "Klassiske algoritmer og kvantebegrensninger for maksimalt kutt på grafer med høy omkrets" (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler og Swati Gupta. "Bruker klassisk og kvante med SDP initialiserte varmstarter for 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 kvanteoptimaliseringsalgoritmen til en kvantealternerende 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$-miksere: Analytiske og numeriske resultater for kvantealternerende 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 omtrentlig kvanteoptimaliseringsalgoritme for å løse kombinatoriske problemer på en kvantedatamaskin". Phys. Rev. Forskning 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Andreas Bärtschi og Stephan Eidenbenz. "Grover miksere for QAOA: Skifte kompleksitet fra mikserdesign 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. "Nesten optimal kvantekrets for Grovers ustrukturerte søk ved bruk av et tverrfelt". Physical Review A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Kjærlighet K Grover. "En rask kvantemekanisk algoritme for databasesøk". I Proceedings av det tjueåttende årlige ACM-symposiet om teori om databehandling. Side 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Yin Zhang, Samuel Burer og Renato DC Monteiro. "Rank-2 avspenningsheuristikk 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øse sdps for synkronisering og maxcut-problemer via grothendieck-ulikheten". I konferanse 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ærming for 2-lokale kvantehamiltonianere med positive termer" (2022). arXiv:2206.08342.
arxiv: 2206.08342

[41] Reuben Tate og Swati Gupta. "Ci-qube". GitHub-depot (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 optimalisering av ikke-plane grafproblemer på en plan superledende prosessor". 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. "Begrensende målefeil 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. "Reduksjon av målefeil for variasjonskvantealgoritmer" (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: Storskala maskinlæring på heterogene systemer" (2015).

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

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

[49] MJD Powell. "En direkte søkeoptimaliseringsmetode som modellerer mål- og begrensningsfunksjonene ved lineær interpolering". 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. "Matriseanalyse 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 enhetlig metode for egendekomponering 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. "Tilkobling av kartesiske produkter av 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øse ikke-lineære økonomiske planleggingsproblemer med 109 beslutningsvariabler på massivt parallelle arkitekturer". WIT Transactions on Modeling and Simulation 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 kvanteinformasjon: 10-årsjubileumsutgave". 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 null-støyekstrapolering for kvante-gate-feilredusering". 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. "Sannsynlighetsfeilkansellering med sparsomme pauli-lindblad-modeller på støyende kvanteprosessorer". NaturfysikkSide 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 for å løse binære kvadratiske problemer". ACM Transactions on Mathematical Software 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer og Matt McGinnis. "De minste egenverdiene til hamming-grafer, johnson-grafer og andre avstand-regulære grafer med klassiske parametere". Journal of Combinatorial Theory, Series B 133, 88–121 (2018).
https:///doi.org/10.1016/j.jctb.2018.04.005

[61] Donald Knuth. "Kombinatoriske matriser". Utvalgte artikler om diskret matematikk (2000).
https://doi.org/10.1016/S0898-1221(04)90150-2

Sitert av

[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 (2022).

[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, "Komplementer Grovers søkealgoritme: Implementering av 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 gjennomgang A 107 6, 062406 (2023).

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

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-09-27 01:31:19). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2023-09-27 01:31:17).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.