QAOA cu pornire caldă, cu mixere personalizate, converge în mod dovedibil și învinge din punct de vedere computerizat limita maximă a lui Goemans-Williamson la adâncimi joase a circuitului

QAOA cu pornire caldă, cu mixere personalizate, converge în mod dovedibil și învinge din punct de vedere computerizat limita maximă a lui Goemans-Williamson la adâncimi joase a circuitului

Marca temporală: 26 septembrie 2023, ora 9:22

Reuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3, și Swati Gupta4

1CCS-3 Științe informaționale, Laboratorul Național Los Alamos, Los Alamos, NM 87544, SUA
2Georgia Institute of Technology, Atlanta, GA 30332, SUA
3Georgia Tech Research Institute, Atlanta, GA 30332, SUA
4Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02142, SUA

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Generalizăm algoritmul de optimizare cuantică aproximativă (QAOA) al lui Farhi și colab. (2014) pentru a permite stări inițiale separabile arbitrare cu mixere corespunzătoare, astfel încât starea de pornire să fie cea mai excitată stare a hamiltonianului de amestecare. Demonstrăm această versiune a QAOA, pe care o numim $QAOA-warmest$, prin simularea Max-Cut pe grafice ponderate. Inițializam starea de pornire ca $pornire la cald$ folosind aproximări dimensionale $2$ și $3$ obținute folosind proiecții aleatorii ale soluțiilor programului semidefinit al lui Max-Cut și definim un $mixer personalizat dependent de pornire la cald. Arătăm că aceste porniri la cald inițializează circuitul QAOA cu aproximări cu factor constant de 0.658$ pentru 2$-dimensional și 0.585$ pentru 3$-dimensionale porniri la cald pentru grafice cu greutăți de margine nenegative, îmbunătățind trivialul cunoscut anterior ( adică $0.5$ pentru inițializare standard) limite în cel mai rău caz la $p=0$. Acești factori, de fapt, limitează inferioară aproximarea realizată pentru Max-Cut la adâncimi mai mari de circuit, deoarece arătăm, de asemenea, că QAOA-mai cald cu orice stare inițială separabilă converge către Max-Cut sub limita adiabatică ca $prightarrow infty$. Cu toate acestea, alegerea pornirilor la cald are un impact semnificativ asupra ratei de convergență la Max-Cut și arătăm empiric că pornirile noastre la cald ating o convergență mai rapidă în comparație cu abordările existente. În plus, simulările noastre numerice arată reduceri de calitate superioară în comparație cu QAOA standard, algoritmul clasic Goemans-Williamson și un QAOA cu pornire caldă fără mixere personalizate pentru o bibliotecă de instanțe de grafice de $1148$ (până la $11$ noduri) și adâncime $p=8 $. Mai arătăm că QAOA-mai cald depășește QAOA standard al lui Farhi și colab. în experimente pe hardware-ul actual IBM-Q și Quantinuum.

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.

Imagine prezentată: Performanța QAOA-cea mai caldă (cu porniri la cald) și QAOA standard în funcție de adâncimea QAOA pentru o simulare ideală (punctată) și zgomotoasă (punctată). Pentru graficul cu 20 de noduri ales, GW atinge un raport de aproximare de 0.912, în timp ce, în cazul ideal, QAOA mai cald depășește GW pentru $p geq 2$, în timp ce QAOA standard necesită $p > 4$. Simularea zgomotului se bazează pe datele de calibrare de la dispozitivul Guadalupe de la IBM-Q.

Rezumat popular

Algoritmul de optimizare cuantică aproximativă (QAOA) este o tehnică hibridă cuantică-clasică pentru optimizarea combinatorie care promite a fi mai puternică decât orice optimizator clasic. În această lucrare, exemplificam potențialul său pe o problemă fundamentală de optimizare combinatorie, cunoscută sub numele de Max-Cut, unde cel mai bun algoritm clasic posibil este cel de Goemans și Williamson (GW). Obținem acest lucru prin introducerea pornirilor la cald obținute în mod clasic în QAOA, cu operatori de amestecare modificați și arătăm din punct de vedere computațional că acest lucru depășește GW. Modificăm algoritmul cuantic în mod corespunzător pentru a menține conexiunea cu calculul adiabatic cuantic; discutăm teorie și oferim dovezi numerice și experimentale care arată promisiunea abordării noastre.

► Date BibTeX

► Referințe

[1] John Preskill. „Calcul cuantic în era NISQ și nu numai”. Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[2] Aram W. Harrow și Ashley Montanaro. „Supremația computațională cuantică”. Natura 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

[3] Edward Farhi, Jeffrey Goldstone și Sam Gutmann. „Un algoritm de optimizare cuantică aproximativă” (2014).

[4] Iain Dunning, Swati Gupta și John Silberholz. „Ce funcționează cel mai bine când? O evaluare sistematică a euristicii pentru Max-Cut și QUBO”. INFORMS Journal on Computing 30 (2018).
https://​/​doi.org/​10.1287/​ijoc.2017.0798

[5] Michel X Goemans și David P Williamson. „Algoritmi de aproximare îmbunătățiți pentru probleme de tăiere maximă și de satisfacție folosind programarea semidefinită”. Journal of the ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684

[6] Samuel Burer și Renato DC Monteiro. „Un algoritm de programare neliniară pentru rezolvarea de programe semidefinite prin factorizare de rang scăzut”. Programare matematică 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: Un cadru open-source pentru calculul cuantic” (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard și Eugene Tang. „QAOA se blochează pornind de la o coardă clasică bună” (2022).

[9] Daniel J. Egger, Jakub Mareček și Stefan Woerner. „Optimizare cuantică cu pornire la cald”. Quantum 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack, Raimel A Medina, Richard Kueng și Maksym Serbyn. „Inițializarea recursiva lacomă a algoritmului de optimizare cuantică aproximativă cu îmbunătățire garantată”. Physical Review A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

[11] Stefan H Sack și Maksym Serbyn. „Inițializarea recoacirii cuantice a algoritmului de optimizare cuantică aproximativă”. cuantumul 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler și Mikhail D Lukin. „Algoritm de optimizare cuantică aproximativă: performanță, mecanism și implementare pe dispozitive pe termen scurt”. Physical Review X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski și Travis S Humble. „Transferul parametrilor pentru optimizarea cuantică aproximativă a tăieturii maxime ponderate”. Tranzacții ACM pe calculul cuantic 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706

[14] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev și Ilya Safro. „Transferabilitatea parametrilor optimi QAOA între grafice aleatorii”. În 2021, IEEE International Conference on Quantum Computing and Engineering (QCE). Paginile 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 și Daniel J Egger. „Scalarea algoritmului de optimizare cuantică aproximativă pe hardware bazat pe qubit supraconductor”. 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 și Travis S Humble. „Scalarea optimizării aproximative cuantice pe hardware pe termen scurt”. Scientific Reports 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

[17] Gian Giacomo Guerreschi și Anne Y Matsuura. „QAOA pentru max-cut necesită sute de qubiți pentru accelerarea cuantică”. Rapoarte științifice 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] Charles Moussa, Henri Calandra și Vedran Dunjko. „A cuantic sau nu a cuantic: spre selecția algoritmului în optimizarea cuantică pe termen scurt”. Quantum Science and Technology 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] Colin Campbell și Edward Dahl. „QAOA de cel mai înalt nivel”. În 2022, a 19-a Conferință Internațională IEEE privind însoțitorul de arhitectură software (ICSA-C). Paginile 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 și George Siopsis. „Impactul structurilor grafice pentru QAOA asupra maxcut”. Procesarea informațiilor cuantice 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​și Daniel J Egger. „Strângerea și optimizarea aproximativă cuantică” (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg și Ilya Safro. „Simetrii clasice și algoritmul de optimizare cuantică aproximativă”. Procesarea informațiilor cuantice 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] Jonathan Wurtz și Peter Love. „Performanța algoritmului de optimizare cuantică aproximativă Maxcut garantează pentru p> 1”. Physical Review A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

[24] Edward Farhi, Jeffrey Goldstone și Sam Gutmann. „Algoritmi cuantici pentru arhitecturi cu qubit fix” (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig și Eugene Tang. „Obstacole în calea optimizării cuantice variaționale din protecția simetriei”. Physical Review Letters 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[26] Edward Farhi, David Gamarnik și Sam Gutmann. „Algoritmul de optimizare cuantică aproximativă trebuie să vadă întregul grafic: Un caz tipic” (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig și Eugene Tang. „Algoritmi cuantici-clasici hibridi pentru colorarea aproximativă a graficelor”. Quantum 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] Matthew B Hastings. „Algoritmi de aproximare a adâncimii mărginiți clasici și cuantici” (2019).

[29] Kunal Marwaha. „Algoritmul de tăiere maximă clasică locală depășește $ p= 2$ QAOA pe graficele obișnuite cu circumferință mare”. Quantum 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] Boaz Barak și Kunal Marwaha. „Algoritmi clasici și limitări cuantice pentru tăierea maximă pe grafice cu circumferință mare” (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler și Swati Gupta. „Legătura dintre clasic și cuantic cu pornirile la cald inițializate SDP pentru QAOA”. Tranzacții ACM pe calculul cuantic (2022).
https: / / doi.org/ 10.1145 / 3549554

[32] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli și Rupak Biswas. „De la algoritmul de optimizare cuantică aproximativă la un operator cuantic alternativ ansatz”. Algoritmi 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy și Eleanor G. Rieffel. „$xy$ mixere: rezultate analitice și numerice pentru operatorul alternativ cuantic ansatz”. Fiz. 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 și Sophia E. Economou. „Algoritm adaptiv de optimizare cuantică aproximativă pentru rezolvarea problemelor combinatorii pe un computer cuantic”. Fiz. Rev. Research 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

[35] Andreas Bärtschi și Stephan Eidenbenz. „Amestecătoare Grover pentru QAOA: Trecerea complexității de la proiectarea mixerului la pregătirea în stare”. În 2020, IEEE International Conference on Quantum Computing and Engineering (QCE). Paginile 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] Zhang Jiang, Eleanor G Rieffel și Zhihui Wang. „Circuit cuantic aproape optim pentru căutarea nestructurată a lui Grover folosind un câmp transversal”. Physical Review A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

[37] Iubitor K Grover. „Un algoritm mecanic cuantic rapid pentru căutarea în baze de date”. În Actele celui de-al douăzeci și opta simpozion anual ACM despre teoria calculului. Paginile 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866

[38] Yin Zhang, Samuel Burer și Renato DC Monteiro. „Euristice de relaxare de rangul 2 pentru max-cut și alte programe binare pătratice”. SIAM Journal on Optimization 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari și Roberto Imbuzeiro Oliveira. „Rezolvarea sdps pentru probleme de sincronizare și maxcut prin inegalitatea grothendieck”. În Conferința despre teoria învățării. Paginile 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] Ojas Parekh și Kevin Thompson. „O aproximare optimă a stării produsului pentru hamiltonieni cuantici cu 2 locali cu termeni pozitivi” (2022). arXiv:2206.08342.
arXiv: 2206.08342

[41] Reuben Tate și Swati Gupta. „Ci-qube”. Depozitul GitHub (2021). url: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] Howard Karloff. „Cât de bun este algoritmul Goemans–Williamson MAX-CUT?”. 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 și colab. „Optimizarea aproximativă cuantică a problemelor grafice neplanare pe un procesor supraconductor plan”. 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 și Jay M. Gambetta. „Atenuarea erorilor de măsurare în experimentele multiqubit”. Fiz. Rev. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

[45] George S. Barron și Christopher J. Wood. „Atenuarea erorilor de măsurare pentru algoritmi cuantici variaționali” (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 și Xiaoqiang Zheng. „TensorFlow: Învățare automată la scară largă pe sisteme eterogene” (2015).

[47] Diederik P. Kingma și Jimmy Ba. „Adam: O metodă de optimizare stocastică” (2014).

[48] Roger Fletcher. „Metode practice de optimizare (ediția a II-a)”. John Wiley și fiii. New York, NY, SUA (2).
https: / / doi.org/ 10.1002 / 9781118723203

[49] MJD Powell. „O metodă de optimizare directă a căutării care modelează funcțiile obiectiv și de constrângere prin interpolare liniară”. 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. „Analiză matriceală pentru oameni de știință și ingineri”. Volumul 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 WissenschaftenPagini 456–477 (1912).

[52] A. Kaveh și H. Rahami. „O metodă unificată pentru compunerea proprie a produselor grafice”. Comunicări în metodele numerice în inginerie cu aplicații biomedicale 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

[53] Simon Špacapan. „Conectivitatea produselor carteziene ale graficelor”. Litere de matematică aplicată 21, 682–685 (2008).
https://​/​doi.org/​10.1016/​j.aml.2007.06.010

[54] Jacek Gondzio și Andreas Grothey. „Rezolvarea problemelor de planificare financiară neliniară cu 109 variabile de decizie pe arhitecturi masiv paralele”. WIT Transactions on Modeling and Simulation 43 (2006).
https://​/​doi.org/​10.2495/​CF060101

[55] Fan RK Chung. „Teoria grafurilor spectrale”. Volumul 92. American Mathematical Soc. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

[56] MA Nielsen și IL Chuang. „Calcul cuantic și informații cuantice: ediția a 10-a aniversare”. 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 și Benjamin Nachman. „Extrapolare zero-zgomot eficientă din punct de vedere informatic pentru atenuarea erorilor cuantice”. Physical Review A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala și Kristan Temme. „Anularea erorilor probabilistice cu modele pauli-lindblad rare pe procesoare cuantice zgomotoase”. Fizica naturiiPagini 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] Nathan Krislock, Jérôme Malick și Frédéric Roupin. „BiqCrunch: O metodă semidefinită de ramuri și legături pentru rezolvarea problemelor binare pătratice”. Tranzacții ACM pe software matematic 43 (2017).
https: / / doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer și Matt McGinnis. „Cele mai mici valori proprii ale graficelor hamming, ale graficelor johnson și ale altor grafice regulate la distanță cu parametri clasici”. Journal of Combinatorial Theory, Seria B 133, 88–121 (2018).
https://​/​doi.org/​10.1016/​j.jctb.2018.04.005

[61] Donald Knuth. „Matrici combinatorii”. Lucrări selectate despre matematică discretă (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Citat de

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner și Daniel J. Egger, „Scalarea algoritmului de optimizare cuantică aproximativă pe hardware bazat pe qubit supraconductor”, Quantum 6, 870 (2022).

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

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

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele și Procolo Lucignano, „Convergence of Digitized-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 și Creston D. Herold, „Modeling noise in global Mølmer-Sørensen interactions apply to quantum approximate optimization”, Revista fizică A 107 6, 062406 (2023).

[7] Guoming Wang, „Algoritmul de optimizare cuantică îmbunătățit clasic”, arXiv: 2203.13936, (2022).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2023-09-27 01:31:19). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2023-09-27 01:31:17).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic