Latensöverväganden för stokastiska optimerare i variationsmässiga kvantalgoritmer

Latensöverväganden för stokastiska optimerare i variationsmässiga kvantalgoritmer

Tidsstämpel: 16 mars 2023 2:28
Källnod: 2015562

Matt Menickelly1, Yunsoo Ha2, och 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

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Varierande kvantalgoritmer, som har blivit framträdande i den bullriga kvantinställningen i mellanskalig skala, kräver implementering av en stokastisk optimerare på klassisk hårdvara. Hittills har den mesta forskningen använt algoritmer baserade på den stokastiska gradientiterationen som den stokastiska klassiska optimeraren. I detta arbete föreslår vi istället att använda stokastiska optimeringsalgoritmer som ger stokastiska processer som emulerar dynamiken hos klassiska deterministiska algoritmer. Detta tillvägagångssätt resulterar i metoder med teoretiskt överlägsna worst-case iterationskomplexiteter, på bekostnad av större per-iteration prov (shot) komplexitet. Vi undersöker denna avvägning både teoretiskt och empiriskt och drar slutsatsen att preferenser för ett val av stokastisk optimerare uttryckligen bör bero på en funktion av både latens och körningstider.

Utvald bild: Latenser och målprecision påverkar valet av stokastiska optimerare för variationsmässiga kvantalgoritmer.

Populär sammanfattning

Varierande kvantalgoritmer är lovande kandidater för att lösa praktiska problem på kortsiktiga kvantdatorer. Processen att optimera dessa algoritmer kan dock vara beräkningsmässigt dyr på grund av de två behoven att 1) ​​utföra upprepade mätningar (skott) på kvantdatorn och 2) justera kvantkretsparametrarna. Här föreslår vi en ny stokastisk optimeringsalgoritm som kallas SHOALS (SHOt Adaptive Line Search) som är utformad under antagandet att tiden som spenderas vid optimering av skott domineras av tiden som spenderas i optimering av kretsjusteringar. Vi visar att SHOALS överträffar andra stokastiska optimeringsalgoritmer i den här inställningen. Tvärtom, när skotttiden är jämförbar med kretskopplingstiden, visar sig stokastiska gradientnedstigningsalgoritmer vara mer effektiva. Genom att överväga avvägningarna mellan skotttid, kretsomkopplingstid och effektiviteten hos optimeringsalgoritmen visar vi att den totala körtiden för variationskvantalgoritmer kan reduceras avsevärt.

► BibTeX-data

► Referenser

[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 kvantkemi på en kvantdator". 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. "Möjligheter för kärnfysik och kvantinformationsvetenskap" (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann och Johannes Knolle. "Simulera kvantmångakroppsdynamik på en aktuell digital kvantdator". 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 och Christian W Bauer. "Kvantalgoritm för högenergifysiksimuleringar". 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 och Seth Lloyd. "Kvantmaskininlärning". Nature 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[6] Roman Orus, Samuel Mugel och Enrique Lizaso. "Kvantberäkning för finans: Översikt och framtidsutsikter". Reviews in Physics 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[7] John Preskill. "Quantum computing i NISQ-eran och därefter". 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 och IA Walmsley. "Optimal kvantfasuppskattning". Physical Review Letters 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

[9] John Preskill. "Feltolerant kvantberäkning". Introduktion till kvantberäkning och information. Sidorna 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. "Variationella kvantalgoritmer". Naturrecensioner Fysik Sidorna 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. "Skalbar kvantsimulering av molekylära energier". Physical Review X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

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

[13] Matthew Otten, Cristian L Cortes och Stephen K Gray. "Brusfjädrande kvantdynamik med hjälp av symmetribevarande ansatzes" (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow och Jay M Gambetta. "Hårdvarueffektiv variationskvantumegenlösare för små molekyler och kvantmagneter". Nature 549, 242–246 (2017).
https: / / doi.org/ 10.1038 / nature23879

[15] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa och Keisuke Fujii. "Kvantumkretslärande". Fysisk granskning 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 och Michael D Schneider. "Kvantmaskininlärning med gaussiska processer med presterande kvantkärnor" (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon och Todd J Martínez. "Kvantberäkning av elektroniska övergångar med hjälp av en variationskvantumegenlösare". 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 och Jarrod R McClean. "Att använda modeller för att förbättra optimerare för variationsmässiga kvantalgoritmer". Quantum Science and Technology 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin och RJ Schoelkopf. "Protokoll för optimal avläsning av qubits med hjälp av en kontinuerlig kvantmätning utan rivning". 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 av den kvantvetenskapliga testbädden för öppen användare". 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 och Jeremy M Sage. "Fångad-jon kvantberäkning: framsteg och utmaningar". Applied Physics Reviews 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio och Patrick J Coles. "En adaptiv optimerare för mätningssnåla variationsalgoritmer". Quantum 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Diederik P Kingma och Jimmy Ba. "Adam: En metod för stokastisk optimering" (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Trygve Helgaker, Poul Jorgensen och Jeppe Olsen. "Molekylär elektronisk strukturteori". John Wiley & Sons. (2014).
https: / / doi.org/ 10.1002 / 9781119019572

[25] Tom Schaul, Ioannis Antonoglou och David Silver. "Enhetstester för stokastisk optimering". I Yoshua Bengio och Yann LeCun, redaktörer, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Kanada, 14-16 april 2014, Conference Track Proceedings. (2014). URL: http://​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Hilal Asi och John C Duchi. "Vikten av bättre modeller för 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 och Miaolan Xie. "Komplexitet med hög sannolikhet begränsar linjesökning baserat på stokastiska orakel" (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly och Katya Scheinberg. "Konvergenshastighetsanalys av en stokastisk trust-region-metod via supermartingales". INFORMERAR Journal on Optimization 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Courtney Paquette och Katya Scheinberg. "En stokastisk linjesökningsmetod med förväntad komplexitetsanalys". SIAM Journal on Optimization 30, 349–376 (2020).
https: / / doi.org/ 10.1137 / 18M1216250

[30] Albert S Berahas, Liyuan Cao och Katya Scheinberg. "Global konvergenshastighetsanalys av en generisk linjesökningsalgoritm med brus". SIAM Journal on Optimization 31, 1489–1518 (2021).
https: / / doi.org/ 10.1137 / 19M1291832

[31] Coralia Cartis, Nicholas IM Gould och Ph L Toint. "Om komplexiteten av brantaste nedstigning, Newtons och regulariserade Newtons metoder för icke-konvexa oinskränkta optimeringsproblem". Siam journal on optimization 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

[32] Coralia Cartis, Nicholas IM Gould och Philippe L Toint. "Om orakelkomplexiteten hos första ordningens och derivatfria algoritmer för smidig icke-konvex minimering". SIAM Journal on Optimization 22, 66–86 (2012).
https: / / doi.org/ 10.1137 / 100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder och Aaron Sidford. "Nedre gränser för att hitta stationära 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 och Aaron Sidford. ""konvex tills motsatsen bevisats": Dimensionsfri acceleration av gradientnedstigning på icke-konvexa funktioner". I internationell konferens om maskininlärning. Sidorna 654–663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

[35] Chi Jin, Praneeth Netrapalli och Michael I Jordan. "Accelererad gradientnedstigning undkommer sadelpunkter snabbare än gradientnedstigning". I konferens om lärandeteori. Sidorna 1042–1085. PMLR (2018). URL: https://​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Saeed Ghadimi och Guanghui Lan. "Stokastiska metoder av första och nollte ordningen för icke-konvex 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 och Blake Woodworth. "Lägre gränser för icke-konvex stokastisk optimering" (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin och Tong Zhang. "Spider: Nästan optimal icke-konvex optimering via stokastisk vägintegrerad differentialskattare". I S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi och R. Garnett, redaktörer, Advances in Neural Information Processing Systems. Volym 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 och Hayata Yamasaki. "Stochastisk gradientlinje bayesisk optimering: Reducering av mätningar vid optimering av parametriserade kvantkretsar" (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Pascual Jordan och Eugene Paul Wigner. ”über das paulische äquivalenzverbot”. I The Collected Works of Eugene Paul Wigner. Sidorna 109–129. Springer (1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac och Nathan Killoran. "Utvärdering av analytiska gradienter på kvanthårdvara". Physical Review A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[42] Joonho Lee, William J Huggins, Martin Head-Gordon och K Birgitta Whaley. "Generaliserade enhetliga kopplade klustervågfunktioner för kvantberäkning". 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 och Jeremy L O'brien. "En variabel egenvärdeslösare på en fotonisk kvantprocessor". 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 och Artur F Izmaylov. "Qubit-kopplad klustermetod: en systematisk metod för kvantkemi på en kvantdator". 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 och Sophia E Economou. "qubit-ADAPT-VQE: En adaptiv algoritm för att konstruera hårdvarueffektiv ansätze på en kvantprocessor". PRX Quantum 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray och Matthew Otten. "Enhetsselektiv kopplad-klustermetod". 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 och Frederic T Chong. "$ o (n^3) $ mätkostnad för variationskvantumegenlösare på molekylära Hamiltonianer". IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly och Katya Scheinberg. "Stokastisk optimering med hjälp av en förtroenderegionsmetod och slumpmässiga modeller". Matematisk programmering 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis och Jorge Nocedal. "Optimeringsmetoder för storskalig maskininlärning". Siam Review 60, 223–311 (2018).
https: / / doi.org/ 10.1137 / 16M1080173

[50] Yoel Drori och Ohad Shamir. "Komplexiteten i att hitta stationära punkter med stokastisk gradientnedstigning". I internationell konferens om maskininlärning. Sidorna 2658–2667. PMLR (2020). URL: https://​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Cong Fang, Zhouchen Lin och Tong Zhang. "Skärp analys för icke-konvex SGD som flyr från sadelpunkter". I konferens om lärandeteori. Sidorna 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 och Sanjiv Kumar. "Adaptiva metoder för icke-konvex optimering". 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 och Olivier Bousquet. "Kompromisserna med storskaligt lärande". I J. Platt, D. Koller, Y. Singer och S. Roweis, redaktörer, Advances in Neural Information Processing Systems. Volym 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 och Robert S Smith. "En kvantklassisk molnplattform optimerad för 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 och Peter Zoller. "Kvantberäkning med neutrala atomer". Journal of modern optics 47, 415–451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo och Kristan Temme. "Avtrappa qubits för att simulera fermioniska 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: Ett ramverk med öppen källkod för kvantberäkning" (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu och Jorge Nocedal. "Algorithm 778: L-BFGS-B: Fortran subrutiner för storskalig bunden begränsad optimering". ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236

[59] Raghu Bollapragada, Richard Byrd och Jorge Nocedal. "Adaptiva samplingsstrategier för 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 och Ping Tak Peter Tang. "En progressiv batchning L-BFGS-metod för maskininlärning". I internationell konferens om maskininlärning. Sidorna 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 och Fatemeh S Hashemi. "Om samplingsfrekvenser i simuleringsbaserade rekursioner". SIAM Journal on Optimization 28, 45–73 (2018).
https: / / doi.org/ 10.1137 / 140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma och Patrick J Coles. "Operatorsampling för skottsparsam optimering i variationsalgoritmer" (2020). arXiv:2004.06252.
arXiv: 2004.06252

[63] Yangyang Xu och Wotao Yin. "Blockera stokastisk gradientiteration för konvex och icke-konvex optimering". SIAM Journal on Optimization 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Citerad av

[1] Matt Menickelly, Stefan M. Wild och Miaolan Xie, "En stokastisk kvasi-Newton-metod i frånvaro av vanliga slumpmässiga tal", arXiv: 2302.09128, (2023).

[2] Kosuke Ito, "Latensmedveten adaptiv skottallokering för körtidseffektiva variationskvantalgoritmer", arXiv: 2302.04422, (2023).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-03-16 18:30:45). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

Det gick inte att hämta Crossref citerade data under senaste försöket 2023-03-16 18:30:43: Det gick inte att hämta citerade data för 10.22331 / q-2023-03-16-949 från Crossref. Detta är normalt om DOI registrerades nyligen.

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal