Latency overvejelser for stokastiske optimizere i variationskvantealgoritmer

Latency overvejelser for stokastiske optimizere i variationskvantealgoritmer

Kildeknude: 2015562

Matt Menickelly1, Yunsoo Ha2, og Matthew Otten3

1Mathematics and Computer Science Division, Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265, USA

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Variationelle kvantealgoritmer, som er blevet fremtrædende i den støjende mellemskala kvanteindstilling, kræver implementering af en stokastisk optimering på klassisk hardware. Til dato har det meste af forskningen anvendt algoritmer baseret på den stokastiske gradientiteration som den stokastiske klassiske optimering. I dette arbejde foreslår vi i stedet at bruge stokastiske optimeringsalgoritmer, der giver stokastiske processer, der emulerer dynamikken i klassiske deterministiske algoritmer. Denne tilgang resulterer i metoder med teoretisk overlegne worst-case iterationskompleksiteter på bekostning af større per-iteration sample (shot) kompleksiteter. Vi undersøger denne afvejning både teoretisk og empirisk og konkluderer, at præferencer for et valg af stokastisk optimizer eksplicit bør afhænge af en funktion af både latens og skududførelsestider.

Variationelle kvantealgoritmer er lovende kandidater til at løse praktiske problemer på kortsigtede kvantecomputere. Processen med at optimere disse algoritmer kan dog være beregningsmæssigt dyr på grund af de to behov for at 1) udføre gentagne målinger (skud) på kvantecomputeren og 2) justere kvantekredsløbsparametrene. Her foreslår vi en ny stokastisk optimeringsalgoritme kaldet SHOALS (SHOt Adaptive Line Search), der er designet under den antagelse, at den tid, der bruges på optimering af optagelser, er domineret af den tid, der bruges på optimering ved at udføre kredsløbsjusteringer. Vi demonstrerer, at SHOALS udkonkurrerer andre stokastiske optimeringsalgoritmer i denne indstilling. Tværtimod, når skudtiden er sammenlignelig med kredsløbsskiftetiden, viser sig stokastiske gradientnedstigningsalgoritmer at være mere effektive. Ved at overveje afvejningen mellem skudtid, kredsløbsskiftetid og effektiviteten af ​​optimeringsalgoritmen viser vi, at den samlede kørselstid for variationskvantealgoritmer kan reduceres betydeligt.

► BibTeX-data

► Referencer

[1] 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. "Mod kvantekemi på en kvantecomputer". Naturkemi 2, 106-111 (2010).
https:/​/​doi.org/​10.1038/​nchem.483

[2] 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. "Muligheder for kernefysik og kvanteinformationsvidenskab" (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann og Johannes Knolle. "Simulering af kvante mange-krops dynamik på en aktuel digital kvantecomputer". npj Quantum Information 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Benjamin Nachman, Davide Provasoli, Wibe A de Jong og Christian W Bauer. "Kvantealgoritme til højenergifysiksimuleringer". Physical Review Letters 126, 062001 (2021).
https://​/​doi.org/​10.1103/​PhysRevLett.126.062001

[5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe og Seth Lloyd. "Kvantemaskinelæring". Nature 549, 195-202 (2017).
https://​/​doi.org/​10.1038/​nature23474

[6] Roman Orus, Samuel Mugel og Enrique Lizaso. "Quantum computing til finansiering: Overblik og udsigter". Anmeldelser i Fysik 4, 100028 (2019).
https://​/​doi.org/​10.1016/​j.revip.2019.100028

[7] John Preskill. "Quantum computing i NISQ-æraen og derefter". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[8] U Dorner, R Demkowicz-Dobrzanski, BJ Smith, JS Lundeen, W Wasilewski, K Banaszek og IA Walmsley. "Optimal kvantefase-estimering". Physical Review Letters 102, 040403 (2009).
https://​/​doi.org/​10.1103/​PhysRevLett.102.040403

[9] John Preskill. "Fejltolerant kvanteberegning". I Introduktion til kvanteberegning og information. Side 213–269. World Scientific (1998).

[10] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. "Variationelle kvantealgoritmer". Nature Reviews PhysicsPages 1–20 (2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[11] 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. "Skalerbar kvantesimulering af molekylære energier". Fysisk gennemgang X 6, 031007 (2016).
https://​/​doi.org/​10.1103/​PhysRevX.6.031007

[12] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li og Simon C Benjamin. "Teori om variationel kvantesimulering". Quantum 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Matthew Otten, Cristian L Cortes og Stephen K Gray. "Støjresistent kvantedynamik ved hjælp af symmetribevarende ansatzes" (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow og Jay M Gambetta. "Hardwareeffektiv variationskvanteegenopløser til små molekyler og kvantemagneter". Nature 549, 242-246 (2017).
https://​/​doi.org/​10.1038/​nature23879

[15] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa og Keisuke Fujii. "Kvantekredsløbslæring". Fysisk anmeldelse A 98, 032309 (2018).
https://​/​doi.org/​10.1103/​PhysRevA.98.032309

[16] Matthew Otten, Imène R Goumiri, Benjamin W Priest, George F Chapline og Michael D Schneider. "Kvantemaskinelæring ved hjælp af gaussiske processer med effektive kvantekerner" (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon og Todd J Martínez. "Kvanteberegning af elektroniske overgange ved hjælp af en variationel kvanteegenopløser". Physical Review Letters 122, 230401 (2019).
https://​/​doi.org/​10.1103/​PhysRevLett.122.230401

[18] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush og Jarrod R McClean. "Brug af modeller til at forbedre optimeringsværktøjer til variationskvantealgoritmer". Quantum Science and Technology 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin og RJ Schoelkopf. "Protokoller til optimal udlæsning af qubits ved hjælp af en kontinuerlig kvante ikke-nedrivningsmåling". Physical Review A 76, 012325 (2007).
https://​/​doi.org/​10.1103/​PhysRevA.76.012325

[20] 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. "Enginering af den kvantevidenskabelige databehandling åben bruger testbed". IEEE Transactions on Quantum Engineering 2, 1–32 (2021).
https://​/​doi.org/​10.1109/​TQE.2021.3096480

[21] Colin D Bruzewicz, John Chiaverini, Robert McConnell og Jeremy M Sage. "Fanget-ion kvantecomputere: Fremskridt og udfordringer". Applied Physics Reviews 6, 021314 (2019).
https://​/​doi.org/​10.1063/​1.5088164

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio og Patrick J Coles. "En adaptiv optimering til målesparsomme variationsalgoritmer". Quantum 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Diederik P Kingma og Jimmy Ba. "Adam: En metode til stokastisk optimering" (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Trygve Helgaker, Poul Jørgensen og Jeppe Olsen. "Molekylær elektronisk strukturteori". John Wiley & sønner. (2014).
https://​/​doi.org/​10.1002/​9781119019572

[25] Tom Schaul, Ioannis Antonoglou og David Silver. "Enhedstest til stokastisk optimering". I Yoshua Bengio og Yann LeCun, redaktører, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, 14.-16. april 2014, Conference Track Proceedings. (2014). url: http://​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Hilal Asi og John C Duchi. "Betydningen af ​​bedre modeller i stokastisk optimering". Proceedings of the National Academy of Sciences 116, 22924–22930 (2019).
https://​/​doi.org/​10.1073/​pnas.1908018116

[27] Billy Jin, Katya Scheinberg og Miaolan Xie. "Høj sandsynlighedskompleksitet sætter grænser for linjesøgning baseret på stokastiske orakler" (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly og Katya Scheinberg. "Konvergenshastighedsanalyse af en stokastisk tillidsregionsmetode via supermartingales". INFORMERER Journal on Optimization 1, 92–119 (2019).
https:/​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Courtney Paquette og Katya Scheinberg. "En stokastisk linjesøgningsmetode med forventet kompleksitetsanalyse". SIAM Journal on Optimization 30, 349–376 (2020).
https://​/​doi.org/​10.1137/​18M1216250

[30] Albert S Berahas, Liyuan Cao og Katya Scheinberg. "Global konvergenshastighedsanalyse af en generisk linjesøgningsalgoritme med støj". SIAM Journal on Optimization 31, 1489–1518 (2021).
https://​/​doi.org/​10.1137/​19M1291832

[31] Coralia Cartis, Nicholas IM Gould og Ph L Toint. "Om kompleksiteten af ​​stejleste nedstigning, Newtons og regulariserede Newtons metoder til ikke-konvekse ubegrænsede optimeringsproblemer". Siam journal om optimering 20, 2833–2852 (2010).
https://​/​doi.org/​10.1137/​090774100

[32] Coralia Cartis, Nicholas IM Gould og Philippe L Toint. "Om orakelkompleksiteten af ​​førsteordens og derivatfrie algoritmer til glat ikke-konveks minimering". SIAM Journal on Optimization 22, 66–86 (2012).
https://​/​doi.org/​10.1137/​100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder og Aaron Sidford. "Nedre grænser for at finde stationære punkter I". Matematisk programmering 184, 71-120 (2020).
https://​/​doi.org/​10.1007/​s10107-019-01406-y

[34] Yair Carmon, John C Duchi, Oliver Hinder og Aaron Sidford. ""konveks, indtil det modsatte er bevist": Dimensionsfri acceleration af gradientnedstigning på ikke-konvekse funktioner. I international konference om maskinlæring. Side 654–663. PMLR (2017).
https://​/​doi.org/​10.5555/​3305381.3305449

[35] Chi Jin, Praneeth Netrapalli og Michael I Jordan. "Accelereret gradientnedstigning undslipper saddelpunkter hurtigere end gradientnedstigning". I konference om læringsteori. Side 1042–1085. PMLR (2018). url: https://​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Saeed Ghadimi og Guanghui Lan. "Stokastiske første- og nulteordens metoder til ikke-konveks stokastisk programmering". SIAM Journal on Optimization 23, 2341–2368 (2013).
https://​/​doi.org/​10.1137/​120880811

[37] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro og Blake Woodworth. "Nedre grænser for ikke-konveks stokastisk optimering" (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin og Tong Zhang. "Spider: Næsten optimal ikke-konveks optimering via stokastisk sti-integreret differentialestimator". I S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi og R. Garnett, redaktører, Advances in Neural Information Processing Systems. Bind 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

[39] Shiro Tamiya og Hayata Yamasaki. "Stokastisk gradientlinje bayesiansk optimering: Reduktion af måleskud ved optimering af parametriserede kvantekredsløb" (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Pascual Jordan og Eugene Paul Wigner. "über das paulische äquivalenzverbot". I The Collected Works of Eugene Paul Wigner. Side 109-129. Springer (1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac og Nathan Killoran. "Evaluering af analytiske gradienter på kvantehardware". Fysisk anmeldelse A 99, 032331 (2019).
https://​/​doi.org/​10.1103/​PhysRevA.99.032331

[42] Joonho Lee, William J Huggins, Martin Head-Gordon og K Birgitta Whaley. "Generaliserede enhedskoblede klyngebølgefunktioner til kvanteberegning". Journal of Chemical Theory and Computation 15, 311–324 (2018).
https://​/​doi.org/​10.1021/​acs.jctc.8b01004

[43] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik og Jeremy L O'brien. "En variabel egenværdiopløser på en fotonisk kvanteprocessor". Nature Communications 5, 1–7 (2014). url: https://doi.org/​10.1038/​ncomms5213.
https://​/​doi.org/​10.1038/​ncomms5213

[44] Ilya G Ryabinkin, Tzu-Ching Yen, Scott N Genin og Artur F Izmaylov. "Qubit-koblet klyngemetode: en systematisk tilgang til kvantekemi på en kvantecomputer". Journal of Chemical Theory and Computation 14, 6317–6326 (2018).
https://​/​doi.org/​10.1021/​acs.jctc.8b00932

[45] Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes og Sophia E Economou. "qubit-ADAPT-VQE: En adaptiv algoritme til at konstruere hardwareeffektiv ansätze på en kvanteprocessor". PRX Quantum 2, 020310 (2021).
https://​/​doi.org/​10.1103/​PRXQuantum.2.020310

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray og Matthew Otten. "Unitary selektiv koblet-klyngemetode". Quantum 6, 703 (2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

[47] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi og Frederic T Chong. "$ o (n^3) $ måleomkostninger for variationskvanteegenopløser på molekylære Hamiltonianere". IEEE Transactions on Quantum Engineering 1, 1-24 (2020).
https://​/​doi.org/​10.1109/​TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly og Katya Scheinberg. "Stokastisk optimering ved hjælp af en tillidsregionsmetode og tilfældige modeller". Matematisk programmering 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis og Jorge Nocedal. "Optimeringsmetoder til maskinlæring i stor skala". Siam Review 60, 223-311 (2018).
https://​/​doi.org/​10.1137/​16M1080173

[50] Yoel Drori og Ohad Shamir. "Kompleksiteten ved at finde stationære punkter med stokastisk gradientnedstigning". I international konference om maskinlæring. Side 2658–2667. PMLR (2020). url: https://​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Cong Fang, Zhouchen Lin og Tong Zhang. "Skarp analyse for ikke-konveks SGD, der undslipper fra saddelpunkter". I konference om læringsteori. Side 1192–1234. PMLR (2019). url: https://​/​proceedings.mlr.press/​v99/​fang19a.html.
https://​/​proceedings.mlr.press/​v99/​fang19a.html

[52] S Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale og Sanjiv Kumar. "Adaptive metoder til ikke-konveks optimering". I Proceedings of 32nd Conference on Neurale Information Processing Systems (NIPS 2018). (2018). url: https://​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

[53] Léon Bottou og Olivier Bousquet. "Afvejningen af ​​læring i stor skala". I J. Platt, D. Koller, Y. Singer og S. Roweis, redaktører, Advances in Neural Information Processing Systems. Bind 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

[54] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva og Robert S Smith. "En kvanteklassisk skyplatform optimeret til variationshybridalgoritmer". Quantum Science and Technology 5, 024003 (2020).
https://​/​doi.org/​10.1088/​2058-9565/​ab7559

[55] HJ Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac og Peter Zoller. "Kvanteberegning med neutrale atomer". Journal of modern optics 47, 415–451 (2000).
https://​/​doi.org/​10.1080/​09500340008244052

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo og Kristan Temme. "Tapning af qubits for at simulere fermioniske Hamiltonians" (2017). arXiv:1701.08213.
arXiv: 1701.08213

[57] 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: En open source-ramme til kvanteberegning" (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu og Jorge Nocedal. "Algorithme 778: L-BFGS-B: Fortran subrutiner til storskala bundet begrænset optimering". ACM Transactions on Mathematical Software (TOMS) 23, 550-560 (1997).
https://​/​doi.org/​10.1145/​279232.279236

[59] Raghu Bollapragada, Richard Byrd og Jorge Nocedal. "Adaptive prøveudtagningsstrategier til stokastisk optimering". SIAM Journal on Optimization 28, 3312–3343 (2018).
https://​/​doi.org/​10.1137/​17M1154679

[60] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi og Ping Tak Peter Tang. "En progressiv batching L-BFGS metode til maskinlæring". I international konference om maskinlæring. Side 620–629. PMLR (2018). url: https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html.
https://​/​proceedings.mlr.press/​v80/​bollapragada18a.html

[61] Raghu Pasupathy, Peter Glynn, Soumyadip Ghosh og Fatemeh S Hashemi. "Om samplingsfrekvenser i simulationsbaserede rekursioner". SIAM Journal on Optimization 28, 45–73 (2018).
https://​/​doi.org/​10.1137/​140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma og Patrick J Coles. "Operator-sampling for skudsparende optimering i variationsalgoritmer" (2020). arXiv:2004.06252.
arXiv: 2004.06252

[63] Yangyang Xu og Wotao Yin. "Bloker stokastisk gradientiteration til konveks og ikke-konveks optimering". SIAM Journal on Optimization 25, 1686–1716 (2015).
https://​/​doi.org/​10.1137/​140983938

Citeret af

[1] Matt Menickelly, Stefan M. Wild og Miaolan Xie, "A Stokastic Quasi-Newton Method in the Absence of Common Random Numbers", arXiv: 2302.09128, (2023).

[2] Kosuke Ito, "Latency-aware adaptive shot allocation for runtime-effektive variationskvantealgoritmer", arXiv: 2302.04422, (2023).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-03-16 18:30:45). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

Kunne ikke hente Crossref citeret af data under sidste forsøg 2023-03-16 18:30:43: Kunne ikke hente citerede data for 10.22331/q-2023-03-16-949 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig.

Tidsstempel:

Mere fra Quantum Journal