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

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.

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

► 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] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, "Quantum SDP-Solvers: Better upper and lower bounds", arXiv:1705.01843, Quantum 4, 230 (2020).

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

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

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

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

[6] P. A. M. Casares and M. A. Martin-Delgado, "A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming", arXiv:1902.06749.

[7] Aram W. Harrow, "Small quantum computers and large classical data sets", arXiv:2004.00026.

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

[9] Yassine Hamoudi, Maharshi Ray, Patrick Rebentrost, Miklos Santha, Xin Wang, and Siyi Yang, "Quantum algorithms for hedging and the Sparsitron", arXiv:2002.06003.

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

[11] Cezar-Mihail Alexandru, Ella Bridgett-Tomkinson, Noah Linden, Joseph MacManus, Ashley Montanaro, and Hannah Morris, "Quantum speedups of some general-purpose numerical optimisation algorithms", arXiv:2004.06521.

[12] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum Algorithms for Escaping from Saddle Points", arXiv:2007.10253.

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