Warm gestarte QAOA met aangepaste mixers convergeert aantoonbaar en verslaat computationeel Goemans-Williamson's Max-Cut bij lage circuitdieptes

Warm gestarte QAOA met aangepaste mixers convergeert aantoonbaar en verslaat computationeel Goemans-Williamson's Max-Cut bij lage circuitdieptes

Ruben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3 en Swati Gupta4

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

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

We generaliseren het Quantum Approximate Optimization Algorithm (QAOA) van Farhi et al. (2014) om willekeurige scheidbare begintoestanden met overeenkomstige mixers mogelijk te maken, zodat de starttoestand de meest opgewonden toestand van de mengende Hamiltoniaan is. We demonstreren deze versie van QAOA, die we $QAOA-warmest$ noemen, door Max-Cut te simuleren op gewogen grafieken. We initialiseren de starttoestand als een $warm-start$ met behulp van $2$ en $3$-dimensionale benaderingen verkregen met behulp van gerandomiseerde projecties van oplossingen voor het semi-definitieve programma van Max-Cut, en definiëren een warm-start-afhankelijke $custom mixer$. We laten zien dat deze warme starts het QAOA-circuit initialiseren met constante-factorbenaderingen van $0.658$ voor $2$-dimensionale en $0.585$ voor $3$-dimensionale warme starts voor grafieken met niet-negatieve randgewichten, wat een verbetering is ten opzichte van eerder bekende triviale ( dwz $0.5$ voor standaardinitialisatie) in het slechtste geval bij $p=0$. Deze factoren beperken in feite de benadering die wordt bereikt voor Max-Cut bij hogere circuitdiepten, omdat we ook laten zien dat QAOA-warmste met een scheidbare initiële toestand convergeert naar Max-Cut onder de adiabatische limiet als $prightarrow infty$. De keuze voor een warme start heeft echter een aanzienlijke invloed op de mate van convergentie naar Max-Cut, en we laten empirisch zien dat onze warme start een snellere convergentie bereikt vergeleken met bestaande benaderingen. Bovendien laten onze numerieke simulaties bezuinigingen van hogere kwaliteit zien vergeleken met standaard QAOA, het klassieke Goemans-Williamson-algoritme en een warm gestarte QAOA zonder aangepaste mixers voor een instantiebibliotheek van $1148$-grafieken (tot $11$-knooppunten) en diepte $p=8 $. We laten verder zien dat QAOA-warmest beter presteert dan de standaard QAOA van Farhi et al. in experimenten met de huidige IBM-Q- en Quantinuum-hardware.

Kwantum benaderend optimalisatie-algoritme (QAOA) is een hybride kwantum-klassieke techniek voor combinatorische optimalisatie die krachtiger belooft te zijn dan welke klassieke optimizer dan ook. In dit werk illustreren we het potentieel ervan aan de hand van een fundamenteel combinatorisch optimalisatieprobleem, bekend als Max-Cut, waarbij het best mogelijke klassieke algoritme dat van Goemans en Williamson (GW) is. We bereiken dit door klassiek verkregen warme starts te introduceren in de QAOA, met aangepaste mengoperatoren, en laten computationeel zien dat dit beter presteert dan GW. We passen het kwantumalgoritme op de juiste manier aan om de verbinding met kwantum-adiabatisch computergebruik te behouden; we bespreken de theorie en leveren numeriek en experimenteel bewijs dat de belofte van onze aanpak aantoont.

► BibTeX-gegevens

► Referenties

[1] John Prekill. "Quantum computing in het NISQ-tijdperk en daarna". Kwantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow en Ashley Montanaro. "Quantum computationele suprematie". Natuur 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Edward Farhi, Jeffrey Goldstone en Sam Gutmann. "Een kwantum-bij benadering optimalisatie-algoritme" (2014).

[4] Iain Dunning, Swati Gupta en John Silberholz. “Wat werkt wanneer het beste? Een systematische evaluatie van heuristieken voor Max-Cut en QUBO”. INFORMS Tijdschrift over computergebruik 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

[5] Michel X Goemans en David P Williamson. "Verbeterde benaderingsalgoritmen voor maximale snij- en bevredigingsproblemen met behulp van semidefiniet programmeren". Publicatieblad van de ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[6] Samuel Burer en Renato DC Monteiro. "Een niet-lineair programmeeralgoritme voor het oplossen van semidefiniete programma's via factorisatie van lage rang". Wiskundig programmeren 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: een open-sourceframework voor kwantumcomputing” (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard en Eugene Tang. “De QAOA loopt vast vanaf een goede klassieke snaar” (2022).

[9] Daniel J. Egger, Jakub Mareček en Stefan Woerner. "Warmstartende kwantumoptimalisatie". Kwantum 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack, Raimel A Medina, Richard Kueng en Maksym Serbyn. "Recursieve hebzuchtige initialisatie van het kwantum-geschatte optimalisatie-algoritme met gegarandeerde verbetering". Fysieke beoordeling A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[11] Stefan H Sack en Maksym Servin. "Kwantum-gloeiende initialisatie van het kwantum-geschatte optimalisatie-algoritme". kwantum 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler en Mikhail D Lukin. "Kwantum-bij benadering optimalisatie-algoritme: prestaties, mechanisme en implementatie op apparaten voor de korte termijn". Fysieke beoordeling X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski en Travis S Humble. "Parameteroverdracht voor kwantumgeschatte optimalisatie van gewogen maxcut". ACM-transacties op kwantumcomputing 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[14] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev en Ilya Safro. "Overdraagbaarheid van optimale QAOA-parameters tussen willekeurige grafieken". In 2021 IEEE Internationale Conferentie over Quantum Computing and Engineering (QCE). Pagina's 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 en Daniel J Egger. "Schaalvergroting van het kwantum-bij benadering optimalisatie-algoritme op supergeleidende qubit-gebaseerde hardware". Kwantum 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 en Travis S Humble. "Het schalen van geschatte kwantumoptimalisatie op hardware voor de korte termijn". Wetenschappelijke rapporten 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

[17] Gian Giacomo Guerreschi en Anne Y Matsuura. “QAOA voor max-cut vereist honderden qubits voor kwantumversnelling”. Wetenschappelijke rapporten 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra en Vedran Dunjko. "Naar kwantum of niet naar kwantum: naar algoritmeselectie in kwantumoptimalisatie op korte termijn". Kwantumwetenschap en technologie 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell en Edward Dahl. “QAOA van de hoogste orde”. In 2022 IEEE 19e Internationale Conferentie over Software Architecture Companion (ICSA-C). Pagina's 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 en George Siopsis. "Impact van grafiekstructuren voor QAOA op maxcut". Kwantuminformatieverwerking 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​en Daniel J Egger. "Knijpen en kwantum-geschatte optimalisatie" (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg en Ilya Safro. "Klassieke symmetrieën en het kwantum-bij benadering optimalisatie-algoritme". Kwantuminformatieverwerking 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz en Peter Love. "Maxcut quantum geschatte optimalisatie-algoritme prestatiegaranties voor p> 1". Fysieke beoordeling A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone en Sam Gutmann. “Kwantumalgoritmen voor vaste qubit-architecturen” (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig en Eugene Tang. “Obstakels voor variatie-kwantumoptimalisatie door symmetriebescherming”. Fysieke beoordelingsbrieven 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik en Sam Gutmann. “Het kwantum-geschatte optimalisatie-algoritme moet de hele grafiek zien: een typisch geval” (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig en Eugene Tang. ‘Hybride kwantumklassieke algoritmen voor geschatte grafiekkleuring’. Kwantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. "Klassieke en kwantumbegrensde algoritmen voor dieptebenadering" (2019).

[29] Kunal Marwaha. “Het lokale klassieke max-cut-algoritme presteert beter dan $ p= 2$ QAOA op reguliere grafieken met een hoge omvang”. Kwantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak en Kunal Marwaha. "Klassieke algoritmen en kwantumbeperkingen voor maximale verlaging van grafieken met een hoge omvang" (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler en Swati Gupta. "Het overbruggen van klassiek en kwantum met door SDP geïnitialiseerde warme starts voor QAOA". ACM-transacties over kwantumcomputing (2022).
https: / / doi.org/ 10.1145 / 3549554

[32] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli en Rupak Biswas. "Van het kwantum-bij benadering optimalisatie-algoritme tot een kwantum-alternerende operator ansatz". Algoritmen 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy en Eleanor G. Rieffel. "$ xy$ mixers: analytische en numerieke resultaten voor de kwantumalternerende operator ansatz". Fys. 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 en Sophia E. Economou. "Adaptief kwantum-bij benadering optimalisatie-algoritme voor het oplossen van combinatorische problemen op een kwantumcomputer". Fys. Rev. Onderzoek 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Andreas Bärtschi en Stephan Eidenbenz. "Grover-mixers voor QAOA: verschuiving van complexiteit van mixerontwerp naar staatsvoorbereiding". In 2020 IEEE Internationale Conferentie over Quantum Computing and Engineering (QCE). Pagina's 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel en Zhihui Wang. "Bijna optimaal kwantumcircuit voor de ongestructureerde zoektocht van Groger met behulp van een transversaal veld". Fysieke beoordeling A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Liefs K. Grover. "Een snel kwantummechanisch algoritme voor het doorzoeken van databases". In Proceedings van het achtentwintigste jaarlijkse ACM-symposium over Theory of computing. Pagina's 212-219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Yin Zhang, Samuel Burer en Renato DC Monteiro. "Rang-2 ontspanningsheuristieken voor max-cut en andere binaire kwadratische programma's". SIAM Journal on Optimization 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari en Roberto Imbuzeiro Oliveira. "Sdps oplossen voor synchronisatie- en maxcut-problemen via de Grothendieck-ongelijkheid". In conferentie over leertheorie. Pagina's 1476–1515. PMLR (2017).
https:/​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh en Kevin Thompson. "Een optimale product-toestand-benadering voor 2-lokale kwantumhamiltonians met positieve termen" (2022). arXiv:2206.08342.
arXiv: 2206.08342

[41] Ruben Tate en Swati Gupta. “Ci-qube”. GitHub-opslagplaats (2021). url: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] Howard Karloff. "Hoe goed is het Goemans-Williamson MAX-CUT-algoritme?". 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. "Kwantum-bij benadering optimalisatie van niet-planaire grafiekproblemen op een planaire supergeleidende processor". Natuurfysica 17, 332–336 (2021).
https: / / doi.org/ 10.1038 / s41567-020-01105-y

[44] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay en Jay M. Gambetta. "Het beperken van meetfouten in multiqubit-experimenten". Fys. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[45] George S. Barron en Christopher J. Wood. “Meetfoutbeperking voor variatiekwantumalgoritmen” (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 en Xiaoqiang Zheng. “TensorFlow: Grootschalig machinaal leren op heterogene systemen” (2015).

[47] Diederik P. Kingma en Jimmy Ba. “Adam: Een methode voor stochastische optimalisatie” (2014).

[48] Rogier Fletcher. “Praktische methoden voor optimalisatie (2e editie)”. John Wiley en zonen. New York, NY, VS (1987).
https: / / doi.org/ 10.1002 / 9781118723203

[49] MJD Powell. "Een directe zoekoptimalisatiemethode die de doel- en beperkingsfuncties modelleert door lineaire interpolatie". Vooruitgang in optimalisatie en numerieke analyse 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] Alan J. Laub. “Matrixanalyse voor wetenschappers en ingenieurs”. Deel 91. Siam. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907

[51] Georg Frobenius. “Ueber matrizen aus nicht negatieve elementen”. Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften Pagina's 456–477 (1912).

[52] A. Kaveh en H. Rahami. "Een uniforme methode voor eigendecompositie van grafiekproducten". Communicatie in numerieke methoden in engineering met biomedische toepassingen 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Spacapan. "Connectiviteit van cartesische producten van grafieken". Toegepaste Wiskunde Letters 21, 682-685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

[54] Jacek Gondzio en Andreas Grothey. "Niet-lineaire financiële planningsproblemen oplossen met 109 beslissingsvariabelen op massaal parallelle architecturen". WIT-transacties over modellering en simulatie 43 (2006).
https://​/​doi.org/​10.2495/​CF060101

[55] Fan RK Chung. "Spectrale grafentheorie". Deel 92. Amerikaanse wiskundige Soc. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] MA Nielsen en IL Chuang. “Kwantumberekening en kwantuminformatie: 10e jubileumeditie”. 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 en Benjamin Nachman. "Computationeel efficiënte nul-ruis-extrapolatie voor het beperken van kwantum-gate-fouten". Fysieke beoordeling A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala en Kristan Temme. "Probabilistische foutannulering met schaarse Pauli-Lindblad-modellen op luidruchtige kwantumprocessors". Natuurfysica Pagina's 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick en Frédéric Roupin. "BiqCrunch: een semidefinite branch-and-bound-methode voor het oplossen van binaire kwadratische problemen". ACM-transacties op wiskundige software 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer en Matt McGinnis. "De kleinste eigenwaarden van Hamming-grafieken, Johnson-grafieken en andere afstandsreguliere grafieken met klassieke parameters". Journal of Combinatorial Theory, serie B 133, 88–121 (2018).
https: / / doi.org/ 10.1016 / j.jctb.2018.04.005

[61] Donald Knuth. "Combinatorische matrices". Geselecteerde artikelen over discrete wiskunde (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Geciteerd door

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner en Daniel J. Egger, "Schaal van het kwantum-geschatte optimalisatie-algoritme op supergeleidende qubit-gebaseerde hardware", Kwantum 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun en Marco Pistoia, "Afstemming tussen initiële status en mixer verbetert QAOA-prestaties voor beperkte portfolio-optimalisatie", arXiv: 2305.03857, (2023).

[3] V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad en Ping Koy Lam, “Een expressieve Ansatz voor kwantumoptimalisatie op lage diepte”, arXiv: 2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo en Anh Pham, "Aanvulling op het zoekalgoritme van Grover: een implementatie van amplitude-onderdrukking", arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele en Procolo Lucignano, "Convergentie van gedigitaliseerde-counterdiabatische QAOA: circuitdiepte versus vrije parameters", arXiv: 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble en Creston D. Herold, "Modellering van ruis in mondiale Mølmer-Sørensen-interacties toegepast op geschatte kwantumoptimalisatie", Fysieke beoordeling A 107 6, 062406 (2023).

[7] Guoming Wang, “Klassiek versterkt kwantumoptimalisatie-algoritme”, arXiv: 2203.13936, (2022).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2023-09-27 01:31:19). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2023-09-27 01:31:17).

Tijdstempel:

Meer van Quantum Journaal