Quantum algorithms and lower bounds for convex optimization
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
► BibTeX data
► 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] 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).
[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] 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).
[5] 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).
[6] Xin Wang, Zhixin Song, and Youle Wang, "Variational Quantum Singular Value Decomposition", Quantum 5, 483 (2021).
[7] Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li, "Quantum algorithm for online convex optimization", Quantum Science and Technology 7 2, 025022 (2022).
[8] 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).
[9] 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).
[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] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", INFORMS Journal on Computing 35 2, 266 (2023).
[13] 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).
[14] Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang, "Quantum simulation of real-space dynamics", Quantum 6, 860 (2022).
[15] 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).
[16] Patrick Rebentrost and Seth Lloyd, "Quantum computational finance: quantum algorithm for portfolio optimization", arXiv:1811.03975, (2018).
[17] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost, "Near-term quantum algorithms for linear systems of equations", arXiv:1909.07344, (2019).
[18] Aram W. Harrow, "Small quantum computers and large classical data sets", arXiv:2004.00026, (2020).
[19] 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).
[20] 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).
[21] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, "Quantum SDP-Solvers: Better upper and lower bounds", arXiv:1705.01843, (2017).
[22] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, "Convex optimization using quantum oracles", arXiv:1809.00643, (2018).
[23] Yanlin Chen and Ronald de Wolf, "Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints", arXiv:2110.13086, (2021).
[24] 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).
[25] Chenyi Zhang and Tongyang Li, "Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions", arXiv:2212.03906, (2022).
[26] Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and Miklos Santha, "Quantum and Classical Algorithms for Approximate Submodular Function Minimization", arXiv:1907.05378, (2019).
[27] 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).
[28] 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).
[29] 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).
[30] Tongyang Li and Ruizhe Zhang, "Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits", arXiv:2209.12897, (2022).
[31] Andrew M. Childs, Shih-Han Hung, and Tongyang Li, "Quantum query complexity with matrix-vector products", arXiv:2102.11349, (2021).
[32] Weiyuan Gong, Chenyi Zhang, and Tongyang Li, "Robustness of Quantum Algorithms for Nonconvex Optimization", arXiv:2212.02548, (2022).
[33] Aaron Sidford and Chenyi Zhang, "Quantum speedups for stochastic optimization", arXiv:2308.01582, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 21:33:07) and SAO/NASA ADS (last updated successfully 2023-09-21 21:33:08). 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.