Il QAOA avviato a caldo con mixer personalizzati converge in modo dimostrabile e batte a livello computazionale il Max-Cut di Goemans-Williamson a basse profondità del circuito

Il QAOA avviato a caldo con mixer personalizzati converge in modo dimostrabile e batte a livello computazionale il Max-Cut di Goemans-Williamson a basse profondità del circuito

Timestamp: 26 settembre 2023 9:22

Ruben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3e Swati Gupta4

1CCS-3 Scienze dell'informazione, Laboratorio nazionale di Los Alamos, Los Alamos, NM 87544, USA
2Georgia Institute of Technology, Atlanta, GA 30332, Stati Uniti
3Georgia Tech Research Institute, Atlanta, GA 30332, Stati Uniti
4Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02142, Stati Uniti

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Generalizziamo l'algoritmo di ottimizzazione approssimata quantistica (QAOA) di Farhi et al. (2014) per consentire stati iniziali separabili arbitrari con miscelatori corrispondenti in modo tale che lo stato iniziale sia lo stato più eccitato dell'Hamiltoniana di miscelazione. Dimostriamo questa versione di QAOA, che chiamiamo $QAOA-warmest$, simulando Max-Cut su grafici ponderati. Inizializziamo lo stato iniziale come $avvio a caldo$ utilizzando approssimazioni dimensionali di $2$ e $3$ ottenute utilizzando proiezioni randomizzate di soluzioni al programma semi-definito di Max-Cut e definiamo un $mixer personalizzato$ dipendente dall'avvio a caldo. Mostriamo che questi avviamenti a caldo inizializzano il circuito QAOA con approssimazioni con fattore costante di $ 0.658 $ per $ 2 $ dimensionali e $ 0.585 $ per $ 3 $ avviamenti a caldo dimensionali per grafici con pesi dei bordi non negativi, migliorando rispetto ai banali avviamenti precedentemente noti ( ovvero $0.5$ per l'inizializzazione standard) limite del caso peggiore a $p=0$. Questi fattori infatti limitano inferiore l'approssimazione ottenuta per Max-Cut a profondità del circuito più elevate, poiché mostriamo anche che QAOA-warmest con qualsiasi stato iniziale separabile converge a Max-Cut sotto il limite adiabatico come $prightarrow infty$. Tuttavia, la scelta degli avviamenti a caldo ha un impatto significativo sul tasso di convergenza verso Max-Cut e mostriamo empiricamente che i nostri avviamenti a caldo raggiungono una convergenza più rapida rispetto agli approcci esistenti. Inoltre, le nostre simulazioni numeriche mostrano tagli di qualità superiore rispetto al QAOA standard, al classico algoritmo di Goemans-Williamson e a un QAOA avviato a caldo senza mixer personalizzati per una libreria di istanze di grafici $1148$ (fino a $11$ nodi) e profondità $p=8 $. Mostriamo inoltre che il QAOA più caldo supera il QAOA standard di Farhi et al. in esperimenti sugli attuali hardware IBM-Q e Quantinuum.

Il QAOA avviato a caldo con mixer personalizzati converge in modo dimostrabile e batte dal punto di vista computazionale il Max-Cut di Goemans-Williamson a basse profondità di circuito PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Immagine in primo piano: prestazioni del QAOA più caldo (con avviamenti a caldo) e del QAOA standard in funzione della profondità del QAOA per una simulazione ideale (tratteggiata) e rumorosa (punteggiata). Per il grafico a 20 nodi scelto, GW raggiunge un rapporto di approssimazione di 0.912, mentre nel caso ideale, QAOA-warmest supera GW per $p geq 2$ mentre QAOA standard richiede $p > 4$. La simulazione del rumore si basa sui dati di calibrazione del dispositivo Guadalupe di IBM-Q.

Riepilogo popolare

L'algoritmo di ottimizzazione approssimata quantistica (QAOA) è una tecnica ibrida quantistica-classica per l'ottimizzazione combinatoria che promette di essere più potente di qualsiasi ottimizzatore classico. In questo lavoro, esempiamo il suo potenziale su un problema fondamentale di ottimizzazione combinatoria, noto come Max-Cut, dove il miglior algoritmo classico possibile è quello di Goemans e Williamson (GW). Raggiungiamo questo obiettivo introducendo avviamenti a caldo ottenuti in modo classico al QAOA, con operatori di miscelazione modificati, e mostriamo computazionalmente che questo supera GW. Modifichiamo opportunamente l'algoritmo quantistico per mantenere la connessione al calcolo adiabatico quantistico; discutiamo di teoria e forniamo prove numeriche e sperimentali che mostrano la promessa del nostro approccio.

► dati BibTeX

► Riferimenti

, Giovanni Preskill. "Quantum computing nell'era NISQ e oltre". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

, Aram W. Harrow e Ashley Montanaro. “Supremazia computazionale quantistica”. Natura 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

, Edward Farhi, Jeffrey Goldstone e Sam Gutmann. “Un algoritmo di ottimizzazione quantistica approssimata” (2014).

, Iain Dunning, Swati Gupta e John Silberholz. “Cosa funziona meglio e quando? Una valutazione sistematica delle euristiche per Max-Cut e QUBO”. INFORMA Journal on Computing 30 (2018).
https: / / doi.org/ 10.1287 / ijoc.2017.0798

, Michel X Goemans e David P Williamson. "Algoritmi di approssimazione migliorati per problemi di massimo taglio e soddisfacibilità utilizzando la programmazione semidefinita". Giornale dell'ACM (JACM) 42, 1115–1145 (1995).
https: / / doi.org/ 10.1145 / 227683.227684 mila

, Samuel Burer e Renato DC Monteiro. "Un algoritmo di programmazione non lineare per risolvere programmi semidefiniti tramite fattorizzazione di basso rango". Programmazione matematica 95, 329–357 (2003).
https:/​/​doi.org/​10.1007/​s10107-002-0352-8

, Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, et al. "Qiskit: un framework open source per l'informatica quantistica" (2019).

, Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard e Eugene Tang. “Il QAOA si blocca partendo da una buona corda classica” (2022).

, Daniel J. Egger, Jakub Mareček e Stefan Woerner. "Ottimizzazione quantistica con avvio a caldo". Quantico 5, 479 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

, Stefan H Sack, Raimel A Medina, Richard Kueng e Maksym Serbyn. "Inizializzazione greedy ricorsiva dell'algoritmo di ottimizzazione approssimata quantistica con miglioramento garantito". Revisione fisica A 107, 062404 (2023).
https: / / doi.org/ 10.1103 / PhysRevA.107.062404

, Stefan H. Sack e Maksym Serbyn. "Inizializzazione della ricottura quantistica dell'algoritmo di ottimizzazione quantistica approssimata". quanto 5, 491 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

, Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler e Mikhail D Lukin. "Algoritmo di ottimizzazione quantistica approssimativa: prestazioni, meccanismo e implementazione su dispositivi a breve termine". Revisione fisica X 10, 021067 (2020).
https: / / doi.org/ 10.1103 / PhysRevX.10.021067

, Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski e Travis S Humble. "Trasferimento di parametri per l'ottimizzazione quantistica approssimata del maxcut ponderato". Transazioni ACM sull'informatica quantistica 4, 1–15 (2023).
https: / / doi.org/ 10.1145 / 3584706 mila

, Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev e Ilya Safro. "Trasferibilità dei parametri QAOA ottimali tra grafici casuali". Nel 2021 Conferenza internazionale IEEE sull'informatica e l'ingegneria quantistica (QCE). Pagine 171–180. IEEE (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00034

, Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner e Daniel J Egger. "Ridimensionamento dell'algoritmo di ottimizzazione approssimata quantistica su hardware basato su qubit superconduttori". Quantico 6, 870 (2022).
https:/​/​doi.org/​10.22331/​q-2022-12-07-870

, Phillip C Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis e Travis S Humble. "Ridimensionamento dell'ottimizzazione quantistica approssimativa su hardware a breve termine". Rapporti scientifici 12, 12388 (2022).
https: / / doi.org/ 10.1038 / s41598-022-14767-w

, Gian Giacomo Guerreschi e Anne Y Matsuura. "Il QAOA per il taglio massimo richiede centinaia di qubit per l'accelerazione quantistica". Rapporti scientifici 9, 1–7 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

, Charles Moussa, Henri Calandra e Vedran Dunjko. “A quantistici o non quantistici: verso la selezione dell’algoritmo nell’ottimizzazione quantistica a breve termine”. Scienza e tecnologia quantistica 5, 044009 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

, Colin Campbell e Edward Dahl. “QAOA di primissimo ordine”. Nel 2022 IEEE 19a Conferenza internazionale sul Software Architecture Companion (ICSA-C). Pagine 141–146. IEEE (2022).
https://​/​doi.org/​10.1109/​ICSA-C54293.2022.00035

, Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble e George Siopsis. "Impatto delle strutture grafiche per QAOA su maxcut". Elaborazione delle informazioni quantistiche 20, 1–21 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

, Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​e Daniel J Egger. “Squeezing e ottimizzazione quantistica approssimata” (2022).

, Ruslan Shaydulin, Stuart Hadfield, Tad Hogg e Ilya Safro. "Simmetrie classiche e algoritmo di ottimizzazione quantistica approssimata". Elaborazione delle informazioni quantistiche 20, 1–28 (2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

, Jonathan Wurtz e Peter Love. "Garanzie di prestazioni dell'algoritmo di ottimizzazione approssimata quantistica Maxcut per p> 1". Revisione fisica A 103, 042612 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042612

, Edward Farhi, Jeffrey Goldstone e Sam Gutmann. “Algoritmi quantistici per architetture a qubit fissi” (2017).

, Sergey Bravyi, Alexander Kliesch, Robert Koenig e Eugene Tang. "Ostacoli all'ottimizzazione quantistica variazionale derivanti dalla protezione della simmetria". Lettere di revisione fisica 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

, Edward Farhi, David Gamarnik e Sam Gutmann. "L'algoritmo di ottimizzazione quantistica approssimata deve vedere l'intero grafico: un caso tipico" (2020).

, Sergey Bravyi, Alexander Kliesch, Robert Koenig e Eugene Tang. "Algoritmi ibridi quanto-classici per la colorazione approssimativa dei grafi". Quantico 6, 678 (2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

, Matteo B Hastings. “Algoritmi di approssimazione della profondità limitata classica e quantistica” (2019).

, Kunal Marwaha. "L'algoritmo classico locale di taglio massimo supera $ p = 2 $ QAOA su grafici regolari ad alta circonferenza". Quantico 5, 437 (2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

, Boaz Barak e Kunal Marwaha. “Algoritmi classici e limitazioni quantistiche per il taglio massimo su grafici ad alta circonferenza” (2021).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14

, Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler e Swati Gupta. "Colmare classico e quantistico con gli avviamenti a caldo inizializzati SDP per QAOA". Transazioni ACM sull'informatica quantistica (2022).
https: / / doi.org/ 10.1145 / 3549554 mila

, Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli e Rupak Biswas. “Dall’algoritmo di ottimizzazione quantistica approssimata all’operatore quantistico alternato ansatz”. Algoritmi 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

, Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy e Eleanor G. Rieffel. "Mixer $xy$: risultati analitici e numerici per l'operatore alternato quantistico ansatz". Fis. Rev. A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

, Linghua Zhu, Ho Lun Tang, George S. Barron, FA Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes e Sophia E. Economou. "Algoritmo di ottimizzazione approssimata quantistica adattiva per la risoluzione di problemi combinatori su un computer quantistico". Fis. Rev. Ricerca 4, 033029 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033029

, Andreas Bärtschi e Stephan Eidenbenz. "Miscelatori Grover per QAOA: spostamento della complessità dalla progettazione del miscelatore alla preparazione dello stato". Nel 2020 Conferenza internazionale IEEE sull'informatica e l'ingegneria quantistica (QCE). Pagine 72–82. IEEE (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00020

, Zhang Jiang, Eleanor G. Rieffel e Zhihui Wang. "Circuito quantistico quasi ottimale per la ricerca non strutturata di Grover utilizzando un campo trasversale". Revisione fisica A 95, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.062317

, Lov K Grover. "Un algoritmo quantomeccanico veloce per la ricerca nel database". In Atti del ventottesimo simposio annuale ACM sulla teoria dell'informatica. Pagine 212–219. (1996).
https: / / doi.org/ 10.1145 / 237814.237866 mila

, Yin Zhang, Samuel Burer e Renato DC Monteiro. "Euristiche di rilassamento di grado 2 per max-cut e altri programmi quadratici binari". SIAM Journal on Optimization 12, 503––521 (2001).
https: / / doi.org/ 10.1137 / S1052623400382467

, Song Mei, Theodor Misiakiewicz, Andrea Montanari e Roberto Imbuzeiro Oliveira. "Risoluzione dei problemi di sincronizzazione e maxcut tramite la disuguaglianza di Grothendieck". In Conferenza sulla teoria dell'apprendimento. Pagine 1476–1515. PMLR (2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

, Ojas Parekh e Kevin Thompson. "Un'approssimazione ottimale dello stato del prodotto per hamiltoniani quantistici a 2 locali con termini positivi" (2022). arXiv:2206.08342.
arXiv: 2206.08342

, Ruben Tate e Swati Gupta. “Ci-qube”. Repository GitHub (2021). URL: https://​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

, Howard Karloff. "Quanto è valido l'algoritmo Goemans-Williamson MAX-CUT?". SIAM Journal on Computing 29, 336–350 (1999).
https: / / doi.org/ 10.1137 / S0097539797321481

, 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. "Ottimizzazione quantistica approssimata di problemi di grafo non planare su un processore superconduttore planare". Fisica della natura 17, 332–336 (2021).
https: / / doi.org/ 10.1038 / s41567-020-01105-y

, Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay e Jay M. Gambetta. "Mitigazione degli errori di misurazione negli esperimenti multiqubit". Fis. Rev. A 103, 042605 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.042605

, George S. Barron e Christopher J. Wood. “Mitigazione degli errori di misura per algoritmi quantistici variazionali” (2020).

, 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 e Xiaoqiang Zheng. “TensorFlow: apprendimento automatico su larga scala su sistemi eterogenei” (2015).

, Diederik P. Kingma e Jimmy Ba. "Adam: un metodo per l'ottimizzazione stocastica" (2014).

, Roger Fletcher. “Metodi pratici di ottimizzazione (2a edizione)”. John Wiley e figli. New York, New York, Stati Uniti (1987).
https: / / doi.org/ 10.1002 / 9781118723203 mila

, MJD Powell. "Un metodo di ottimizzazione della ricerca diretta che modella le funzioni obiettivo e vincolo mediante interpolazione lineare". Progressi nell'ottimizzazione e nell'analisi numerica 275, 51–67 (1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

, Alan J.Laub. “Analisi di matrice per scienziati e ingegneri”. Volume 91. Siam. (2005).
https: / / doi.org/ 10.1137 / 1.9780898717907 mila

, Georg Frobenius. “Ueber matrizen aus nicht negativen elementen”. Sitzungsberichte der Königlich Preussischen Akademie der WissenschaftenPagine 456–477 (1912).

, A. Kaveh e H. Rahami. "Un metodo unificato per la composizione automatica dei prodotti grafici". Comunicazioni in metodi numerici in ingegneria con applicazioni biomediche 21, 377–388 (2005).
https://​/​doi.org/​10.1002/​cnm.753

, Simon Spacapan. “Connettività di prodotti cartesiani di grafi”. Lettere di matematica applicata 21, 682–685 (2008).
https: / / doi.org/ 10.1016 / j.aml.2007.06.010

, Jacek Gondzio e Andreas Grothey. "Risoluzione di problemi di pianificazione finanziaria non lineare con 109 variabili decisionali su architetture massivamente parallele". Transazioni WIT su modellazione e simulazione 43 (2006).
https://​/​doi.org/​10.2495/​CF060101

, Il fan RK Chung. “Teoria dei grafi spettrali”. Volume 92. Società matematica americana. (1997).
https://​/​doi.org/​10.1090/​cbms/​092

, MA Nielsen e IL Chuang. “Calcolo quantistico e informazione quantistica: edizione del decimo anniversario”. Cambridge University Press, New York. (10).
https: / / doi.org/ 10.1017 / CBO9780511976667

, Vincent R. Pascuzzi, Andre He, Christian W. Bauer, Wibe A. de Jong e Benjamin Nachman. "Estrapolazione a rumore zero computazionalmente efficiente per la mitigazione degli errori del gate quantistico". Revisione fisica A 105, 042406 (2022).
https: / / doi.org/ 10.1103 / PhysRevA.105.042406

, Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala e Kristan Temme. "Cancellazione probabilistica degli errori con modelli sparsi di Pauli-Lindblad su processori quantistici rumorosi". Nature PhysicsPagine 1–6 (2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

, Nathan Krislock, Jérôme Malick e Frédéric Roupin. "BiqCrunch: un metodo branch-and-bound semidefinito per risolvere problemi quadratici binari". Transazioni ACM sul software matematico 43 (2017).
https: / / doi.org/ 10.1145 / 3005345 mila

, Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer e Matt McGinnis. "Gli autovalori più piccoli dei grafici di Hamming, dei grafici di Johnson e di altri grafici a distanza regolare con parametri classici". Journal of Combinatorial Theory, serie B 133, 88–121 (2018).
https: / / doi.org/ 10.1016 / j.jctb.2018.04.005

, Donald Knut. “Matrici combinatorie”. Articoli selezionati sulla matematica discreta (2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

Citato da

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner e Daniel J. Egger, "Ridimensionamento dell'algoritmo di ottimizzazione approssimata quantistica su hardware basato su qubit superconduttori", Quantico 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun e Marco Pistoia, "L'allineamento tra stato iniziale e mixer migliora le prestazioni QAOA per l'ottimizzazione del portafoglio vincolato", arXiv: 2305.03857, (2023).

[3] V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad e Ping Koy Lam, "Un Ansatz espressivo per l'ottimizzazione quantistica a bassa profondità", arXiv: 2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo e Anh Pham, "Complemento dell'algoritmo di ricerca di Grover: un'implementazione della soppressione dell'ampiezza", arXiv: 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele e Procolo Lucignano, “Convergenza del QAOA digitalizzato-controdiabatico: profondità del circuito rispetto a parametri liberi”, arXiv: 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble e Creston D. Herold, "Modellazione del rumore nelle interazioni globali di Mølmer-Sørensen applicate all'ottimizzazione quantistica approssimativa", Revisione fisica A 107 6, 062406 (2023).

[7] Guoming Wang, "Algoritmo di ottimizzazione quantistica potenziato in modo classico", arXiv: 2203.13936, (2022).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2023-09-27 01:31:19). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2023-09-27 01:31:17).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

Timestamp:

Di più da Diario quantistico