Soojakäivitusega QAOA kohandatud segistitega koondub ja ületab arvutuslikult Goemansi-Williamsoni Max-Cut madala vooluringi sügavuse korral

Soojakäivitusega QAOA kohandatud segistitega koondub ja ületab arvutuslikult Goemansi-Williamsoni Max-Cut madala vooluringi sügavuse korral

Ruuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3ja Swati Gupta4

1CCS-3 infoteadused, Los Alamose riiklik labor, Los Alamos, NM 87544, USA
2Georgia Tehnoloogiainstituut, Atlanta, GA 30332, USA
3Georgia Tech Research Institute, Atlanta, GA 30332, USA
4Sloan School of Management, Massachusettsi Tehnoloogiainstituut, Cambridge, MA 02142, USA

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Üldistame Farhi jt kvantumbkaudse optimeerimise algoritmi (QAOA). (2014), et võimaldada vastavate segistitega suvaliselt eraldatavaid algolekuid nii, et lähteolek oleks seguneva Hamiltoni kõige ergastatud olek. Näitame seda QAOA versiooni, mida nimetame $QAOA-soojemaks $, simuleerides kaalutud graafikutel Max-Cut. Algoleku lähtestame $soe algus$, kasutades $2$ ja $3$-dimensioonide lähendusi, mis on saadud Max-Cuti poolkindla programmi lahenduste juhuslike projektsioonide abil, ja defineerime soojakäivitusest sõltuva $custom mixer$. Näitame, et need soojakäivitused initsialiseerivad QAOA ahela konstantse teguri ligikaudsustega $ 0.658 $ $ 2 $ mõõtmete ja $ 0.585, 3 $ $ 0.5 $ mõõtmete sooja käivitamise korral mittenegatiivse serva kaaluga graafikute jaoks, parandades varem tuntud triviaalset ( st $ 0 $ standardse lähtestamise korral) halvima juhu piirid $ p = 1148 $. Need tegurid on tegelikult madalamad Max-Cuti lähendusest, mis saavutati suuremal vooluringi sügavusel, kuna näitame ka, et QAOA-soojem mis tahes eraldatava algolekuga läheneb Max-Cut-ile adiabaatilise piiri all $prightarrow infty$. Soojakäivituste valik mõjutab aga märkimisväärselt Max-Cuti lähenemise kiirust ja me näitame empiiriliselt, et meie soojakäivitused saavutavad olemasolevate lähenemisviisidega võrreldes kiirema lähenemise. Lisaks näitavad meie numbrilised simulatsioonid kõrgema kvaliteediga kärpeid võrreldes standardse QAOA-ga, klassikalise Goemansi-Williamsoni algoritmiga ja soojendusega QAOA-ga ilma kohandatud mikseriteta eksemplaride teegi jaoks, mis sisaldab 11 $ graafikuid (kuni $ 8 $ sõlmed) ja sügavust $ p = XNUMX $. Lisaks näitame, et QAOA-soojem ületab Farhi jt standardset QAOA-d. katsetes praeguse IBM-Q ja Quantiinumi riistvaraga.

Kvantligikaudne optimeerimisalgoritm (QAOA) on hübriidne kvantklassikaline tehnika kombinatoorseks optimeerimiseks, mis tõotab olla võimsam kui ükski klassikaline optimeerija. Selles töös kirjeldame selle potentsiaali fundamentaalses kombinatoorses optimeerimise probleemis, mida tuntakse Max-Cut nime all, kus parim võimalik klassikaline algoritm on Goemansi ja Williamsoni (GW) algoritm. Me saavutame selle, lisades QAOA-le klassikaliselt saadud soojakäivitused modifitseeritud segamisoperaatoritega ja näitame arvutuslikult, et see ületab GW-d. Muudame kvantalgoritmi sobivalt, et säilitada ühendus kvantadiabaatilise andmetöötlusega; arutame teooriat ning esitame arvulisi ja eksperimentaalseid tõendeid, mis näitavad meie lähenemisviisi lubadust.

► BibTeX-i andmed

► Viited

[1] John Preskill. "Kvantarvutus NISQ ajastul ja pärast seda". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow ja Ashley Montanaro. "Kvantarvutuslik ülimuslikkus". Nature 549, 203–209 (2017).
https://​/​doi.org/​10.1038/​nature23458

[3] Edward Farhi, Jeffrey Goldstone ja Sam Gutmann. "Kvantligikaudne optimeerimisalgoritm" (2014).

[4] Iain Dunning, Swati Gupta ja John Silberholz. "Mis töötab kõige paremini millal? Max-Cuti ja QUBO heuristika süstemaatiline hindamine. TEAVITAB Journal on Computing 30 (2018).
https://​/​doi.org/​10.1287/​ijoc.2017.0798

[5] Michel X Goemans ja David P Williamson. "Täiustatud lähendusalgoritmid maksimaalse lõikamise ja rahuldamisprobleemide jaoks, kasutades poolkindlat programmeerimist". Journal of the ACM (JACM) 42, 1115–1145 (1995).
https://​/​doi.org/​10.1145/​227683.227684

[6] Samuel Burer ja Renato DC Monteiro. "Mittelineaarne programmeerimisalgoritm poolkindlate programmide lahendamiseks madala astme faktoriseerimise kaudu". Mathematical Programming 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 jt. "Qiskit: avatud lähtekoodiga raamistik kvantarvutite jaoks" (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard ja Eugene Tang. "QAOA takerdub heast klassikalisest keelpillist alustades" (2022).

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

[10] Stefan H Sack, Raimel A Medina, Richard Kueng ja Maksym Serbyn. "Kvantligikaudse optimeerimisalgoritmi rekursiivne ahne initsialiseerimine garanteeritud paranemisega". Füüsiline ülevaade A 107, 062404 (2023).
https://​/​doi.org/​10.1103/​PhysRevA.107.062404

[11] Stefan H Sack ja Maksym Serbyn. "Kvantligikaudse optimeerimisalgoritmi kvantlõõmutamise lähtestamine". quantum 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler ja Mihhail D Lukin. "Kvantligikaudne optimeerimisalgoritm: jõudlus, mehhanism ja rakendamine lähiaja seadmetes". Physical Review X 10, 021067 (2020).
https://​/​doi.org/​10.1103/​PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski ja Travis S Humble. "Parameetrite ülekanne kaalutud max lõike kvantumbkaudseks optimeerimiseks". ACM Transactions on Quantum Computing 4, 1–15 (2023).
https://​/​doi.org/​10.1145/​3584706

[14] Aleksei Galda, Xiaoyuan Liu, Danylo Lykov, Juri Aleksejev ja Ilja Safro. "Optimaalsete QAOA parameetrite ülekandmine juhuslike graafikute vahel". 2021. aastal toimub IEEE rahvusvaheline kvantarvutite ja -tehnoloogia konverents (QCE). Lk 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 ja Daniel J Egger. "Kvantligikaudse optimeerimisalgoritmi skaleerimine ülijuhtival kubitil põhineval riistvaral". 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 ja Travis S Humble. "Kvant-ligikaudse optimeerimise skaleerimine lähiajal riistvaras". Scientific Reports 12, 12388 (2022).
https://​/​doi.org/​10.1038/​s41598-022-14767-w

[17] Gian Giacomo Guerreschi ja Anne Y Matsuura. "QAOA max-cut jaoks nõuab kvantkiirendamiseks sadu kubitte." Teaduslikud aruanded 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra ja Vedran Dunjko. "Kvantida või mitte kvantida: algoritmi valimise suunas lähiajalises kvantoptimeerimises". Quantum Science and Technology 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell ja Edward Dahl. "Kõrgeima järgu QAOA". 2022. aastal toimus IEEE 19. rahvusvaheline tarkvaraarhitektuuri kaaslase konverents (ICSA-C). Lk 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 ja George Siopsis. "QAOA graafistruktuuride mõju maxcutile". Quantum Information Processing 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​ja Daniel J Egger. “Pigistamine ja kvantiproksimaalne optimeerimine” (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg ja Ilja Safro. "Klassikalised sümmeetriad ja kvantumbkaudne optimeerimisalgoritm". Quantum Information Processing 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz ja Peter Love. “Maxcut quantum apimated optimization algoritmi toimivusgarantiid p> 1 jaoks”. Füüsiline ülevaade A 103, 042612 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone ja Sam Gutmann. "Kvantalgoritmid fikseeritud qubit arhitektuuridele" (2017).

[25] Sergei Bravyi, Alexander Kliesch, Robert Koenig ja Eugene Tang. "Sümmeetriakaitsest tulenevad variatsioonikvantide optimeerimise takistused". Physical Review Letters 125, 260505 (2020).
https://​/​doi.org/​10.1103/​PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik ja Sam Gutmann. "Kvantligikaudne optimeerimisalgoritm peab nägema kogu graafikut: tüüpiline juhtum" (2020).

[27] Sergei Bravyi, Alexander Kliesch, Robert Koenig ja Eugene Tang. "Kvantklassikalised hübriidalgoritmid ligikaudseks graafiku värvimiseks". Quantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. "Klassikalised ja kvantpiiritud sügavuse lähendamise algoritmid" (2019).

[29] Kunal Marwaha. "Kohalik klassikaline max-cut algoritm ületab kõrge ümbermõõduga tavalistel graafikutel QAOA $ p= 2 $." Quantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak ja Kunal Marwaha. "Klassikalised algoritmid ja kvantpiirangud suure ümbermõõduga graafikute maksimaalseks lõikamiseks" (2021).
https://​/​doi.org/​10.4230/​LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler ja Swati Gupta. "Klassikalise ja kvantmuusika ühendamine SDP-ga lähtestatud QAOA soojakäivitusega". 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 ja Rupak Biswas. "Kvantligikaudsest optimeerimisalgoritmist kuni kvantvahelduva operaatorini ansatz". Algoritmid 12 (2019).
https://​/​doi.org/​10.3390/​a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy ja Eleanor G. Rieffel. “$xy$ mikserid: analüütilised ja numbrilised tulemused kvantvahelduva operaatori ansatz jaoks”. 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 ja Sophia E. Economou. "Adaptiivne kvantumbkaudne optimeerimisalgoritm kombinatoorsete probleemide lahendamiseks kvantarvutis". Phys. Rev. Research 4, 033029 (2022).
https://​/​doi.org/​10.1103/​PhysRevResearch.4.033029

[35] Andreas Bärtschi ja Stephan Eidenbenz. "Groveri segistid QAOA jaoks: keerukuse nihutamine segisti projekteerimiselt oleku ettevalmistamisele". 2020. aastal toimub IEEE rahvusvaheline kvantarvutite ja -tehnoloogia konverents (QCE). Lk 72–82. IEEE (2020).
https://​/​doi.org/​10.1109/​QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel ja Zhihui Wang. Peaaegu optimaalne kvantahel Groveri struktureerimata otsingu jaoks, kasutades põikvälja. Füüsiline ülevaade A 95, 062317 (2017).
https://​/​doi.org/​10.1103/​PhysRevA.95.062317

[37] Lov K Grover. "Kiire kvantmehaaniline algoritm andmebaasi otsimiseks". Väljaandes Proceedings of the Kahekümne kaheksanda iga-aastase ACM-i sümpoosioni andmetöötlusteoorias. Lk 212–219. (1996).
https://​/​doi.org/​10.1145/​237814.237866

[38] Yin Zhang, Samuel Burer ja Renato DC Monteiro. "Rõõgastusheuristika 2. järgu max-cut ja muude binaarsete ruutprogrammide jaoks". SIAM Journal on Optimization 12, 503–521 (2001).
https://​/​doi.org/​10.1137/​S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari ja Roberto Imbuzeiro Oliveira. "Sünkroonimis- ja maxcut-probleemide lahendamine grothendiecki ebavõrdsuse kaudu". Õppeteooria konverentsil. Lk 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh ja Kevin Thompson. "Optimaalne produkti-oleku lähendamine 2-kohaliste positiivsete terminitega kvant-Hamiltoni jaoks" (2022). arXiv:2206.08342.
arXiv: 2206.08342

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

[42] Howard Karloff. "Kui hea on Goemansi-Williamsoni MAX-CUT algoritm?". 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 jt. "Mittetasapinnaliste graafikuprobleemide kvant-ligikaudne optimeerimine tasapinnalises ülijuhtivas protsessoris". 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 ja Jay M. Gambetta. "Mõõtmisvigade leevendamine mitmebitistes katsetes". Phys. Rev. A 103, 042605 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042605

[45] George S. Barron ja Christopher J. Wood. "Mõõtmisvea leevendamine variatsioonikvantalgoritmide jaoks" (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 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 Vanho Vasvan , Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu ja Xiaoqiang Zheng. "TensorFlow: Suuremahuline masinõpe heterogeensetes süsteemides" (2015).

[47] Diederik P. Kingma ja Jimmy Ba. “Adam: Stohhastilise optimeerimise meetod” (2014).

[48] Roger Fletcher. "Praktilised optimeerimismeetodid (2. väljaanne)". John Wiley ja pojad. New York, NY, USA (1987).
https://​/​doi.org/​10.1002/​9781118723203

[49] MJD Powell. "Otseotsingu optimeerimise meetod, mis modelleerib eesmärgi ja piirangu funktsioone lineaarse interpolatsiooni abil". 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. "Maatriksanalüüs teadlastele ja inseneridele". Köide 91. Siam. (2005).
https://​/​doi.org/​10.1137/​1.9780898717907

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

[52] A. Kaveh ja H. Rahami. "Graafiproduktide omajaotuse ühtne meetod". Kommunikatsioonid numbriliste meetodite inseneritöös biomeditsiiniliste rakendustega 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Špacapan. "Graafikute descartes'i korrutiste ühenduvus". Rakendusmatemaatika Letters 21, 682–685 (2008).
https://​/​doi.org/​10.1016/​j.aml.2007.06.010

[54] Jacek Gondzio ja Andreas Grothey. "Mittelineaarse finantsplaneerimise probleemide lahendamine 109 otsustusmuutuja abil massiliselt paralleelsetes arhitektuurides". WIT tehingud modelleerimise ja simulatsiooni kohta 43 (2006).
https://​/​doi.org/​10.2495/​CF060101

[55] Fänn RK Chung. "Spektraalgraafi teooria". Köide 92. American Mathematical Soc. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] MA Nielsen ja IL Chuang. "Kvantarvutus ja kvantteave: 10. aastapäeva väljaanne". 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 ja Benjamin Nachman. "Arvutuslikult tõhus nullmüra ekstrapoleerimine kvantvärava vea leevendamiseks". Physical Review A 105, 042406 (2022).
https://​/​doi.org/​10.1103/​PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala ja Kristan Temme. "Tõenäosuslik vigade tühistamine hõredate pauli-lindblad mudelitega mürarikastel kvantprotsessoritel". Loodusfüüsika lk 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick ja Frédéric Roupin. "BiqCrunch: poolkindla haru ja sidemega meetod binaarsete ruutprobleemide lahendamiseks". ACM tehingud matemaatilise tarkvaraga 43 (2017).
https://​/​doi.org/​10.1145/​3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer ja Matt McGinnis. "Hammingi graafikute, johnsoni graafikute ja muude klassikaliste parameetritega kaugusregulaarsete graafikute väikseimad omaväärtused". Journal of Combinatorial Theory, seeria B 133, 88–121 (2018).
https://​/​doi.org/​10.1016/​j.jctb.2018.04.005

[61] Donald Knuth. "Kombinatoorsed maatriksid". Valitud ettekanded diskreetse matemaatika kohta (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Viidatud

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner ja 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 ja Marco Pistoia, „Algne oleku ja mikseri joondamine parandab QAOA jõudlust piiratud portfelli optimeerimiseks”, arXiv: 2305.03857, (2023).

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

[4] Andrew Vlasic, Salvatore Certo ja Anh Pham, „Täiendada Groveri otsingualgoritmi: amplituudi summutamise rakendamine”, arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele ja Procolo Lucignano, "Digitiseeritud-vastudiabaatilise QAOA lähenemine: vooluringi sügavus versus vabad parameetrid", arXiv: 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble ja Creston D. Herold, "Müra modelleerimine globaalsetes Mølmer-Sørenseni interaktsioonides, rakendatud kvantumbkaudsele optimeerimisele", Füüsiline ülevaade A 107 6, 062406 (2023).

[7] Guoming Wang, "Klassikaliselt võimendatud kvantoptimeerimise algoritm", arXiv: 2203.13936, (2022).

Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2023-09-27 01:31:19). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.

On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2023-09-27 01:31:17).

Ajatempel:

Veel alates Quantum Journal