Convex optimization using quantum oracles

Joran van Apeldoorn1, András Gilyén1, Sander Gribling1, and Ronald de Wolf1,2

1QuSoft, CWI, Amsterdam, the Netherlands
2University of Amsterdam, Amsterdam, the Netherlands

Abstract

We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using $\tilde{O}(1)$ quantum queries to a membership oracle, which is an exponential quantum speed-up over the $\Omega(n)$ membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that $\tilde{O}(n)$ quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: $\Omega(\sqrt{n})$ quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and $\Omega(n)$ quantum separation queries are needed if it does not.

Optimizing a function subject to various constraints is an important task, including practical problems like scheduling, energy minimization, learning neural networks, etc. In many cases the set K of points that satisfy the constraints is "convex", meaning that the line between any two points of K also lies in K. There can be different types of access to K: in some cases we can efficiently determine whether a given point lies in K ("membership queries"), in some cases we can efficiently find a hyperplane separating K from a given point outside of K, and in some cases we can efficiently optimize any well-behaved function over K. We study quantum algorithms that efficiently convert between different such types of access to K. Our work, along with an independent Quantum paper by Chakrabarti et al., gives a quantum algorithm that finds a separating hyperplane based on very few membership queries. This in turn leads to a quadratic quantum improvement in the number of membership queries needed for optimization, compared to the best known classical algorithm. Interestingly, our speed-up is based on the Fourier transform (Jordan's algorithm for computing gradients) rather than Grover search. We also prove that quantum algorithms can speed up the general problem of convex optimization only polynomially.

► References

[1] Andris Ambainis. A better lower bound for quantum algorithms searching an ordered list. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), pages 352–357, 1999.
https:/​/​doi.org/​10.1109/​SFFCS.1999.814606
arXiv:quant-ph/9902053

[2] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 99:1–99:15, 2019.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.99
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. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 403–414, 2017.
https:/​/​doi.org/​10.1109/​FOCS.2017.44
arXiv:1705.01843

[4] Andris Ambainis and Robert Špalek. Quantum algorithms for matching and network flows. In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 172–183, 2006.
https:/​/​doi.org/​10.1007/​11672142_13
arXiv:quant-ph/0508205

[5] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal onComputing, 26(5):1510–1523, 1997.
https:/​/​doi.org/​10.1137/​S0097539796300933
arXiv:quant-ph/9701001

[6] Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 883–897, 2018.
https:/​/​doi.org/​10.1109/​FOCS.2018.00088
arXiv:1804.04739

[7] 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. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 27:1–27:14, 2019.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.27
arXiv:1710.02581

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

[9] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3–4):231–357, 2015.
https:/​/​doi.org/​10.1561/​2200000050
arXiv:1405.4980

[10] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization , 2018.
arXiv:1809.01731

[11] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum , 1996.
arXiv:quant-ph/9607014

[12] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006.
https:/​/​doi.org/​10.1137/​050644719
arXiv:quant-ph/0401091

[13] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1425–1444, 2019.
https:/​/​doi.org/​10.1137/​1.9781611975482.87
arXiv:1711.00465

[14] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.

[15] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (STOC), pages 212–219, 1996.
https:/​/​doi.org/​10.1145/​237814.237866
arXiv:quant-ph/9605043

[16] Andreas Griewank and Andrea Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, second edition, 2008.
https:/​/​doi.org/​10.1137/​1.9780898717761

[17] Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the 39th ACM Symposium on the Theory of Computing (STOC), pages 526–535, 2007.
https:/​/​doi.org/​10.1145/​1250790.1250867
arXiv:quant-ph/0611054

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

[19] Stephen P. Jordan. Quantum Computation Beyond the Circuit Model. PhD thesis, Massachusetts Institute of Technology, 2008.
arXiv:0809.2307
http:/​/​web.mit.edu/​2.111/​www/​2010/​MIT-stephen-jordan-phd-thesis-may08.pdf

[20] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs , 2018.
arXiv:1808.09266

[21] Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala. Efficient convex optimization with membership oracles. In Proceedings of the 31st Conference On Learning Theory (COLT), pages 1292–1294, 2018.
arXiv:1706.07357
http:/​/​proceedings.mlr.press/​v75/​lee18a.html

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

[23] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[24] Márió Szegedy. Quantum speed-up of Markov chain based algorithms. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 32–41, 2004.
https:/​/​doi.org/​10.1109/​FOCS.2004.53
arXiv:quant-ph/0401053

[25] Andrew Chi-Chih Yao. On computing the minima of quadratic forms (preliminary report). In Proceedings of the 7th ACM Symposium on the Theory of Computing (STOC), pages 23–26, 1975.
https:/​/​doi.org/​10.1145/​800116.803749

Cited by

[1] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, "Quantum algorithms and lower bounds for convex optimization", arXiv:1809.01731, Quantum 4, 221 (2020).

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

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

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

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

[6] Joran van Apeldoorn and Sander Gribling, "Simon's problem for linear functions", arXiv:1810.12030.

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

[8] Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, and Miklos Santha, "Quantum algorithms for hedging and the learning of Ising models", arXiv:2002.06003.

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

[10] Ammar Daskin, "The quantum version of the shifted power method and its application in quadratic binary optimization", arXiv:1809.01378.

[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", Quantum Science and Technology 5 4, 045014 (2020).

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

[13] Kamil Wereszczyński, Agnieszka Michalczuk, Damian Pęszor, Marcin Paszkuta, Krzysztof Cyran, and Andrzej Polański, "Cosine series quantum sampling method with applications in signal and image processing", arXiv:2011.12738.

The above citations are from Crossref's cited-by service (last updated successfully 2021-01-26 03:05:40) and SAO/NASA ADS (last updated successfully 2021-01-26 03:05:42). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Convex optimization using quantum oracles”

1. Pingback: Ronald de Wolf | WaveMaker