Latency considerations for stochastic optimizers in variational quantum algorithms

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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Variational quantum algorithms, which have risen to prominence in the noisy intermediate-scale quantum setting, require the implementation of a stochastic optimizer on classical hardware. To date, most research has employed algorithms based on the stochastic gradient iteration as the stochastic classical optimizer. In this work we propose instead using stochastic optimization algorithms that yield stochastic processes emulating the dynamics of classical deterministic algorithms. This approach results in methods with theoretically superior worst-case iteration complexities, at the expense of greater per-iteration sample (shot) complexities. We investigate this trade-off both theoretically and empirically and conclude that preferences for a choice of stochastic optimizer should explicitly depend on a function of both latency and shot execution times.

Variational quantum algorithms are promising candidates for solving practical problems on near-term quantum computers. However, the process of optimizing these algorithms can be computationally expensive due to the two needs to 1) perform repeated measurements (shots) on the quantum computer and 2) adjust the quantum circuit parameters. Here, we propose a new stochastic optimization algorithm called SHOALS (SHOt Adaptive Line Search) that is designed under the assumption that the time spent in optimization performing shots is dominated by the time spent in optimization performing circuit adjustments. We demonstrate that SHOALS outperforms other stochastic optimization algorithms in this setting. On the contrary, when the shot time is comparable to the circuit switching time, stochastic gradient descent algorithms are found to be more efficient. By considering the trade-offs between shot time, circuit switching time, and the efficiency of the optimization algorithm, we show that the total run time of variational quantum algorithms can be significantly reduced.

► BibTeX data

► References

[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).

[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.

[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).

[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).

[5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017).

[6] Roman Orus, Samuel Mugel, and Enrique Lizaso. ``Quantum computing for finance: Overview and prospects''. Reviews in Physics 4, 100028 (2019).

[7] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[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).

[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).

[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).

[12] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C Benjamin. ``Theory of variational quantum simulation''. Quantum 3, 191 (2019).

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

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets''. Nature 549, 242–246 (2017).

[15] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. ``Quantum circuit learning''. Physical Review A 98, 032309 (2018).

[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.

[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).

[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).

[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).

[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).

[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).

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J Coles. ``An adaptive optimizer for measurement-frugal variational algorithms''. Quantum 4, 263 (2020).

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

[24] Trygve Helgaker, Poul Jorgensen, and Jeppe Olsen. ``Molecular electronic-structure theory''. John Wiley & Sons. (2014).

[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:/​/​​abs/​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).

[27] Billy Jin, Katya Scheinberg, and Miaolan Xie. ``High probability complexity bounds for line search based on stochastic oracles'' (2021). 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).

[29] Courtney Paquette and Katya Scheinberg. ``A stochastic line search method with expected complexity analysis''. SIAM Journal on Optimization 30, 349–376 (2020).

[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).

[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).

[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).

[33] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. ``Lower bounds for finding stationary points I''. Mathematical Programming 184, 71–120 (2020).

[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).

[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:/​/​​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).

[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.

[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:/​/​​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.

[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, and Nathan Killoran. ``Evaluating analytic gradients on quantum hardware''. Physical Review A 99, 032331 (2019).

[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).

[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:/​/​​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).

[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).

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray, and Matthew Otten. ``Unitary Selective Coupled-Cluster Method''. Quantum 6, 703 (2022).

[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).

[48] Ruobing Chen, Matt Menickelly, and Katya Scheinberg. ``Stochastic optimization using a trust-region method and random models''. Mathematical Programming 169, 447–487 (2018).

[49] Léon Bottou, Frank E Curtis, and Jorge Nocedal. ``Optimization methods for large-scale machine learning''. Siam Review 60, 223–311 (2018).

[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:/​/​​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:/​/​​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:/​/​​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:/​/​​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).

[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).

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo, and Kristan Temme. ``Tapering off qubits to simulate fermionic Hamiltonians'' (2017). 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).

[59] Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. ``Adaptive sampling strategies for stochastic optimization''. SIAM Journal on Optimization 28, 3312–3343 (2018).

[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:/​/​​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).

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma, and Patrick J Coles. ``Operator sampling for shot-frugal optimization in variational algorithms'' (2020). 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).

Cited by

[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).

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-23 07:10:23). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-03-23 07:10:22).