A melegindítású QAOA egyedi keverőkkel bizonyíthatóan konvergál, és számításilag felülmúlja a Goemans-Williamson-féle Max-Cut-ot alacsony áramköri mélységeken

A melegindítású QAOA egyedi keverőkkel bizonyíthatóan konvergál, és számításilag felülmúlja a Goemans-Williamson-féle Max-Cut-ot alacsony áramköri mélységeken

Reuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3és 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

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

Általánosítjuk Farhi et al. kvantumközelítő optimalizálási algoritmusát (QAOA). (2014) segítségével tetszőlegesen szétválasztható kezdeti állapotokat tesz lehetővé megfelelő keverőkkel úgy, hogy a kiindulási állapot a keverő Hamilton-féle leggerjesztettebb állapota legyen. A QAOA ezen verzióját, amelyet $QAOA-legmelegebb$-nak nevezünk, a Max-Cut szimulálásával mutatjuk be súlyozott grafikonokon. Inicializáljuk a kiindulási állapotot $warm-start$-ként $2$ és $3$-dimenziós közelítésekkel, amelyeket a Max-Cut félig határozott programjának megoldásainak véletlenszerű vetületeivel kapunk, és definiálunk egy melegindítástól függő $custom mixert$. Megmutatjuk, hogy ezek a melegindítások inicializálják a QAOA áramkört 0.658 dolláros konstans tényező közelítéssel a 2 dolláros dimenziós és 0.585 dolláros 3 dolláros dimenziós melegindításokkal a nem negatív élsúllyal rendelkező gráfok esetében, javítva a korábban ismert triviális ( azaz 0.5 $ standard inicializálás esetén) a legrosszabb eset határértékei $p=0$-nál. Ezek a tényezők valójában alacsonyabbak a Max-Cut esetében elért közelítésnél magasabb áramköri mélységeknél, mivel azt is megmutatjuk, hogy a QAOA-legmelegebb bármilyen elkülöníthető kezdeti állapot esetén a Max-Cut-hoz konvergál az adiabatikus határ alatt $prightarrow infty$-ként. A melegindítások kiválasztása azonban jelentősen befolyásolja a Max-Cut-hoz való konvergencia sebességét, és empirikusan megmutatjuk, hogy melegindításaink gyorsabb konvergenciát érnek el a meglévő megközelítésekhez képest. Ezenkívül numerikus szimulációink jobb minőségű vágásokat mutatnak, mint a szabványos QAOA, a klasszikus Goemans-Williamson algoritmus, és egy melegindítású QAOA egyedi keverők nélkül a 1148 dolláros grafikonok (11 dolláros csomópontokig) és a mélység $p=8 példánykönyvtárában. $. Megmutatjuk továbbá, hogy a QAOA-legmelegebb teljesítmény felülmúlja Farhi és munkatársai szabványos QAOA-ját. a jelenlegi IBM-Q és Quantinuum hardvereken végzett kísérletekben.

A Quantum approximate Optimation Algorithm (QAOA) egy hibrid kvantum-klasszikus technika a kombinatorikus optimalizáláshoz, amely minden klasszikus optimalizálónál erősebbnek ígérkezik. Ebben a munkában egy alapvető kombinatorikus optimalizálási probléma, a Max-Cut néven ismert lehetőségeit szemléltetjük, ahol a lehető legjobb klasszikus algoritmus Goemans és Williamson (GW) algoritmusa. Ezt úgy érjük el, hogy a QAOA-ba bevezetjük a klasszikusan előállított melegindításokat, módosított keverőoperátorokkal, és számítási úton megmutatjuk, hogy ez felülmúlja a GW-t. Megfelelően módosítjuk a kvantumalgoritmust, hogy fenntartsuk a kapcsolatot a kvantumadiabatikus számítástechnikával; Megbeszéljük az elméletet, és számszerű és kísérleti bizonyítékokkal szolgálunk, amelyek bemutatják megközelítésünk ígéretét.

► BibTeX adatok

► Referenciák

[1] John Preskill. „Kvantumszámítástechnika a NISQ-korszakban és azon túl”. Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow és Ashley Montanaro. „Kvantumszámítási fölény”. Nature 549, 203–209 (2017).
https://​/​doi.org/​10.1038/​nature23458

[3] Edward Farhi, Jeffrey Goldstone és Sam Gutmann. „A kvantumközelítő optimalizálási algoritmus” (2014).

[4] Iain Dunning, Swati Gupta és John Silberholz. „Mi mikor működik a legjobban? A Max-Cut és a QUBO heurisztikáinak szisztematikus értékelése”. INFORMÁL Journal on Computing 30 (2018).
https://​/​doi.org/​10.1287/​ijoc.2017.0798

[5] Michel X Goemans és David P Williamson. „Továbbfejlesztett közelítési algoritmusok maximális vágási és kielégítési problémákhoz félig meghatározott programozással”. Journal of the ACM (JACM) 42, 1115–1145 (1995).
https://​/​doi.org/​10.1145/​227683.227684

[6] Samuel Burer és Renato DC Monteiro. „Egy nemlineáris programozási algoritmus félig meghatározott programok megoldására alacsony rangú faktorizációval”. Matematikai programozás 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 és mások. „Qiskit: Nyílt forráskódú keretrendszer a kvantumszámításhoz” (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard és Eugene Tang. „A QAOA megakad egy jó klasszikus vonóstól kezdve” (2022).

[9] Daniel J. Egger, Jakub Mareček és Stefan Woerner. „Melegindítású kvantumoptimalizálás”. Quantum 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack, Raimel A Medina, Richard Kueng és Maksym Serbyn. „A kvantumközelítő optimalizálási algoritmus rekurzív mohó inicializálása garantált javulással”. Fizikai Szemle A 107, 062404 (2023).
https://​/​doi.org/​10.1103/​PhysRevA.107.062404

[11] Stefan H Sack és Maksym Serbyn. „A kvantumközelítő optimalizálási algoritmus kvantum-illesztési inicializálása”. quantum 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler és Mikhail D Lukin. „Kvantum közelítő optimalizálási algoritmus: Teljesítmény, mechanizmus és megvalósítás rövid távú eszközökön”. Physical Review X 10, 021067 (2020).
https://​/​doi.org/​10.1103/​PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski és Travis S Humble. „Paraméterátvitel a súlyozott max. vágás kvantumközelítő optimalizálásához”. ACM Transactions on Quantum Computing 4, 1–15 (2023).
https://​/​doi.org/​10.1145/​3584706

[14] Alekszej Galda, Xiaoyuan Liu, Danylo Lykov, Jurij Alekszejev és Ilja Safro. „Az optimális QAOA paraméterek átvitele véletlenszerű gráfok között”. 2021-ben az IEEE nemzetközi kvantumszámítási és mérnöki konferenciája (QCE). 171–180. oldal. IEEE (2021).
https://​/​doi.org/​10.1109/​QCE52317.2021.00034

[15] Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner és Daniel J Egger. „A kvantumközelítő optimalizálási algoritmus skálázása szupravezető qubit alapú hardveren”. 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 és Travis S Humble. „Kvantum közelítő optimalizálás skálázása rövid távú hardveren”. Scientific Reports 12, 12388 (2022).
https://​/​doi.org/​10.1038/​s41598-022-14767-w

[17] Gian Giacomo Guerreschi és Anne Y Matsuura. "A max-cut QAOA-hoz több száz qubit szükséges a kvantumgyorsításhoz." Tudományos jelentések 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra és Vedran Dunjko. „Kvantumozni vagy nem kvantumozni: az algoritmusválasztás felé a rövid távú kvantumoptimalizálásban”. Quantum Science and Technology 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell és Edward Dahl. „Legmagasabb minőségű QAOA”. 2022-ben az IEEE 19. nemzetközi konferenciája a Software Architecture Companionról (ICSA-C). 141–146. oldal. IEEE (2022).
https://​/​doi.org/​10.1109/​ICSA-C54293.2022.00035

[20] Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble és George Siopsis. „A QAOA gráfstruktúráinak hatása a maxcut-ra”. Quantum Information Processing 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​és Daniel J Egger. „Kiszorítás és kvantumközelítő optimalizálás” (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg és Ilya Safro. „Klasszikus szimmetriák és a kvantumközelítő optimalizálási algoritmus”. Quantum Information Processing 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz és Peter Love. „Maxcut kvantumközelítő optimalizálási algoritmus teljesítménygaranciák p> 1 esetén”. Physical Review A 103, 042612 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone és Sam Gutmann. „Kvantumalgoritmusok rögzített qubit architektúrákhoz” (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig és Eugene Tang. „A variációs kvantumoptimalizálás akadályai a szimmetriavédelemből”. Physical Review Letters 125, 260505 (2020).
https://​/​doi.org/​10.1103/​PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik és Sam Gutmann. „A kvantumközelítő optimalizáló algoritmusnak látnia kell a teljes grafikont: tipikus eset” (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig és Eugene Tang. „Hibrid kvantum-klasszikus algoritmusok közelítő gráfszínezéshez”. Quantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. „Klasszikus és kvantumkorlátos mélységközelítő algoritmusok” (2019).

[29] Kunal Marwaha. „A helyi klasszikus max-cut algoritmus felülmúlja a $ p= 2$ QAOA-t nagy kerületű szabályos grafikonokon”. Quantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak és Kunal Marwaha. „Klasszikus algoritmusok és kvantumkorlátozások a maximális vágáshoz nagy kerületű gráfokon” (2021).
https://​/​doi.org/​10.4230/​LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler és Swati Gupta. „A klasszikus és a kvantum áthidalása SDP inicializált melegindításokkal a QAOA-hoz”. 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 és Rupak Biswas. „A kvantumközelítő optimalizáló algoritmustól az ansatz kvantum-alternáló operátorig”. Algoritmusok 12 (2019).
https://​/​doi.org/​10.3390/​a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy és Eleanor G. Rieffel. „$xy$ keverők: Analitikai és numerikus eredmények az ansatz kvantumváltó operátorhoz”. 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 és Sophia E. Economou. „Adaptív kvantumközelítő optimalizáló algoritmus kombinatorikus problémák megoldására kvantumszámítógépen”. Phys. Rev. Research 4, 033029 (2022).
https://​/​doi.org/​10.1103/​PhysRevResearch.4.033029

[35] Andreas Bärtschi és Stephan Eidenbenz. „Grover keverők QAOA-hoz: A bonyolultság áttérés a keverőtervezésről az állapot előkészítésére”. 2020-ban IEEE Nemzetközi Kvantum Számítástechnikai és Mérnöki Konferencia (QCE). 72–82. oldal. IEEE (2020).
https://​/​doi.org/​10.1109/​QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel és Zhihui Wang. „Közel optimális kvantumáramkör Grover strukturálatlan kereséséhez keresztirányú mező használatával”. Fizikai Szemle A 95, 062317 (2017).
https://​/​doi.org/​10.1103/​PhysRevA.95.062317

[37] Szeretem K Grover. „Gyors kvantummechanikai algoritmus adatbázis-kereséshez”. In Proceedings of the huszonnyolcadik éves ACM szimpózium a számítástechnika elméletéről. 212–219. oldal. (1996).
https://​/​doi.org/​10.1145/​237814.237866

[38] Yin Zhang, Samuel Burer és Renato DC Monteiro. „Rang-2 relaxációs heurisztika max-cut és egyéb bináris négyzetes programokhoz”. SIAM Journal on Optimization 12, 503–521 (2001).
https://​/​doi.org/​10.1137/​S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari és Roberto Imbuzeiro Oliveira. „Sdps megoldása szinkronizáláshoz és maxcut problémákhoz a grothendieck egyenlőtlenségen keresztül”. Tanuláselméleti konferencián. 1476–1515. oldal. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh és Kevin Thompson. „Optimális szorzatállapot közelítés 2-lokális kvantum-Hamiltonokhoz pozitív tagokkal” (2022). arXiv:2206.08342.
arXiv: 2206.08342

[41] Reuben Tate és Swati Gupta. „Ci-qube”. GitHub adattár (2021). url: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] Howard Karloff. „Mennyire jó a Goemans–Williamson MAX-CUT algoritmus?”. 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 és mások. „Nem síkbeli gráfproblémák kvantumközelítő optimalizálása síkbeli szupravezető processzoron”. 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 és Jay M. Gambetta. „Mérési hibák mérséklése multiqubites kísérletekben”. Phys. Rev. A 103, 042605 (2021).
https://​/​doi.org/​10.1103/​PhysRevA.103.042605

[45] George S. Barron és Christopher J. Wood. „Mérési hiba mérséklése variációs kvantum-algoritmusokhoz” (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 Vasvanude , Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu és Xiaoqiang Zheng. „TensorFlow: Nagyléptékű gépi tanulás heterogén rendszereken” (2015).

[47] Diederik P. Kingma és Jimmy Ba. „Adam: A metódus a sztochasztikus optimalizáláshoz” (2014).

[48] Roger Fletcher. „Az optimalizálás gyakorlati módszerei (2. kiadás)”. John Wiley és fiai. New York, NY, USA (1987).
https://​/​doi.org/​10.1002/​9781118723203

[49] MJD Powell. „Közvetlen keresés optimalizálási módszer, amely lineáris interpolációval modellezi a cél- és kényszerfüggvényeket”. 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. „Mátrixelemzés tudósoknak és mérnököknek”. 91. kötet Sziám. (2005).
https://​/​doi.org/​10.1137/​1.9780898717907

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

[52] A. Kaveh és H. Rahami. „Egységes módszer gráftermékek sajátfelbontására”. Communications in Numerical Methods in Engineering with Biomedical Applications 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Špacapan. „Grófok derékszögű szorzatainak összekapcsolása”. Applied Mathematics Letters 21, 682–685 (2008).
https://​/​doi.org/​10.1016/​j.aml.2007.06.010

[54] Jacek Gondzio és Andreas Grothey. „Nemlineáris pénzügyi tervezési problémák megoldása 109 döntési változóval masszívan párhuzamos architektúrákon”. WIT Transactions on Modeling and Simulation 43 (2006).
https://​/​doi.org/​10.2495/​CF060101

[55] Fan RK Chung. „Szektrális gráf elmélet”. 92. kötet American Mathematical Soc. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] MA Nielsen és IL Chuang. „Kvantumszámítás és kvantuminformáció: 10. évfordulós kiadás”. 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 és Benjamin Nachman. „Számításilag hatékony nulla zaj extrapoláció a kvantumkapu-hiba mérséklésére”. Physical Review A 105, 042406 (2022).
https://​/​doi.org/​10.1103/​PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala és Kristan Temme. „Valószínűségi hibaelhárítás ritka pauli–lindblad modellekkel zajos kvantumprocesszorokon”. Nature Physics 1–6. oldal (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick és Frédéric Roupin. „BiqCrunch: Félig meghatározott elágazás és kötött módszer bináris másodfokú problémák megoldására”. ACM-tranzakciók matematikai szoftveren 43 (2017).
https://​/​doi.org/​10.1145/​3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer és Matt McGinnis. „A Hamming-gráfok, Johnson-gráfok és más, klasszikus paraméterekkel rendelkező távolságszabályos gráfok legkisebb sajátértékei”. Journal of Combinatorial Theory, B sorozat 133, 88–121 (2018).
https://​/​doi.org/​10.1016/​j.jctb.2018.04.005

[61] Donald Knuth. „Kombinatorikus mátrixok”. Válogatott dolgozatok a diszkrét matematikáról (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Idézi

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

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun és Marco Pistoia, „A kezdeti állapot és a keverő közötti összehangolás javítja a QAOA teljesítményét a korlátozott portfólióoptimalizáláshoz”, arXiv: 2305.03857, (2023).

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

[4] Andrew Vlasic, Salvatore Certo és Anh Pham, „Complement Grover's Search Algorithm: An Amplitude Suppression Implementation”, arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele és Procolo Lucignano, „A digitalizált-ellendiabatikus QAOA konvergenciája: áramkörmélység versus szabad paraméterek”, arXiv: 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble és Creston D. Herold, „Modeling noise in global Mølmer-Sørensen Interactions used to quantum approximate optimization”, Fizikai áttekintés A 107 6, 062406 (2023).

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

A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2023-09-27 01:31:19). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.

On Crossref által idézett szolgáltatás művekre hivatkozó adat nem található (utolsó próbálkozás 2023-09-27 01:31:17).

Időbélyeg:

Még több Quantum Journal