Premisleki o zakasnitvah za stohastične optimizatorje v variacijskih kvantnih algoritmih

Premisleki o zakasnitvah za stohastične optimizatorje v variacijskih kvantnih algoritmih

Izvorno vozlišče: 2015562

Matt Menickelly1, Yunsoo Ha2in Matthew Otten3

1Oddelek za matematiko in računalništvo, Nacionalni laboratorij Argonne, 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

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Variacijski kvantni algoritmi, ki so postali pomembni v hrupni kvantni nastavitvi vmesne lestvice, zahtevajo implementacijo stohastičnega optimizatorja na klasični strojni opremi. Do danes je večina raziskav uporabljala algoritme, ki temeljijo na iteraciji stohastičnega gradienta kot stohastični klasični optimizator. V tem delu namesto tega predlagamo uporabo stohastičnih optimizacijskih algoritmov, ki dajejo stohastične procese, ki posnemajo dinamiko klasičnih determinističnih algoritmov. Rezultat tega pristopa so metode s teoretično boljšo zapletenostjo najslabšega primera iteracije na račun večje zapletenosti vzorca (posnetka) na iteracijo. Ta kompromis raziskujemo tako teoretično kot empirično in sklepamo, da bi morale biti preference za izbiro stohastičnega optimizatorja izrecno odvisne od funkcije zakasnitve in časov izvajanja posnetka.

Variacijski kvantni algoritmi so obetavni kandidati za reševanje praktičnih problemov na bližnjih kvantnih računalnikih. Vendar pa je postopek optimizacije teh algoritmov lahko računsko drag zaradi dveh potreb po 1) izvajanju ponavljajočih se meritev (posnetkov) na kvantnem računalniku in 2) prilagajanju parametrov kvantnega vezja. Tukaj predlagamo nov algoritem za stohastično optimizacijo, imenovan SHOALS (SHOt Adaptive Line Search), ki je zasnovan ob predpostavki, da čas, porabljen za optimizacijo izvajanja posnetkov, prevladuje nad časom, porabljenim za optimizacijo izvajanja prilagoditev vezja. Dokazujemo, da SHOALS v tej nastavitvi prekaša druge algoritme stohastične optimizacije. Nasprotno, ko je čas strela primerljiv s časom preklopa vezja, se ugotovi, da so algoritmi stohastičnega gradientnega spuščanja bolj učinkoviti. Z upoštevanjem kompromisov med časom udarca, časom preklopa vezja in učinkovitostjo optimizacijskega algoritma pokažemo, da je skupni čas delovanja variacijskih kvantnih algoritmov mogoče znatno zmanjšati.

► BibTeX podatki

► Reference

[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. “Kvantni kemiji na kvantnem računalniku”. Nature Chemistry 2, 106–111 (2010).
https: / / doi.org/ 10.1038 / nchem.483

[2] Ian C Cloët, Matthew R Dietrich, John Arrington, Aleksej Bazavov, Michael Bishof, Adam Freese, Aleksej V Gorškov, Anna Grassellino, Kawtar Hafidi, Zubin Jacob idr. »Priložnosti za jedrsko fiziko in kvantno informacijsko znanost« (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann in Johannes Knolle. "Simulacija kvantne dinamike več teles na trenutnem digitalnem kvantnem računalniku". npj Kvantne informacije 5, 1–13 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Benjamin Nachman, Davide Provasoli, Wibe A de Jong in Christian W Bauer. "Kvantni algoritem za simulacije visokoenergijske fizike". 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 in Seth Lloyd. "Kvantno strojno učenje". Narava 549, 195–202 (2017).
https: / / doi.org/ 10.1038 / nature23474

[6] Roman Orus, Samuel Mugel in Enrique Lizaso. "Kvantno računalništvo za finance: pregled in možnosti". Ocene iz fizike 4, 100028 (2019).
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[7] John Preskill. "Kvantno računalništvo v dobi NISQ in pozneje". 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 in IA Walmsley. "Optimalna kvantna ocena faze". Physical Review Letters 102, 040403 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.040403

[9] John Preskill. "Kvantno računanje, odporno na napake". V uvodu v kvantno računanje in informacije. Strani 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. "Variacijski kvantni algoritmi". 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 idr. "Skalabilna kvantna simulacija molekulskih energij". Physical Review X 6, 031007 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.031007

[12] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li in Simon C Benjamin. “Teorija variacijske kvantne simulacije”. Quantum 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Matthew Otten, Cristian L Cortes in Stephen K Gray. »Kvantna dinamika, odporna na hrup, z uporabo anzacev, ki ohranjajo simetrijo« (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow in Jay M Gambetta. "Strojno učinkovit variacijski kvantni lastni reševalec za majhne molekule in kvantne magnete". Narava 549, 242–246 (2017).
https: / / doi.org/ 10.1038 / nature23879

[15] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa in Keisuke Fujii. "Učenje kvantnega vezja". 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 in Michael D Schneider. »Učenje kvantnega stroja z uporabo gaussovih procesov z zmogljivimi kvantnimi jedri« (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon in Todd J Martínez. "Kvantno računanje elektronskih prehodov z uporabo variacijskega kvantnega lastnega reševalca". 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 in Jarrod R McClean. "Uporaba modelov za izboljšanje optimizatorjev za variacijske kvantne algoritme". Kvantna znanost in tehnologija 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin in RJ Schoelkopf. "Protokoli za optimalno odčitavanje kubitov z uporabo neprekinjenega kvantnega nerušitvenega merjenja". 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 idr. "Inženiring kvantno znanstvenega računalništva z odprtim uporabniškim testom". 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 in Jeremy M Sage. "Kvantno računalništvo z ujetimi ioni: napredek in izzivi". Applied Physics Reviews 6, 021314 (2019).
https: / / doi.org/ 10.1063 / 1.5088164

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio in Patrick J Coles. »Prilagodljiv optimizator za variacijske algoritme, ki so varčni pri meritvah«. Quantum 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Diederik P Kingma in Jimmy Ba. “Adam: Metoda za stohastično optimizacijo” (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Trygve Helgaker, Poul Jorgensen in Jeppe Olsen. “Teorija molekularne elektronske strukture”. John Wiley & Sons. (2014).
https: / / doi.org/ 10.1002 / 9781119019572

[25] Tom Schaul, Ioannis Antonoglou in David Silver. "Enotni testi za stohastično optimizacijo". V Yoshua Bengio in Yann LeCun, urednika, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Kanada, april 14-16, 2014, Conference Track Proceedings. (2014). url: http://​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Hilal Asi in John C Duchi. “Pomen boljših modelov v stohastični optimizaciji”. Zbornik Nacionalne akademije znanosti 116, 22924–22930 (2019).
https: / / doi.org/ 10.1073 / pnas.1908018116

[27] Billy Jin, Katya Scheinberg in Miaolan Xie. »Meje kompleksnosti visoke verjetnosti za iskanje vrstic na podlagi stohastičnih orakljev« (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly in Katya Scheinberg. "Analiza stopnje konvergence stohastične metode regije zaupanja prek supermartingalov". INFORMS Revija za optimizacijo 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Courtney Paquette in Katya Scheinberg. »Stohastična metoda iskanja linij s pričakovano analizo kompleksnosti«. SIAM Journal on Optimization 30, 349–376 (2020).
https: / / doi.org/ 10.1137 / 18M1216250

[30] Albert S. Berahas, Liyuan Cao in Katya Scheinberg. “Globalna analiza stopnje konvergence generičnega algoritma za iskanje linij s šumom”. SIAM Journal on Optimization 31, 1489–1518 (2021).
https: / / doi.org/ 10.1137 / 19M1291832

[31] Coralia Cartis, Nicholas IM Gould in Ph L Toint. “O kompleksnosti najstrmejšega spusta, Newtonove in regularizirane Newtonove metode za nekonveksne neomejene optimizacijske probleme”. Revija Siam o optimizaciji 20, 2833–2852 (2010).
https: / / doi.org/ 10.1137 / 090774100

[32] Coralia Cartis, Nicholas IM Gould in Philippe L Toint. "O orakeljski kompleksnosti algoritmov prvega reda in algoritmov brez izpeljav za gladko nekonveksno minimiziranje". SIAM Journal on Optimization 22, 66–86 (2012).
https: / / doi.org/ 10.1137 / 100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder in Aaron Sidford. "Spodnje meje za iskanje stacionarnih točk I". Matematično programiranje 184, 71–120 (2020).
https: / / doi.org/ 10.1007 / s10107-019-01406-y

[34] Yair Carmon, John C Duchi, Oliver Hinder in Aaron Sidford. ""konveksno, dokler se ne dokaže krivda": Brezdimenzijski pospešek gradientnega spuščanja na nekonveksnih funkcijah". Na mednarodni konferenci o strojnem učenju. Strani 654–663. PMLR (2017).
https: / / doi.org/ 10.5555 / 3305381.3305449

[35] Chi Jin, Praneeth Netrapalli in Michael I Jordan. »Pospešeni spust po naklonu hitreje uide iz sedla kot spust po naklonu«. Na konferenci o teoriji učenja. Strani 1042–1085. PMLR (2018). url: https://​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Saeed Ghadimi in Guanghui Lan. “Stohastične metode prvega in ničelnega reda za nekonveksno stohastično programiranje”. 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 in Blake Woodworth. »Spodnje meje za nekonveksno stohastično optimizacijo« (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin in Tong Zhang. "Spider: Skoraj optimalna nekonveksna optimizacija prek stohastičnega diferencialnega ocenjevalca, integriranega v pot". V S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi in R. Garnett, uredniki, Advances in Neural Information Processing Systems. Zvezek 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 in Hayata Yamasaki. »Bayesova optimizacija stohastične gradientne črte: Zmanjšanje merilnih posnetkov pri optimizaciji parametriziranih kvantnih vezij« (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Pascual Jordan in Eugene Paul Wigner. „über das paulische äquivalenzverbot“. V Zbranih delih Eugena Paula Wignerja. Strani 109–129. Springer (1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac in Nathan Killoran. "Vrednotenje analitičnih gradientov na kvantni strojni opremi". Physical Review A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[42] Joonho Lee, William J Huggins, Martin Head-Gordon in K Birgitta Whaley. "Splošne enotne sklopljene valovne funkcije grozdov za kvantno računanje". 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 in Jeremy L O'brien. "Variacijski reševalec lastnih vrednosti na fotonskem kvantnem procesorju". 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 in Artur F Izmaylov. "Metoda sklopljenih grozdov Qubit: sistematičen pristop k kvantni kemiji na kvantnem računalniku". 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 in Sophia E Economou. “qubit-ADAPT-VQE: prilagodljiv algoritem za izdelavo strojno učinkovitih ansätze na kvantnem procesorju”. PRX Quantum 2, 020310 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020310

[46] Dmitrij A. Fedorov, Jurij Aleksejev, Stephen K. Gray in Matthew Otten. “Enotna selektivna sklopljena metoda”. 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 in Frederic T Chong. “$ o (n^3) $ stroški meritev za variacijski kvantni lastni reševalec na molekularnih hamiltonianih”. IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly in Katya Scheinberg. “Stohastična optimizacija z uporabo metode regije zaupanja in naključnih modelov”. Matematično programiranje 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis in Jorge Nocedal. "Optimizacijske metode za obsežno strojno učenje". Siam Review 60, 223–311 (2018).
https: / / doi.org/ 10.1137 / 16M1080173

[50] Yoel Drori in Ohad Shamir. "Zapletenost iskanja stacionarnih točk s stohastičnim gradientnim spuščanjem". Na mednarodni konferenci o strojnem učenju. Strani 2658–2667. PMLR (2020). url: https://​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Cong Fang, Zhouchen Lin in Tong Zhang. "Ostra analiza za nekonveksne SGD, ki uhajajo iz sedla". Na konferenci o teoriji učenja. Strani 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 in Sanjiv Kumar. “Prilagodljive metode za nekonveksno optimizacijo”. V zborniku 32. konference o sistemih za obdelavo nevronskih informacij (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 in Olivier Bousquet. "Kompromisi učenja velikega obsega". V J. Platt, D. Koller, Y. Singer in S. Roweis, uredniki, Advances in Neural Information Processing Systems. Zvezek 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 in Robert S Smith. "Kvantno-klasična platforma v oblaku, optimizirana za variacijske hibridne algoritme". Kvantna znanost in tehnologija 5, 024003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7559

[55] HJ Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac in Peter Zoller. "Kvantno računalništvo z nevtralnimi atomi". Journal of Modern Optics 47, 415–451 (2000).
https: / / doi.org/ 10.1080 / 09500340008244052

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo in Kristan Temme. »Zožanje kubitov za simulacijo fermionskih hamiltonianov« (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: Odprtokodni okvir za kvantno računalništvo« (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu in Jorge Nocedal. “Algoritem 778: L-BFGS-B: Fortran podprogrami za obsežno vezano omejeno optimizacijo”. ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https: / / doi.org/ 10.1145 / 279232.279236

[59] Raghu Bollapragada, Richard Byrd in Jorge Nocedal. "Prilagodljive strategije vzorčenja za stohastično optimizacijo". SIAM Journal on Optimization 28, 3312–3343 (2018).
https: / / doi.org/ 10.1137 / 17M1154679

[60] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi in Ping Tak Peter Tang. »Metoda L-BFGS s progresivnim šaržerjem za strojno učenje«. Na mednarodni konferenci o strojnem učenju. Strani 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 in Fatemeh S. Hashemi. "O stopnjah vzorčenja v rekurzijah, ki temeljijo na simulaciji". SIAM Journal on Optimization 28, 45–73 (2018).
https: / / doi.org/ 10.1137 / 140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma in Patrick J Coles. »Vzorčenje operaterja za varčno optimizacijo v variacijskih algoritmih« (2020). arXiv:2004.06252.
arXiv: 2004.06252

[63] Yangyang Xu in Wotao Yin. »Iteracija stohastičnega gradienta bloka za konveksno in nekonveksno optimizacijo«. SIAM Journal on Optimization 25, 1686–1716 (2015).
https: / / doi.org/ 10.1137 / 140983938

Navedel

[1] Matt Menickelly, Stefan M. Wild in Miaolan Xie, "Stohastična kvazi-Newtonova metoda v odsotnosti običajnih naključnih števil", arXiv: 2302.09128, (2023).

[2] Kosuke Ito, »Latency-aware adaptive shot allocation for run-time učinkovite variational quantum algorithms«, arXiv: 2302.04422, (2023).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2023-03-16 18:30:45). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

Pridobitve ni bilo mogoče Crossref citirani podatki med zadnjim poskusom 2023-03-16 18:30:43: Citiranih podatkov za 10.22331 / q-2023-03-16-949 od Crossrefa ni bilo mogoče pridobiti. To je normalno, če je bil DOI registriran pred kratkim.

Časovni žig:

Več od Quantum Journal