Considerazioni sulla latenza per gli ottimizzatori stocastici negli algoritmi quantistici variazionali

Considerazioni sulla latenza per gli ottimizzatori stocastici negli algoritmi quantistici variazionali

Nodo di origine: 2015562

Matt Menikelly1, Yunsoo Ha2e Matthew Otten3

1Divisione di matematica e informatica, Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts Dipartimento di ingegneria industriale e dei sistemi, North Carolina State University, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

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

Astratto

Gli algoritmi quantistici variazionali, che sono diventati importanti nel rumoroso contesto quantistico su scala intermedia, richiedono l'implementazione di un ottimizzatore stocastico sull'hardware classico. Ad oggi, la maggior parte della ricerca ha utilizzato algoritmi basati sull'iterazione del gradiente stocastico come ottimizzatore stocastico classico. In questo lavoro proponiamo invece di utilizzare algoritmi di ottimizzazione stocastica che producono processi stocastici che emulano la dinamica degli algoritmi deterministici classici. Questo approccio si traduce in metodi con complessità di iterazione nel caso peggiore teoricamente superiori, a scapito di maggiori complessità di campione (shot) per-iterazione. Investighiamo questo compromesso sia teoricamente che empiricamente e concludiamo che le preferenze per la scelta dell'ottimizzatore stocastico dovrebbero dipendere esplicitamente da una funzione sia della latenza che dei tempi di esecuzione dello scatto.

Gli algoritmi quantistici variazionali sono candidati promettenti per risolvere problemi pratici sui computer quantistici a breve termine. Tuttavia, il processo di ottimizzazione di questi algoritmi può essere computazionalmente costoso a causa delle due necessità di 1) eseguire misurazioni ripetute (scatti) sul computer quantistico e 2) regolare i parametri del circuito quantistico. Qui, proponiamo un nuovo algoritmo di ottimizzazione stocastica chiamato SHOALS (SHOt Adaptive Line Search) progettato partendo dal presupposto che il tempo impiegato nell'ottimizzazione per eseguire i tiri è dominato dal tempo impiegato nell'ottimizzazione per eseguire le regolazioni del circuito. Dimostriamo che SHOALS supera gli altri algoritmi di ottimizzazione stocastica in questo contesto. Al contrario, quando il tempo di sparo è paragonabile al tempo di commutazione del circuito, gli algoritmi di discesa del gradiente stocastico risultano più efficienti. Considerando i compromessi tra tempo di ripresa, tempo di commutazione del circuito e efficienza dell'algoritmo di ottimizzazione, mostriamo che il tempo di esecuzione totale degli algoritmi quantistici variazionali può essere significativamente ridotto.

► dati BibTeX

► Riferimenti

, Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri, et al. “Verso la chimica quantistica su un computer quantistico”. Chimica della natura 2, 106–111 (2010).
https: / / doi.org/ 10.1038 / nchem.483

, Ian C Cloët, Matthew R Dietrich, John Arrington, Alexei Bazavov, Michael Bishof, Adam Freese, Alexey V Gorshkov, Anna Grassellino, Kawtar Hafidi, Zubin Jacob, et al. “Opportunità per la fisica nucleare e la scienza dell’informazione quantistica” (2019). arXiv:1903.05453.
arXiv: 1903.05453

, Adam Smith, MS Kim, Frank Pollmann e Johannes Knolle. "Simulazione della dinamica quantistica a molti corpi su un attuale computer quantistico digitale". npj Informazioni quantistiche 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

, Benjamin Nachman, Davide Provasoli, Wibe A de Jong e Christian W Bauer. “Algoritmo quantistico per simulazioni di fisica delle alte energie”. Lettere di revisione fisica 126, 062001 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.062001

, Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe e Seth Lloyd. "Apprendimento automatico quantistico". Natura 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

, Roman Orus, Samuel Mugel e Enrique Lizaso. “Informatica quantistica per la finanza: panoramica e prospettive”. Recensioni in Fisica 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

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

, U Dorner, R Demkowicz-Dobrzanski, BJ Smith, JS Lundeen, W Wasilewski, K Banaszek e IA Walmsley. “Stima ottimale della fase quantistica”. Lettere di revisione fisica 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

, Giovanni Preskill. “Calcolo quantistico tollerante agli errori”. In Introduzione al calcolo quantistico e all'informazione. Pagine 213–269. Mondo scientifico (1998).

, Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. “Algoritmi quantistici variazionali”. Nature Reviews PhysicsPagine 1–20 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

, Peter JJ O'Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, et al. "Simulazione quantistica scalabile di energie molecolari". Revisione fisica X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

, Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li e Simon C Benjamin. "Teoria della simulazione quantistica variazionale". Quantum 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

, Matthew Otten, Cristian L Cortes e Stephen K Gray. "Dinamica quantistica resiliente al rumore utilizzando ansatze che preservano la simmetria" (2019). arXiv:1910.06284.
arXiv: 1910.06284

, Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow e Jay M Gambetta. "Autosolver quantistico variazionale efficiente in termini di hardware per piccole molecole e magneti quantistici". Natura 549, 242–246 (2017).
https: / / doi.org/ 10.1038 / nature23879

, Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa e Keisuke Fujii. "Apprendimento del circuito quantistico". Revisione fisica A 98, 032309 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.032309

, Matthew Otten, Imène R Goumiri, Benjamin W Priest, George F Chapline e Michael D Schneider. "Apprendimento automatico quantistico che utilizza processi gaussiani con kernel quantistici performanti" (2020). arXiv:2004.11280.
arXiv: 2004.11280

, Robert M Parrish, Edward G Hohenstein, Peter L McMahon e Todd J Martínez. "Calcolo quantistico delle transizioni elettroniche utilizzando un autorisolvitore quantistico variazionale". Lettere di revisione fisica 122, 230401 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.230401

, Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush e Jarrod R McClean. "Utilizzo di modelli per migliorare gli ottimizzatori per algoritmi quantistici variazionali". Scienza e tecnologia quantistica 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

, Jay Gambetta, WA Braff, A Wallraff, SM Girvin e RJ Schoelkopf. "Protocolli per la lettura ottimale dei qubit utilizzando una misurazione continua di non demolizione quantistica". Revisione fisica A 76, 012325 (2007).
https: / / doi.org/ 10.1103 / PhysRevA.76.012325

, Susan M Clark, Daniel Lobser, Melissa C Revelle, Christopher G Yale, David Bossert, Ashlyn D Burch, Matthew N Chow, Craig W Hogle, Megan Ivory, Jessica Pehr, et al. "Ingegnerizzazione del banco di prova aperto per gli utenti del calcolo scientifico quantistico". Transazioni IEEE sull'ingegneria quantistica 2, 1–32 (2021).
https: / / doi.org/ 10.1109 / TQE.2021.3096480

, Colin D Bruzewicz, John Chiaverini, Robert McConnell e Jeremy M Sage. "Calcolo quantistico a ioni intrappolati: progressi e sfide". Recensioni di fisica applicata 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164 mila

, Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio e Patrick J Coles. "Un ottimizzatore adattivo per algoritmi variazionali frugali in termini di misurazione". Quantico 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

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

, Trygve Helgaker, Poul Jorgensen e Jeppe Olsen. "Teoria della struttura elettronica molecolare". John Wiley & Figli. (2014).
https: / / doi.org/ 10.1002 / 9781119019572 mila

, Tom Schaul, Ioannis Antonoglou e David Silver. "Test unitari per l'ottimizzazione stocastica". In Yoshua Bengio e Yann LeCun, redattori, 2a conferenza internazionale sulle rappresentazioni dell'apprendimento, ICLR 2014, Banff, AB, Canada, 14-16 aprile 2014, Conference Track Proceedings. (2014). url: http://​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

, Hilal Asi e John C. Duchi. "L'importanza di modelli migliori nell'ottimizzazione stocastica". Atti dell'Accademia nazionale delle scienze 116, 22924–22930 (2019).
https: / / doi.org/ 10.1073 / pnas.1908018116

, Billy Jin, Katya Scheinberg e Miaolan Xie. "Limiti di complessità ad alta probabilità per la ricerca lineare basata su oracoli stocastici" (2021). arXiv:2106.06454.
arXiv: 2106.06454

, Jose Blanchet, Coralia Cartis, Matt Menickelly e Katya Scheinberg. "Analisi del tasso di convergenza di un metodo stocastico della regione di fiducia tramite supermartingale". INFORMA Journal on Optimization 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

, Courtney Paquette e Katya Scheinberg. "Un metodo di ricerca di linee stocastiche con analisi della complessità attesa". Giornale SIAM sull'ottimizzazione 30, 349–376 (2020).
https: / / doi.org/ 10.1137 / 18M1216250

, Albert S Berahas, Liyuan Cao e Katya Scheinberg. "Analisi del tasso di convergenza globale di un generico algoritmo di ricerca di linee con rumore". SIAM Journal on Optimization 31, 1489–1518 (2021).
https: / / doi.org/ 10.1137 / 19M1291832

, Coralia Cartis, Nicholas IM Gould e Ph L Toint. "Sulla complessità della discesa più ripida, metodi di Newton e di Newton regolarizzato per problemi di ottimizzazione non vincolata non convessa". Rivista Siam sull'ottimizzazione 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100 mila

, Coralia Cartis, Nicholas IM Gould e Philippe L Toint. "Sulla complessità oracolare degli algoritmi del primo ordine e privi di derivate per la minimizzazione liscia non convessa". SIAM Journal sull'ottimizzazione 22, 66–86 (2012).
https: / / doi.org/ 10.1137 / 100812276 mila

, Yair Carmon, John C. Duchi, Oliver Hinder e Aaron Sidford. “Limiti inferiori per la ricerca di punti stazionari I”. Programmazione matematica 184, 71–120 (2020).
https: / / doi.org/ 10.1007 / s10107-019-01406-y

, Yair Carmon, John C. Duchi, Oliver Hinder e Aaron Sidford. ““convesso fino a prova contraria”: accelerazione senza dimensione della discesa del gradiente su funzioni non convesse”. Nella conferenza internazionale sull'apprendimento automatico. Pagine 654–663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449 mila

, Chi Jin, Praneeth Netrapalli e Michael I Jordan. “La discesa in gradiente accelerata sfugge ai punti di sella più velocemente della discesa in gradiente”. Nella conferenza sulla teoria dell'apprendimento. Pagine 1042–1085. PMLR (2018). url: https://​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

, Saeed Ghadimi e Guanghui Lan. "Metodi stocastici del primo e zero ordine per la programmazione stocastica non convessa". Giornale SIAM sull'ottimizzazione 23, 2341–2368 (2013).
https: / / doi.org/ 10.1137 / 120880811 mila

, Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro e Blake Woodworth. “Limiti inferiori per l’ottimizzazione stocastica non convessa” (2019). arXiv:1912.02365.
arXiv: 1912.02365

, Cong Fang, Chris Junchi Li, Zhouchen Lin e Tong Zhang. "Spider: ottimizzazione non convessa quasi ottimale tramite stimatore differenziale integrato nel percorso stocastico". In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi e R. Garnett, editori, Advances in Neural Information Processing Systems. Volume 31. Curran Associates, Inc. (2018). url: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf

, Shiro Tamiya e Hayata Yamasaki. "Ottimizzazione bayesiana della linea del gradiente stocastico: riduzione dei colpi di misurazione nell'ottimizzazione dei circuiti quantistici parametrizzati" (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

, Pascual Jordan e Eugene Paul Wigner. “über das paulische äquivalenzverbot”. Nella raccolta delle opere di Eugene Paul Wigner. Pagine 109–129. Springer (1993).

, Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac e Nathan Killoran. "Valutazione dei gradienti analitici su hardware quantistico". Revisione fisica A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

, Joonho Lee, William J. Huggins, Martin Head-Gordon e K. Birgitta Whaley. "Funzioni d'onda a grappolo accoppiate unitarie generalizzate per il calcolo quantistico". Journal of Chemical Theory and Computation 15, 311–324 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b01004

, Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik e Jeremy L O'brien. "Un risolutore di autovalori variazionali su un processore quantistico fotonico". Comunicazioni sulla natura 5, 1–7 (2014). URL: https://​/​doi.org/​10.1038/​ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213

, Ilya G Ryabinkin, Tzu-Ching Yen, Scott N Genin e Artur F Izmaylov. "Metodo del cluster accoppiato Qubit: un approccio sistematico alla chimica quantistica su un computer quantistico". Journal of Chemical Theory and Computation 14, 6317–6326 (2018).
https: / / doi.org/ 10.1021 / acs.jctc.8b00932

, Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes e Sophia E Economou. “qubit-ADAPT-VQE: un algoritmo adattivo per costruire ansätze efficiente in termini di hardware su un processore quantistico”. PRX Quantum 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

, Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray e Matthew Otten. “Metodo unitario selettivo dei cluster accoppiati”. Quantico 6, 703 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

, Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi e Frederic T Chong. "Costo di misurazione $ o (n ^ 3) $ per autosolutore quantistico variazionale su hamiltoniani molecolari". Transazioni IEEE sull'ingegneria quantistica 1, 1–24 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3035814

, Ruobing Chen, Matt Menickelly e Katya Scheinberg. "Ottimizzazione stocastica utilizzando il metodo della regione di fiducia e modelli casuali". Programmazione matematica 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

, Léon Bottou, Frank E. Curtis e Jorge Nocedal. "Metodi di ottimizzazione per l'apprendimento automatico su larga scala". Siam Revisione 60, 223–311 (2018).
https: / / doi.org/ 10.1137 / 16M1080173

, Yoel Drori e Ohad Shamir. “La complessità di trovare punti stazionari con gradiente discendente stocastico”. Nella conferenza internazionale sull'apprendimento automatico. Pagine 2658–2667. PMLR (2020). url: https://​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

, Cong Fang, Zhouchen Lin e Tong Zhang. "Analisi acuta per SGD non convessi in fuga dai punti di sella". Nella conferenza sulla teoria dell'apprendimento. Pagine 1192–1234. PMLR (2019). URL: https://​/​proceedings.mlr.press/​v99/​fang19a.html.
https://​/​proceedings.mlr.press/​v99/​fang19a.html

, S Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale e Sanjiv Kumar. "Metodi adattativi per l'ottimizzazione non convessa". Negli atti della 32a conferenza sui sistemi di elaborazione delle informazioni neurali (NIPS 2018). (2018). url: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

, Léon Bottou e Olivier Bousquet. “I compromessi dell’apprendimento su larga scala”. In J. Platt, D. Koller, Y. Singer e S. Roweis, editori, Advances in Neural Information Processing Systems. Volume 20. Curran Associates, Inc. (2007). url: https://​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf

, Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva e Robert S Smith. “Una piattaforma cloud quantistica-classica ottimizzata per algoritmi ibridi variazionali”. Scienza e tecnologia quantistica 5, 024003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7559

, HJ Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac e Peter Zoller. “Computazione quantistica con atomi neutri”. Giornale di ottica moderna 47, 415–451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052 mila

, Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo e Kristan Temme. "Rastremazione dei qubit per simulare hamiltoniani fermionici" (2017). arXiv:1701.08213.
arXiv: 1701.08213

, MD SAJID ANIS, Héctor Abraham, AduOffei, Rochisha Agarwal, Gabriele Agliardi, Merav Aharoni, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Sashwat Anagolum, Eli Arbel, Abraham Asfaw, Anish Athalye, Artur Avkhadiev, et al. "Qiskit: un framework open source per l'informatica quantistica" (2021).

, Ciyou Zhu, Richard H Byrd, Peihuang Lu e Jorge Nocedal. "Algoritmo 778: L-BFGS-B: subroutine Fortran per l'ottimizzazione vincolata su larga scala". ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236 mila

, Raghu Bollapragada, Richard Byrd e Jorge Nocedal. "Strategie di campionamento adattativo per l'ottimizzazione stocastica". SIAM Journal sull'ottimizzazione 28, 3312–3343 (2018).
https: / / doi.org/ 10.1137 / 17M1154679

, Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi e Ping Tak Peter Tang. "Un metodo L-BFGS di batching progressivo per l'apprendimento automatico". Nella conferenza internazionale sull'apprendimento automatico. Pagine 620–629. PMLR (2018). url: https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html.
https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html

, Raghu Pasupathy, Peter Glynn, Soumyadip Ghosh e Fatemeh S Hashemi. "Sulle frequenze di campionamento nelle ricorsioni basate sulla simulazione". SIAM Journal sull'ottimizzazione 28, 45–73 (2018).
https: / / doi.org/ 10.1137 / 140951679 mila

, Andrew Arrasmith, Lukasz Cincio, Rolando D Somma, and Patrick J Coles. "Campionamento dell'operatore per l'ottimizzazione shot-frugale negli algoritmi variazionali" (2020). arXiv:2004.06252.
arXiv: 2004.06252

, Yangyang Xu e Wotao Yin. "Blocca l'iterazione del gradiente stocastico per l'ottimizzazione convessa e non convessa". SIAM Journal sull'ottimizzazione 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938 mila

Citato da

[1] Matt Menickelly, Stefan M. Wild e Miaolan Xie, "Un metodo stocastico quasi-Newton in assenza di numeri casuali comuni", arXiv: 2302.09128, (2023).

[2] Kosuke Ito, "Allocazione adattiva dei colpi in grado di riconoscere la latenza per algoritmi quantistici variazionali efficienti in termini di tempo di esecuzione", arXiv: 2302.04422, (2023).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2023-03-16 18:30:45). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

Impossibile recuperare Crossref citato da dati durante l'ultimo tentativo 2023-03-16 18:30:43: Impossibile recuperare i dati citati per 10.22331 / q-2023-03-16-949 da Crossref. Questo è normale se il DOI è stato registrato di recente.

Timestamp:

Di più da Diario quantistico