Latency-betraktninger for stokastiske optimerere i variasjonskvantealgoritmer

Latency-betraktninger for stokastiske optimerere i variasjonskvantealgoritmer

Tidsstempel: 16. mars 2023 2:28
Kilde node: 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

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Varierende kvantealgoritmer, som har blitt fremtredende i den støyende kvanteinnstillingen i mellomskala, krever implementering av en stokastisk optimizer på klassisk maskinvare. Til dags dato har mesteparten av forskningen brukt algoritmer basert på den stokastiske gradient-iterasjonen som den stokastiske klassiske optimalisereren. I dette arbeidet foreslår vi i stedet å bruke stokastiske optimaliseringsalgoritmer som gir stokastiske prosesser som emulerer dynamikken til klassiske deterministiske algoritmer. Denne tilnærmingen resulterer i metoder med teoretisk overlegne worst-case iterasjonskompleksiteter, på bekostning av større per-iterasjons sample (shot) kompleksitet. Vi undersøker denne avveiningen både teoretisk og empirisk og konkluderer med at preferanser for et valg av stokastisk optimizer eksplisitt bør avhenge av en funksjon av både latens og utførelsestider for skudd.

Utvalgt bilde: Latenser og målpresisjon påvirker valget av stokastiske optimerere for variasjonskvantealgoritmer.

Populært sammendrag

Varierende kvantealgoritmer er lovende kandidater for å løse praktiske problemer på kortsiktige kvantedatamaskiner. Imidlertid kan prosessen med å optimalisere disse algoritmene være beregningsmessig kostbar på grunn av de to behovene for å 1) utføre gjentatte målinger (skudd) på kvantecomputeren og 2) justere kvantekretsparametrene. Her foreslår vi en ny stokastisk optimaliseringsalgoritme kalt SHOALS (SHOt Adaptive Line Search) som er designet under forutsetningen om at tiden brukt på optimalisering av skudd domineres av tiden brukt på optimalisering for å utføre kretsjusteringer. Vi demonstrerer at SHOALS utkonkurrerer andre stokastiske optimaliseringsalgoritmer i denne innstillingen. Tvert imot, når skuddtiden er sammenlignbar med kretsbyttetiden, er stokastiske gradientnedstigningsalgoritmer funnet å være mer effektive. Ved å vurdere avveiningene mellom skuddtid, kretsbyttetid og effektiviteten til optimaliseringsalgoritmen, viser vi at den totale kjøretiden til variasjonskvantealgoritmer kan reduseres betydelig.

► BibTeX-data

► Referanser

[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. "Mot kvantekjemi på en kvantedatamaskin". Nature Chemistry 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. "Muligheter for kjernefysikk og kvanteinformasjonsvitenskap" (2019). arXiv:1903.05453.
arxiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann og Johannes Knolle. "Simulering av kvante-mangekroppsdynamikk på en nåværende digital kvantedatamaskin". 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 for høyenergifysikksimuleringer". 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. "Kvantemaskinlæring". Nature 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[6] Roman Orus, Samuel Mugel og Enrique Lizaso. "Kvantedatabehandling for finans: Oversikt og prospekter". Anmeldelser i Physics 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[7] John Preskill. "Kvantedatabehandling i NISQ-æraen og utover". 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 kvantefaseestimering". Physical Review Letters 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

[9] John Preskill. "Filtolerant kvanteberegning". I Introduksjon til kvanteberegning og informasjon. 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. "Variasjonskvantealgoritmer". 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 av molekylære energier". Fysisk gjennomgang 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 variasjonskvantesimulering". 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øyelastisk kvantedynamikk ved bruk av 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. "Maskinvareeffektiv variasjonskvanteegenløser for 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. "Kvantekretslæring". Physical Review 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. "Kvantemaskinlæring ved bruk av gaussiske prosesser med effektive kvantekjerner" (2020). arXiv:2004.11280.
arxiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon og Todd J Martínez. "Kvanteberegning av elektroniske overganger ved bruk av en variasjonskvanteegenlø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. "Bruke modeller for å forbedre optimerere for variasjonskvantealgoritmer". 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 for optimal avlesning av qubits ved bruk av en kontinuerlig kvante ikke-riving må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. "Konstruksjon av den kvantevitenskapelige databehandlingen åpne brukertestbed". 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 kvanteberegning: Fremgang og utfordringer". 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 optimizer for målingsnøysomme variasjonsalgoritmer". Quantum 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

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

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

[25] Tom Schaul, Ioannis Antonoglou og David Silver. "Enhetstester for stokastisk optimalisering". 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 av bedre modeller i stokastisk optimalisering". 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øy sannsynlighetskompleksitet begrenser linjesøk basert på stokastiske orakler" (2021). arXiv:2106.06454.
arxiv: 2106.06454

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

[29] Courtney Paquette og Katya Scheinberg. "En stokastisk linjesøkmetode 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 konvergenshastighetsanalyse av en generisk linjesøkealgoritme med støy". 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 til den bratteste nedstigningen, Newtons og regulariserte Newtons metoder for ikke-konvekse ubegrensede optimaliseringsproblemer". Siam journal on optimization 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

[32] Coralia Cartis, Nicholas IM Gould og Philippe L Toint. "Om orakelkompleksiteten til førsteordens og derivatfrie algoritmer for jevn 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 grenser for å finne stasjonæ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 inntil det motsatte er bevist": Dimensjonsfri akselerasjon av gradientnedstigning på ikke-konvekse funksjoner. I internasjonal konferanse om maskinlæring. Side 654–663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

[35] Chi Jin, Praneeth Netrapalli og Michael I Jordan. "Aksellerert gradientnedstigning slipper unna setepunkter raskere enn gradientnedstigning". I konferanse 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 nullteordens metoder for 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 grenser for ikke-konveks stokastisk optimalisering" (2019). arXiv:1912.02365.
arxiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin og Tong Zhang. "Edderkopp: Nesten optimal ikke-konveks optimalisering via stokastisk baneintegrert differensialestimator". 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. "Bayesisk optimering av stokastisk gradientlinje: Redusering av måleskudd ved optimalisering av parameteriserte kvantekretser" (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 av analytiske gradienter på kvantemaskinvare". Physical Review 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. "Generaliserte enhetlig koblede klyngebølgefunksjoner for 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 variasjonsegenverdiløser på en fotonisk kvanteprosessor". Naturkommunikasjon 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 tilnærming til kvantekjemi på en kvantedatamaskin". 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 for å konstruere maskinvareeffektiv ansätze på en kvanteprosessor". 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. "Enhetsselektiv koplet-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ålekostnad for variasjonskvanteegenløser på molekylære Hamiltonians". 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 optimalisering ved hjelp av en tillitsregionmetode og tilfeldige 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. "Optimaliseringsmetoder for 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 å finne stasjonære punkter med stokastisk gradientnedstigning". I internasjonal konferanse 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 som rømmer fra setepunkter". I konferanse 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 for ikke-konveks optimalisering". In Proceedings of 32nd Conference on Neural 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. "Kompromissene ved storskala læring". 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 skyplattform optimalisert for variasjonshybridalgoritmer". 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 nøytrale 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. "Tapering av qubits for å 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: Et rammeverk med åpen kildekode for kvanteberegning" (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu og Jorge Nocedal. "Algorithm 778: L-BFGS-B: Fortran subrutiner for storskala bundet begrenset optimalisering". 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øvetakingsstrategier for stokastisk optimalisering". 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 for maskinlæring". I internasjonal konferanse 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 simuleringsbaserte rekursjoner". 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. "Operatorprøvetaking for skuddsparende optimalisering i variasjonsalgoritmer" (2020). arXiv:2004.06252.
arxiv: 2004.06252

[63] Yangyang Xu og Wotao Yin. "Blokker stokastisk gradientiterasjon for konveks og ikke-konveks optimalisering". SIAM Journal on Optimization 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Sitert av

[1] Matt Menickelly, Stefan M. Wild og Miaolan Xie, "En stokastisk kvasi-Newton-metode i fravær av vanlige tilfeldige tall", arxiv: 2302.09128, (2023).

[2] Kosuke Ito, "Latens-bevisst adaptiv skuddallokering for kjøretidseffektive variasjonskvantealgoritmer", arxiv: 2302.04422, (2023).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-03-16 18:30:45). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

Kunne ikke hente Crossref sitert av data under siste forsøk 2023-03-16 18:30:43: Kunne ikke hente siterte data for 10.22331 / q-2023-03-16-949 fra Crossref. Dette er normalt hvis DOI nylig ble registrert.

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal