Considérations de latence pour les optimiseurs stochastiques dans les algorithmes quantiques variationnels

Considérations de latence pour les optimiseurs stochastiques dans les algorithmes quantiques variationnels

Horodatage: 16 mars 2023 2h28
Nœud source: 2015562

Matt Menickelly1, Yunsoo Ha2et Matthew Otten3

1Division de mathématiques et d'informatique, Laboratoire national d'Argonne, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts Département d'ingénierie industrielle et des systèmes, Université d'État de Caroline du Nord, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Les algorithmes quantiques variationnels, qui ont pris de l'importance dans le domaine quantique bruyant à échelle intermédiaire, nécessitent la mise en œuvre d'un optimiseur stochastique sur du matériel classique. À ce jour, la plupart des recherches ont utilisé des algorithmes basés sur l’itération du gradient stochastique comme optimiseur stochastique classique. Dans ce travail, nous proposons plutôt d'utiliser des algorithmes d'optimisation stochastiques qui produisent des processus stochastiques émulant la dynamique des algorithmes déterministes classiques. Cette approche aboutit à des méthodes avec des complexités d'itération théoriquement supérieures dans le pire des cas, au détriment de plus grandes complexités d'échantillon (shot) par itération. Nous étudions ce compromis à la fois théoriquement et empiriquement et concluons que les préférences pour le choix d'un optimiseur stochastique devraient explicitement dépendre d'une fonction à la fois de la latence et des temps d'exécution des tirs.

Image présentée : Les latences et la précision des cibles affectent le choix des optimiseurs stochastiques pour les algorithmes quantiques variationnels.

Résumé populaire

Les algorithmes quantiques variationnels sont des candidats prometteurs pour résoudre des problèmes pratiques sur les ordinateurs quantiques à court terme. Cependant, le processus d'optimisation de ces algorithmes peut être coûteux en termes de calcul en raison des deux nécessités 1) d'effectuer des mesures répétées (prises de vue) sur l'ordinateur quantique et 2) d'ajuster les paramètres du circuit quantique. Nous proposons ici un nouvel algorithme d'optimisation stochastique appelé SHOALS (SHOt Adaptive Line Search) qui est conçu en supposant que le temps passé à optimiser les tirs est dominé par le temps passé à optimiser les ajustements du circuit. Nous démontrons que SHOALS surpasse les autres algorithmes d'optimisation stochastique dans ce contexte. Au contraire, lorsque le temps de tir est comparable au temps de commutation du circuit, les algorithmes de descente de gradient stochastique s'avèrent plus efficaces. En considérant les compromis entre le temps d'exécution, le temps de commutation du circuit et l'efficacité de l'algorithme d'optimisation, nous montrons que le temps d'exécution total des algorithmes quantiques variationnels peut être considérablement réduit.

► Données BibTeX

► Références

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. « Vers la chimie quantique sur un ordinateur quantique ». Chimie naturelle 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és pour la physique nucléaire et la science de l'information quantique » (2019). arXiv : 1903.05453.
arXiv: 1903.05453

Adam Smith, MS Kim, Frank Pollmann et Johannes Knolle. « Simuler la dynamique quantique à N corps sur un ordinateur quantique numérique actuel ». npj Informations quantiques 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

Benjamin Nachman, Davide Provasoli, Wibe A de Jong et Christian W Bauer. "Algorithme quantique pour les simulations de physique des hautes énergies". Lettres d'examen physique 126, 062001 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.126.062001

Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe et Seth Lloyd. "Apprentissage automatique quantique". Nature 549, 195-202 (2017).
https: / / doi.org/ 10.1038 / nature23474

Roman Orus, Samuel Mugel et Enrique Lizaso. « L'informatique quantique pour la finance : aperçu et perspectives ». Commentaires dans Physics 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

John Preskill. "L'informatique quantique à l'ère NISQ et au-delà". Quantique 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 et IA Walmsley. "Estimation optimale de la phase quantique". Lettres d'examen physique 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

John Preskill. « Calcul quantique tolérant aux pannes ». Dans Introduction au calcul et à l'information quantiques. Pages 213 à 269. Monde scientifique (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. "Algorithmes quantiques variationnels". Nature Reviews PhysicsPages 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. « Simulation quantique évolutive des énergies moléculaires ». Examen physique X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li et Simon C Benjamin. « Théorie de la simulation quantique variationnelle ». Quantique 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

Matthew Otten, Cristian L Cortes et Stephen K Gray. «Dynamique quantique résiliente au bruit utilisant des ansatzes préservant la symétrie» (2019). arXiv : 1910.06284.
arXiv: 1910.06284

Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow et Jay M Gambetta. "Solveur propre quantique variationnel à efficacité matérielle pour les petites molécules et les aimants quantiques". Nature 549, 242–246 (2017).
https: / / doi.org/ 10.1038 / nature23879

Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa et Keisuke Fujii. "Apprentissage des circuits quantiques". Examen physique A 98, 032309 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.032309

Matthew Otten, Imène R Goumiri, Benjamin W Priest, George F Chapline et Michael D Schneider. « Apprentissage automatique quantique utilisant des processus gaussiens avec des noyaux quantiques performants » (2020). arXiv : 2004.11280.
arXiv: 2004.11280

Robert M Parrish, Edward G Hohenstein, Peter L McMahon et Todd J Martínez. "Calcul quantique des transitions électroniques à l'aide d'un solveur propre quantique variationnel". Lettres d'examen physique 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 et Jarrod R McClean. "Utiliser des modèles pour améliorer les optimiseurs pour les algorithmes quantiques variationnels". Science et technologie quantiques 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

Jay Gambetta, WA Braff, A Wallraff, SM Girvin et RJ Schoelkopf. "Protocoles pour une lecture optimale des qubits à l'aide d'une mesure quantique continue de non-démolition". Examen physique 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. « Ingénierie du banc d'essai utilisateur ouvert de calcul scientifique quantique ». Transactions IEEE sur l'ingénierie quantique 2, 1-32 (2021).
https: / / doi.org/ 10.1109 / TQE.2021.3096480

Colin D Bruzewicz, John Chiaverini, Robert McConnell et Jeremy M Sage. « Informatique quantique à ions piégés : progrès et défis ». Revues de physique appliquée 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164

Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio et Patrick J Coles. "Un optimiseur adaptatif pour les algorithmes variationnels frugaux en mesures". Quantique 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

Diederik P Kingma et Jimmy Ba. « Adam : Une méthode d'optimisation stochastique » (2014). arXiv : 1412.6980.
arXiv: 1412.6980

Trygve Helgaker, Poul Jorgensen et Jeppe Olsen. "Théorie de la structure électronique moléculaire". John Wiley et fils. (2014).
https: / / doi.org/ 10.1002 / 9781119019572

Tom Schaul, Ioannis Antonoglou et David Silver. "Tests unitaires pour l'optimisation stochastique". Dans Yoshua Bengio et Yann LeCun, rédacteurs, 2e Conférence internationale sur les représentations d'apprentissage, ICLR 2014, Banff, AB, Canada, 14-16 avril 2014, Actes de la conférence. (2014). URL : http://​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

Hilal Asi et John C Duchi. "L'importance de meilleurs modèles dans l'optimisation stochastique". Actes de l'Académie nationale des sciences 116, 22924-22930 (2019).
https: / / doi.org/ 10.1073 / pnas.1908018116

Billy Jin, Katya Scheinberg et Miaolan Xie. « Limites de complexité à haute probabilité pour la recherche de lignes basée sur des oracles stochastiques » (2021). arXiv :2106.06454.
arXiv: 2106.06454

José Blanchet, Coralia Cartis, Matt Menickelly et Katya Scheinberg. "Analyse du taux de convergence d'une méthode stochastique de région de confiance via des supermartingales". INFORMS Journal sur l'optimisation 1, 92-119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

Courtney Paquette et Katya Scheinberg. "Une méthode de recherche de ligne stochastique avec analyse de complexité attendue". SIAM Journal sur l'optimisation 30, 349-376 (2020).
https: / / doi.org/ 10.1137 / 18M1216250

Albert S. Berahas, Liyuan Cao et Katya Scheinberg. "Analyse globale du taux de convergence d'un algorithme générique de recherche de lignes avec bruit". SIAM Journal sur l'optimisation 31, 1489-1518 (2021).
https: / / doi.org/ 10.1137 / 19M1291832

Coralia Cartis, Nicholas IM Gould et Ph L Toint. "Sur la complexité de la descente la plus raide, les méthodes de Newton et de Newton régularisé pour les problèmes d'optimisation non convexes et sans contraintes". Journal Siam sur l'optimisation 20, 2833-2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

Coralia Cartis, Nicholas IM Gould et Philippe L Toint. "Sur la complexité oracle des algorithmes de premier ordre et sans dérivées pour une minimisation non convexe en douceur". SIAM Journal sur l'optimisation 22, 66-86 (2012).
https: / / doi.org/ 10.1137 / 100812276

Yair Carmon, John C Duchi, Oliver Hinder et Aaron Sidford. « Limites inférieures pour trouver des points stationnaires I ». Programmation mathématique 184, 71-120 (2020).
https: / / doi.org/ 10.1007 / s10107-019-01406-y

Yair Carmon, John C Duchi, Oliver Hinder et Aaron Sidford. « « convexe jusqu'à preuve du contraire » : accélération sans dimension de la descente de gradient sur les fonctions non convexes ». Lors de la Conférence internationale sur l'apprentissage automatique. Pages 654-663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

Chi Jin, Praneeth Netrapalli et Michael I Jordan. « La descente de pente accélérée échappe aux points de selle plus rapidement que la descente de pente ». Dans Conférence sur la théorie de l'apprentissage. Pages 1042 à 1085. PMLR (2018). URL : https:/​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

Saeed Ghadimi et Guanghui Lan. "Méthodes stochastiques du premier et du zéro ordre pour la programmation stochastique non convexe". SIAM Journal sur l'optimisation 23, 2341-2368 (2013).
https: / / doi.org/ 10.1137 / 120880811

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro et Blake Woodworth. « Limites inférieures pour l'optimisation stochastique non convexe » (2019). arXiv : 1912.02365.
arXiv: 1912.02365

Cong Fang, Chris Junchi Li, Zhouchen Lin et Tong Zhang. "Spider : optimisation non convexe quasi optimale via un estimateur différentiel stochastique intégré au chemin". Dans S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi et R. Garnett, éditeurs, 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 et Hayata Yamasaki. « Optimisation bayésienne de la ligne de gradient stochastique : réduction des prises de mesure dans l'optimisation des circuits quantiques paramétrés » (2021). arXiv :2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

Pascual Jordan et Eugène Paul Wigner. « über das paulische äquivalenzverbot ». Dans Les œuvres rassemblées d'Eugène Paul Wigner. Pages 109 à 129. Springer (1993).

Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac et Nathan Killoran. "Évaluer les gradients analytiques sur le matériel quantique". Examen physique A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

Joonho Lee, William J Huggins, Martin Head-Gordon et K Birgitta Whaley. "Fonctions d'onde de cluster couplées unitaires généralisées pour le calcul quantique". Journal de théorie chimique et calcul 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 et Jeremy L O'brien. "Un solveur de valeurs propres variationnelles sur un processeur quantique photonique". Communications sur la nature 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 et Artur F Izmaylov. « Méthode des clusters couplés par qubits : une approche systématique de la chimie quantique sur un ordinateur quantique ». Journal de théorie chimique et calcul 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 et Sophia E Economou. "qubit-ADAPT-VQE : un algorithme adaptatif pour construire des réponses matériellement efficaces sur un processeur quantique". PRX Quantique 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray et Matthew Otten. «Méthode de cluster couplé sélectif unitaire». Quantique 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 et Frederic T Chong. "$ o (n ^ 3) $ coût de mesure pour le solveur propre quantique variationnel sur les hamiltoniens moléculaires". Transactions IEEE sur l'ingénierie quantique 1, 1-24 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3035814

Ruobing Chen, Matt Menickelly et Katya Scheinberg. "Optimisation stochastique utilisant une méthode de région de confiance et des modèles aléatoires". Programmation mathématique 169, 447-487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

Léon Bottou, Frank E Curtis et Jorge Nocedal. "Méthodes d'optimisation pour l'apprentissage automatique à grande échelle". Revue Siam 60, 223-311 (2018).
https: / / doi.org/ 10.1137 / 16M1080173

Yoel Drori et Ohad Shamir. "La complexité de trouver des points stationnaires avec descente de gradient stochastique". Lors de la Conférence internationale sur l'apprentissage automatique. Pages 2658 à 2667. PMLR (2020). URL : https:/​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

Cong Fang, Zhouchen Lin et Tong Zhang. "Analyse précise des SGD non convexes s'échappant des points de selle". Dans Conférence sur la théorie de l'apprentissage. Pages 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 et Sanjiv Kumar. "Méthodes adaptatives pour l'optimisation non convexe". Dans les actes de la 32e conférence sur les systèmes de traitement de l'information neuronale (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 et Olivier Bousquet. "Les compromis de l'apprentissage à grande échelle". Dans J. Platt, D. Koller, Y. Singer et S. Roweis, éditeurs, 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 et Robert S Smith. « Une plate-forme cloud quantique classique optimisée pour les algorithmes hybrides variationnels ». Science et technologie quantiques 5, 024003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7559

HJ Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac et Peter Zoller. « Informatique quantique avec atomes neutres ». Journal d'optique moderne 47, 415-451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052

Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo et Kristan Temme. « Tapering off qubits pour simuler des hamiltoniens fermioniques » (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 pour l'informatique quantique » (2021).

Ciyou Zhu, Richard H Byrd, Peihuang Lu et Jorge Nocedal. "Algorithme 778 : L-BFGS-B : sous-programmes Fortran pour une optimisation à grande échelle avec contraintes liées". Transactions ACM sur logiciels mathématiques (TOMS) 23, 550-560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236

Raghu Bollapragada, Richard Byrd et Jorge Nocedal. "Stratégies d'échantillonnage adaptatives pour l'optimisation stochastique". SIAM Journal sur l'optimisation 28, 3312-3343 (2018).
https: / / doi.org/ 10.1137 / 17M1154679

Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi et Ping Tak Peter Tang. "Une méthode L-BFGS par lots progressifs pour l'apprentissage automatique". Lors de la Conférence internationale sur l'apprentissage automatique. Pages 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 et Fatemeh S Hashemi. "Sur les taux d'échantillonnage dans les récursions basées sur la simulation". SIAM Journal sur l'optimisation 28, 45-73 (2018).
https: / / doi.org/ 10.1137 / 140951679

Andrew Arrasmith, Lukasz Cincio, Rolando D Somma et Patrick J Coles. « Échantillonnage d'opérateurs pour une optimisation frugale dans les algorithmes variationnels » (2020). arXiv : 2004.06252.
arXiv: 2004.06252

Yangyang Xu et Wotao Yin. "Bloquer l'itération du gradient stochastique pour l'optimisation convexe et non convexe". SIAM Journal sur l'optimisation 25, 1686-1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Cité par

[1] Matt Menickelly, Stefan M. Wild et Miaolan Xie, « Une méthode stochastique quasi-Newton en l'absence de nombres aléatoires communs », arXiv: 2302.09128, (2023).

[2] Kosuke Ito, « Allocation de tir adaptative tenant compte de la latence pour des algorithmes quantiques variationnels efficaces au moment de l'exécution », arXiv: 2302.04422, (2023).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2023-03-16 18:30:45). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

Impossible de récupérer Données de référence croisée lors de la dernière tentative 2023-03-16 18:30:43: Impossible de récupérer les données citées par 10.22331 / q-2023-03-16-949 de Crossref. C'est normal si le DOI a été enregistré récemment.

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique