Quantum algorithms and lower bounds for convex optimization

Shouvanik Chakrabarti; Andrew M. Childs; Tongyang Li; Xiaodi Wu

doi:10.22331/q-2020-01-13-221

Quantum algorithms and lower bounds for convex optimization

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu

Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland

Published:	2020-01-13, volume 4, page 221
Eprint:	arXiv:1809.01731v3
Doi:	https://doi.org/10.22331/q-2020-01-13-221
Citation:	Quantum 4, 221 (2020).

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

Abstract

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an $n$-dimensional convex body using $\tilde{O}(n)$ queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires $\tilde{\Omega}(\sqrt n)$ evaluation queries and $\Omega(\sqrt{n})$ membership queries.

Popular summary

Convex optimization has been a central topic in mathematics, theoretical computer science, and operations research over the last several decades. Our work, along with an independent paper by van Apeldoorn et al., gives the first quantum algorithm with provable quantum speedup for general convex optimization. On the other hand, our quantum lower bounds demonstrate that the quantum speedup for general convex optimization is at most polynomial, ruling out the possibility of an exponential speedup (such as in Shor’s factoring algorithm.

► BibTeX data

@article{Chakrabarti2020quantumalgorithms,
  doi = {10.22331/q-2020-01-13-221},
  url = {https://doi.org/10.22331/q-2020-01-13-221},
  title = {Quantum algorithms and lower bounds for convex optimization},
  author = {Chakrabarti, Shouvanik and Childs, Andrew M. and Li, Tongyang and Wu, Xiaodi},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {221},
  month = jan,
  year = {2020}
}

► References

[1] Andris Ambainis and Ashley Montanaro, Quantum algorithms for search with wildcards and combinatorial group testing, Quantum Information and Computation 14 (2014), no. 5&6, 439–453.
https://doi.org/10.26421/QIC14.5-6
arXiv:arXiv:1210.1148

[2] Joran van Apeldoorn and András Gilyén, Improvements in quantum SDP-solving with applications, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 99:1–99:15, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.
https://doi.org/10.4230/LIPIcs.ICALP.2019.99
arXiv:arXiv:1804.05058

[3] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, Quantum SDP-solvers: Better upper and lower bounds, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, 2017.
https://doi.org/10.1109/FOCS.2017.44
arXiv:arXiv:1705.01843

[4] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, Convex optimization using quantum oracles, Quantum, 2019.
arXiv:arXiv:1809.00643

[5] Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, 2004.

[6] Fernando G.S.L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 27:1–27:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.
https://doi.org/10.4230/LIPIcs.ICALP.2019.27
arXiv:arXiv:1710.02581v2

[7] Fernando G.S.L. Brandão and Krysta Svore, Quantum speed-ups for solving semidefinite programs, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415–426, 2017.
https://doi.org/10.1109/FOCS.2017.45
arXiv:arXiv:1609.05537

[8] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305 (2002), 53–74.
arXiv:arXiv:quant-ph/0005055

[9] Andrew M. Childs, Robin Kothari, and Rolando D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM Journal on Computing 46 (2017), no. 6, 1920–1950.
https://doi.org/10.1137/16M1087072
arXiv:arXiv:1511.02306

[10] George B. Dantzig and Mukund N. Thapa, Linear programming 2: Theory and extensions, Springer, 2006.

[11] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1425–1444, Society for Industrial and Applied Mathematics, 2019.
https://doi.org/10.1137/1.9781611975482.87
arXiv:arXiv:1711.00465

[12] Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2, Springer, 2012.

[13] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103 (2009), no. 15, 150502.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:arXiv:0811.3171

[14] Lars Hörmander, The analysis of linear partial differential operators: Distribution theory and Fourier analysis, Springer-Verlag, 1990.

[15] Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005), no. 5, 050501.
https://doi.org/10.1103/PhysRevLett.95.050501
arXiv:arXiv:quant-ph/0405146

[16] Adam T. Kalai and Santosh Vempala, Simulated annealing for convex optimization, Mathematics of Operations Research 31 (2006), no. 2, 253–266.
https://doi.org/10.1287/moor.1060.0194

[17] Narendra Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 302–311, 1984.
https://doi.org/10.1145/800057.808695

[18] James E. Kelley, Jr., The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics 8 (1960), no. 4, 703–712.
https://doi.org/10.1137/0108053

[19] Iordanis Kerenidis and Anupam Prakash, Quantum gradient descent for linear systems and least squares, 2017.
arXiv:arXiv:1704.04992

[20] Yin Tat Lee, personal communication, 2018.

[21] Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala, Efficient convex optimization with membership oracles, Proceedings of the 31st Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 75, pp. 1292–1294, 2018.
arXiv:arXiv:1706.07357

[22] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong, A faster cutting plane method and its implications for combinatorial and convex optimization, Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1049–1065, 2015.
https://doi.org/10.1109/FOCS.2015.68
arXiv:arXiv:1508.04874

[23] László Lovász and Santosh Vempala, Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 57–68, 2006.
https://doi.org/10.1109/FOCS.2006.28

[24] Arkadi S. Nemirovski, Information-based complexity of convex programming, lecture notes, 1995.

[25] Arkadi S. Nemirovski and David B. Yudin, Problem complexity and method efficiency in optimization, Wiley, 1983.

[26] Yurii Nesterov, Introductory lectures on convex optimization: A basic course, Applied Optimization, vol. 87, Springer, 2013.

[27] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, Quantum gradient descent and Newton's method for constrained polynomial optimization, New Journal of Physics 21 (2019), no. 7, 073023, IOP Publishing.
https://doi.org/10.1088/1367-2630/ab2a9e
arXiv:arXiv:1612.01789

[28] Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 338–343, 1989.
https://doi.org/10.1109/SFCS.1989.63500

Cited by

[1] Kiran Adhikari, Christian Deppe, Aman Ganeju, Iva Kumari Lamichhane, Rohit Bhattarai, Manghang Limbu, and Nishma Bhattarai, Lecture Notes in Computer Science 14620, 460 (2025) ISBN:978-3-031-82013-7.

[2] Yizhou Liu, Weijie J. Su, and Tongyang Li, "On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks", Quantum 7, 1030 (2023).

[3] Edric Matwiejew, Jason Pye, and Jingbo B Wang, "Quantum optimisation for continuous multivariable functions by a structured search", Quantum Science and Technology 8 4, 045013 (2023).

[4] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).

[5] Benjamin C B Symons, David Galvin, Emre Sahin, Vassil Alexandrov, and Stefano Mensa, "A practitioner’s guide to quantum algorithms for optimisation problems", Journal of Physics A: Mathematical and Theoretical 56 45, 453001 (2023).

[6] Abraham Itzhak Weinberg, "Quantum-accelerated security analysis in quantum cryptography: semidefinite programming (SDP) from classical bottlenecks to quantum solutions — a comprehensive review", Quantum Machine Intelligence 8 2, 90 (2026).

[7] Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, and Miklos Santha, "Quantum algorithms for hedging and the learning of Ising models", Physical Review A 103 1, 012418 (2021).

[8] Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li, "Quantum algorithm for online convex optimization", Quantum Science and Technology 7 2, 025022 (2022).

[9] Simon Apers and Sander Gribling, "Quantum Speedups for Linear Programming via Interior Point Methods", SIAM Journal on Computing 55 1, 93 (2026).

[10] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", Quantum 5, 529 (2021).

[11] Kishor Bharti, Tobias Haug, Vlatko Vedral, and Leong-Chuan Kwek, "Noisy intermediate-scale quantum algorithm for semidefinite programming", Physical Review A 105 5, 052445 (2022).

[12] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, "Quantum SDP-Solvers: Better upper and lower bounds", Quantum 4, 230 (2020).

[13] Giacomo Nannicini, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

[14] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[15] Yuxin Zhang and Changpeng Shao, "Quantum spectral method for gradient and Hessian estimation", Journal of Computer and System Sciences 160, 103812 (2026).

[16] Abhishek, Pankaj Bhatt, Mirza Naziah Baig, R. Sridevi, and Bramah Hazela, Advances in Medical Technologies and Clinical Practice 169 (2024) ISBN:9798369332122.

[17] Penghui Yao and Zekun Ye, "On the exact quantum query complexity of MOD and EXACT functions", Frontiers of Computer Science 19 4, 194901 (2025).

[18] Wen Guan, Gabriel Perdue, Arthur Pesah, Maria Schuld, Koji Terashi, Sofia Vallecorsa, and Jean-Roch Vlimant, "Quantum machine learning in high energy physics", Machine Learning: Science and Technology 2 1, 011003 (2021).

[19] Nikitas Stamatopoulos, Guglielmo Mazzola, Stefan Woerner, and William J. Zeng, "Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms", Quantum 6, 770 (2022).

[20] Xin Wang, Zhixin Song, and Youle Wang, "Variational Quantum Singular Value Decomposition", Quantum 5, 483 (2021).

[21] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[22] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, "Quantum Algorithm for Estimating Volumes of Convex Bodies", ACM Transactions on Quantum Computing 4 3, 1 (2023).

[23] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", INFORMS Journal on Computing 35 2, 266 (2023).

[24] Zherui Chen, Yuchen Lu, Hao Wang, Yizhou Liu, and Tongyang Li, "Quantum Langevin Dynamics for Optimization", Communications in Mathematical Physics 406 3, 52 (2025).

[25] Hristo Venev, Thien Udomsrirungruang, Dimitar Dimitrov, Timon Gehr, and Martin Vechev, "qblaze: An Efficient and Scalable Sparse Quantum Simulator", Proceedings of the ACM on Programming Languages 9 OOPSLA2, 444 (2025).

[26] Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang, "Quantum simulation of real-space dynamics", Quantum 6, 860 (2022).

[27] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao, "Quantum-inspired algorithm for general minimum conical hull problems", Physical Review Research 2 3, 033199 (2020).

[28] Alejandro Giraldo-Quintero, Daniel Sierra-Sosa, Ibrahim Imam, and Adel S. Elmaghraby, "Quantum Computing Optimization: An Introduction", IEEE Access 14, 63363 (2026).

[29] Sandeep Kumar Sood, Manmohan Singh, and Munish Bhatia, "Extraction of emerging trends in quantum algorithm archives", Neural Computing and Applications 36 29, 17851 (2024).

[30] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Víctor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal, "Challenges and opportunities in quantum optimization", Nature Reviews Physics 6 12, 718 (2024).

[31] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[32] Patrick Rebentrost and Seth Lloyd, "Quantum computational finance: quantum algorithm for portfolio optimization", arXiv:1811.03975, (2018).

[33] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost, "Near-term quantum algorithms for linear systems of equations with regression loss functions", New Journal of Physics 23 11, 113021 (2021).

[34] Yuexin Su, Ziyi Yang, Peiyuan Huang, Tongyang Li, and Yinyu Ye, "Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities", arXiv:2507.04438, (2025).

[35] Aram W. Harrow, "Small quantum computers and large classical data sets", arXiv:2004.00026, (2020).

[36] Xiwen Tao, Chenyi Zhang, Helin Wang, Yexin Zhang, and Tongyang Li, "Gradient Testing and Estimation by Comparisons", arXiv:2405.11454, (2024).

[37] P. A. M. Casares and M. A. Martin-Delgado, "A quantum interior-point predictor─corrector algorithm for linear programming", Journal of Physics A Mathematical General 53 44, 445305 (2020).

[38] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, "Convex optimization using quantum oracles", Quantum 4, 220 (2020).

[39] Annie Marsden, Liam O'Carroll, Aaron Sidford, and Chenyi Zhang, "Isotropic Noise in Stochastic and Quantum Convex Optimization", arXiv:2510.20745, (2025).

[40] Yanlin Chen and Ronald de Wolf, "Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints", arXiv:2110.13086, (2021).

[41] Jiaqi Leng, Kewen Wu, Xiaodi Wu, and Yufan Zheng, "(Sub)Exponential Quantum Speedup for Optimization", arXiv:2504.14841, (2025).

[42] Benjamin A. Cordier, Nicolas P. D. Sawaya, Gian G. Guerreschi, and Shannon K. McWeeney, "Biology and medicine in the landscape of quantum advantages", arXiv:2112.00760, (2021).

[43] Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and Miklos Santha, "Quantum and Classical Algorithms for Approximate Submodular Function Minimization", arXiv:1907.05378, (2019).

[44] Aaron Sidford and Chenyi Zhang, "Quantum speedups for stochastic optimization", arXiv:2308.01582, (2023).

[45] Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, and Tongyang Li, "Quantum Algorithms and Lower Bounds for Finite-Sum Optimization", arXiv:2406.03006, (2024).

[46] Weiyuan Gong, Chenyi Zhang, and Tongyang Li, "Robustness of Quantum Algorithms for Nonconvex Optimization", arXiv:2212.02548, (2022).

[47] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost, "Near-term quantum algorithms for linear systems of equations", arXiv:1909.07344, (2019).

[48] Penghui Yao and Zekun Ye, "On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$", arXiv:2303.10935, (2023).

[49] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, "Quantum algorithm for estimating volumes of convex bodies", arXiv:1908.03903, (2019).

[50] Chenyi Zhang and Tongyang Li, "Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions", arXiv:2212.03906, (2022).

[51] Zexian Li, Guofeng Zhang, and Xiao-Ming Zhang, "Reducing C-NOT Counts for State Preparation and Block Encoding via Diagonal Matrix Migration", arXiv:2603.16492, (2026).

[52] Andrew M. Childs, Shih-Han Hung, and Tongyang Li, "Quantum query complexity with matrix-vector products", arXiv:2102.11349, (2021).

[53] Cezar-Mihail Alexandru, Ella Bridgett-Tomkinson, Noah Linden, Joseph MacManus, Ashley Montanaro, and Hannah Morris, "Quantum speedups of some general-purpose numerical optimisation algorithms", Quantum Science and Technology 5 4, 045014 (2020).

[54] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", arXiv:2504.05624, (2025).

[55] Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang, "Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants", arXiv:2210.06539, (2022).

[56] Tongyang Li and Ruizhe Zhang, "Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits", arXiv:2209.12897, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2026-09-08 16:27:15) and SAO/NASA ADS (last updated successfully 2026-09-08 16:27:18). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.