Sztochasztikus optimalizálók késleltetési szempontjai variációs kvantum algoritmusokban

Sztochasztikus optimalizálók késleltetési szempontjai variációs kvantum algoritmusokban

Forrás csomópont: 2015562

Matt Menickelly1, Yunsoo Ha2és Matthew Otten3

1Matematikai és számítástechnikai osztály, Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts Ipari és Rendszermérnöki Tanszék, Észak-Karolinai Állami Egyetem, 915 Partners Way, Raleigh, NC 27601
3HRL Laboratories, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

A zajos, közepes skálájú kvantumbeállításokban előtérbe került variációs kvantum algoritmusok sztochasztikus optimalizálót igényelnek a klasszikus hardvereken. A mai napig a legtöbb kutatás sztochasztikus gradiens iteráción alapuló algoritmusokat alkalmazott sztochasztikus klasszikus optimalizálóként. Ebben a munkában ehelyett sztochasztikus optimalizálási algoritmusok használatát javasoljuk, amelyek a klasszikus determinisztikus algoritmusok dinamikáját emuláló sztochasztikus folyamatokat eredményeznek. Ez a megközelítés elméletileg jobb legrosszabb eset iterációs bonyolultságú módszereket eredményez, a nagyobb iterációs minta (lövés) bonyolultságának rovására. Elméletileg és empirikusan is megvizsgáljuk ezt a kompromisszumot, és arra a következtetésre jutottunk, hogy a sztochasztikus optimalizáló választásának preferenciáinak kifejezetten a várakozási idő és a végrehajtási idő függvényében kell függniük.

A variációs kvantum algoritmusok ígéretes jelöltek gyakorlati problémák megoldására rövid távú kvantumszámítógépeken. Az algoritmusok optimalizálásának folyamata azonban számítási szempontból költséges lehet, mivel 1) ismételt méréseket (lövéseket) kell végrehajtani a kvantumszámítógépen, és 2) be kell állítani a kvantumáramkör paramétereit. Itt egy új, SHOALS (SHOt Adaptive Line Search) nevű sztochasztikus optimalizálási algoritmust javasolunk, amely abból a feltételezésből indul ki, hogy a felvételkészítéssel végzett optimalizálásban eltöltött időt az optimalizálással töltött idő dominálja az áramköri beállítások végrehajtásával. Bemutatjuk, hogy a SHOALS ebben a beállításban felülmúlja a többi sztochasztikus optimalizálási algoritmust. Ellenkezőleg, ha a felvételi idő összemérhető az áramkör kapcsolási idejével, a sztochasztikus gradiens süllyedési algoritmusok hatékonyabbnak bizonyulnak. Figyelembe véve a lövésidő, az áramköri kapcsolási idő és az optimalizáló algoritmus hatékonysága közötti kompromisszumot, megmutatjuk, hogy a variációs kvantum algoritmusok teljes futásideje jelentősen csökkenthető.

► BibTeX adatok

► Referenciák

[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. “Towards quantum chemistry on a quantum computer”. 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. “Opportunities for nuclear physics & quantum information science” (2019). arXiv:1903.05453.
arXiv: 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann, and Johannes Knolle. “Simulating quantum many-body dynamics on a current digital quantum computer”. 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, and Christian W Bauer. “Quantum algorithm for high energy physics simulations”. 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 és Seth Lloyd. „Kvantumgépi tanulás”. Nature 549, 195–202 (2017).
https://​/​doi.org/​10.1038/​nature23474

[6] Roman Orus, Samuel Mugel és Enrique Lizaso. „Kvantumszámítás a pénzügyekhez: Áttekintés és kilátások”. Reviews in Physics 4, 100028 (2019).
https://​/​doi.org/​10.1016/​j.revip.2019.100028

[7] John Preskill. „Kvantumszámítástechnika a NISQ-korszakban és azon túl”. 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, and IA Walmsley. “Optimal quantum phase estimation”. Physical Review Letters 102, 040403 (2009).
https://​/​doi.org/​10.1103/​PhysRevLett.102.040403

[9] John Preskill. “Fault-tolerant quantum computation”. In Introduction to quantum computation and information. Pages 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. “Variational quantum algorithms”. 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. “Scalable quantum simulation of molecular energies”. Physical Review X 6, 031007 (2016).
https://​/​doi.org/​10.1103/​PhysRevX.6.031007

[12] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li és Simon C Benjamin. „A variációs kvantumszimuláció elmélete”. Quantum 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] Matthew Otten, Cristian L Cortes, and Stephen K Gray. “Noise-resilient quantum dynamics using symmetry-preserving ansatzes” (2019). arXiv:1910.06284.
arXiv: 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow és Jay M Gambetta. „Hardver-hatékony variációs kvantum-sajátmegoldó kis molekulákhoz és kvantummágnesekhez”. Nature 549, 242–246 (2017).
https://​/​doi.org/​10.1038/​nature23879

[15] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa és Keisuke Fujii. „Kvantumkör tanulás”. Fizikai Szemle 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, and Michael D Schneider. “Quantum machine learning using gaussian processes with performant quantum kernels” (2020). arXiv:2004.11280.
arXiv: 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon, and Todd J Martínez. “Quantum computation of electronic transitions using a variational quantum eigensolver”. 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, and Jarrod R McClean. “Using models to improve optimizers for variational quantum algorithms”. Quantum Science and Technology 5, 044008 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin, and RJ Schoelkopf. “Protocols for optimal readout of qubits using a continuous quantum nondemolition measurement”. 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. “Engineering the quantum scientific computing open user 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, and Jeremy M Sage. “Trapped-ion quantum computing: Progress and challenges”. Applied Physics Reviews 6, 021314 (2019).
https://​/​doi.org/​10.1063/​1.5088164

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio és Patrick J Coles. „Adaptív optimalizáló méréstakarékos variációs algoritmusokhoz”. Quantum 4, 263 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] Diederik P Kingma and Jimmy Ba. “Adam: A method for stochastic optimization” (2014). arXiv:1412.6980.
arXiv: 1412.6980

[24] Trygve Helgaker, Poul Jorgensen és Jeppe Olsen. „Molekuláris elektronszerkezet-elmélet”. John Wiley & Sons. (2014).
https://​/​doi.org/​10.1002/​9781119019572

[25] Tom Schaul, Ioannis Antonoglou, and David Silver. “Unit tests for stochastic optimization”. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings. (2014). url: http:/​/​arxiv.org/​abs/​1312.6055.
arXiv: 1312.6055

[26] Hilal Asi and John C Duchi. “The importance of better models in stochastic optimization”. Proceedings of the National Academy of Sciences 116, 22924–22930 (2019).
https://​/​doi.org/​10.1073/​pnas.1908018116

[27] Billy Jin, Katya Scheinberg, and Miaolan Xie. “High probability complexity bounds for line search based on stochastic oracles” (2021). arXiv:2106.06454.
arXiv: 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg. “Convergence rate analysis of a stochastic trust-region method via supermartingales”. INFORMS Journal on Optimization 1, 92–119 (2019).
https://​/​doi.org/​10.1287/​ijoo.2019.0016

[29] Courtney Paquette and Katya Scheinberg. “A stochastic line search method with expected complexity analysis”. SIAM Journal on Optimization 30, 349–376 (2020).
https://​/​doi.org/​10.1137/​18M1216250

[30] Albert S Berahas, Liyuan Cao, and Katya Scheinberg. “Global convergence rate analysis of a generic line search algorithm with noise”. SIAM Journal on Optimization 31, 1489–1518 (2021).
https://​/​doi.org/​10.1137/​19M1291832

[31] Coralia Cartis, Nicholas IM Gould, and Ph L Toint. “On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization problems”. Siam journal on optimization 20, 2833–2852 (2010).
https://​/​doi.org/​10.1137/​090774100

[32] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. “On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization”. SIAM Journal on Optimization 22, 66–86 (2012).
https://​/​doi.org/​10.1137/​100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. “Lower bounds for finding stationary points I”. Mathematical Programming 184, 71–120 (2020).
https://​/​doi.org/​10.1007/​s10107-019-01406-y

[34] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. ““convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions”. In International Conference on Machine Learning. Pages 654–663. PMLR (2017).
https://​/​doi.org/​10.5555/​3305381.3305449

[35] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. “Accelerated gradient descent escapes saddle points faster than gradient descent”. In Conference On Learning Theory. Pages 1042–1085. PMLR (2018). url: https:/​/​proceedings.mlr.press/​v75/​jin18a.html.
https://​/​proceedings.mlr.press/​v75/​jin18a.html

[36] Saeed Ghadimi and Guanghui Lan. “Stochastic first-and zeroth-order methods for nonconvex stochastic programming”. 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, and Blake Woodworth. “Lower bounds for non-convex stochastic optimization” (2019). arXiv:1912.02365.
arXiv: 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. “Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator”. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, 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

[39] Shiro Tamiya and Hayata Yamasaki. “Stochastic gradient line bayesian optimization: Reducing measurement shots in optimizing parameterized quantum circuits” (2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv: 2111.07952

[40] Pascual Jordan and Eugene Paul Wigner. “über das paulische äquivalenzverbot”. In The Collected Works of Eugene Paul Wigner. Pages 109–129. Springer (1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac és Nathan Killoran. „Analitikai gradiensek kiértékelése kvantumhardveren”. Physical Review A 99, 032331 (2019).
https://​/​doi.org/​10.1103/​PhysRevA.99.032331

[42] Joonho Lee, William J Huggins, Martin Head-Gordon, and K Birgitta Whaley. “Generalized unitary coupled cluster wave functions for quantum computation”. 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, and Jeremy L O’brien. “A variational eigenvalue solver on a photonic quantum processor”. 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, and Artur F Izmaylov. “Qubit coupled cluster method: a systematic approach to quantum chemistry on a quantum computer”. 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, and Sophia E Economou. “qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansätze on a quantum processor”. PRX Quantum 2, 020310 (2021).
https://​/​doi.org/​10.1103/​PRXQuantum.2.020310

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray, and Matthew Otten. “Unitary Selective Coupled-Cluster Method”. 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, and Frederic T Chong. “$ o (n^3) $ measurement cost for variational quantum eigensolver on molecular Hamiltonians”. IEEE Transactions on Quantum Engineering 1, 1–24 (2020).
https://​/​doi.org/​10.1109/​TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly, and Katya Scheinberg. “Stochastic optimization using a trust-region method and random models”. Mathematical Programming 169, 447–487 (2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis, and Jorge Nocedal. “Optimization methods for large-scale machine learning”. Siam Review 60, 223–311 (2018).
https://​/​doi.org/​10.1137/​16M1080173

[50] Yoel Drori and Ohad Shamir. “The complexity of finding stationary points with stochastic gradient descent”. In International Conference on Machine Learning. Pages 2658–2667. PMLR (2020). url: https:/​/​proceedings.mlr.press/​v119/​drori20a.html.
https://​/​proceedings.mlr.press/​v119/​drori20a.html

[51] Cong Fang, Zhouchen Lin, and Tong Zhang. “Sharp analysis for nonconvex SGD escaping from saddle points”. In Conference on Learning Theory. Pages 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, and Sanjiv Kumar. “Adaptive methods for nonconvex optimization”. 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 and Olivier Bousquet. “The tradeoffs of large scale learning”. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, 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

[54] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva, and Robert S Smith. “A quantum-classical cloud platform optimized for variational hybrid algorithms”. Quantum Science and Technology 5, 024003 (2020).
https://​/​doi.org/​10.1088/​2058-9565/​ab7559

[55] H-J Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac, and Peter Zoller. “Quantum computing with neutral atoms”. Journal of modern optics 47, 415–451 (2000).
https://​/​doi.org/​10.1080/​09500340008244052

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo és Kristan Temme. „Kúbitok szűkítése a fermionikus Hamiltoniánusok szimulálására” (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: An open-source framework for quantum computing” (2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu, and Jorge Nocedal. “Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization”. ACM Transactions on Mathematical Software (TOMS) 23, 550–560 (1997).
https://​/​doi.org/​10.1145/​279232.279236

[59] Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. “Adaptive sampling strategies for stochastic optimization”. SIAM Journal on Optimization 28, 3312–3343 (2018).
https://​/​doi.org/​10.1137/​17M1154679

[60] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. “A progressive batching L-BFGS method for machine learning”. In International Conference on Machine Learning. Pages 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, and Fatemeh S Hashemi. “On sampling rates in simulation-based recursions”. SIAM Journal on Optimization 28, 45–73 (2018).
https://​/​doi.org/​10.1137/​140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma és Patrick J Coles. „Operátori mintavétel a takarékos optimalizáláshoz variációs algoritmusokban” (2020). arXiv:2004.06252.
arXiv: 2004.06252

[63] Yangyang Xu and Wotao Yin. “Block stochastic gradient iteration for convex and nonconvex optimization”. SIAM Journal on Optimization 25, 1686–1716 (2015).
https://​/​doi.org/​10.1137/​140983938

Idézi

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

[2] Kosuke Ito, “Latency-aware adaptive shot allocation for run-time efficient variational quantum algorithms”, arXiv: 2302.04422, (2023).

A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2023-03-16 18:30:45). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.

Nem sikerült lekérni Az adatok által hivatkozott kereszthivatkozás utolsó próbálkozáskor 2023-03-16 18:30:43: Nem sikerült lekérni a 10.22331/q-2023-03-16-949 hivatkozás által hivatkozott adatokat a Crossref-től. Ez normális, ha a DOI-t nemrég regisztrálták.

Időbélyeg:

Még több Quantum Journal