Convex optimization using quantum oracles
1QuSoft, CWI, Amsterdam, the Netherlands
2University of Amsterdam, Amsterdam, the Netherlands
| Published: | 2020-01-13, volume 4, page 220 |
| Eprint: | arXiv:1809.00643v4 |
| Doi: | https://doi.org/10.22331/q-2020-01-13-220 |
| Citation: | Quantum 4, 220 (2020). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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.
Popular summary
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.
► BibTeX data
► 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", Quantum 4, 221 (2020).
[2] Benjamin A. Cordier, Nicolas P. D. Sawaya, Gian Giacomo Guerreschi, and Shannon K. McWeeney, "Biology and medicine in the landscape of quantum advantages", Journal of The Royal Society Interface 19 196, 20220541 (2022).
[3] Grégoire H. Cattan and Alexandre Quemy, "Case-Based and Quantum Classification for ERP-Based Brain–Computer Interfaces", Brain Sciences 13 2, 303 (2023).
[4] 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).
[5] Xin Wang, Zhixin Song, and Youle Wang, "Variational Quantum Singular Value Decomposition", Quantum 5, 483 (2021).
[6] Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li, "Quantum algorithm for online convex optimization", Quantum Science and Technology 7 2, 025022 (2022).
[7] 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).
[8] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", Quantum 5, 529 (2021).
[9] 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).
[10] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", INFORMS Journal on Computing 35 2, 266 (2023).
[11] 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).
[12] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain, "Quantum Computing for Finance: State-of-the-Art and Future Prospects", IEEE Transactions on Quantum Engineering 1, 1 (2020).
[13] Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang, "Quantum simulation of real-space dynamics", Quantum 6, 860 (2022).
[14] Sayonsom Chanda, Manish Mohanpurkar, and Rob Hovsapian, 2023 13th International Symposium on Advanced Topics in Electrical Engineering (ATEE) 1 (2023) ISBN:979-8-3503-3193-6.
[15] Patrick Rebentrost and Seth Lloyd, "Quantum computational finance: quantum algorithm for portfolio optimization", arXiv:1811.03975, (2018).
[16] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost, "Near-term quantum algorithms for linear systems of equations", arXiv:1909.07344, (2019).
[17] Aram W. Harrow, "Small quantum computers and large classical data sets", arXiv:2004.00026, (2020).
[18] 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).
[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] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, "Quantum algorithms and lower bounds for convex optimization", arXiv:1809.01731, (2018).
[21] Yanlin Chen and Ronald de Wolf, "Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints", arXiv:2110.13086, (2021).
[22] 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).
[23] 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).
[24] Tongyang Li and Ruizhe Zhang, "Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits", arXiv:2209.12897, (2022).
[25] Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and Miklos Santha, "Quantum and Classical Algorithms for Approximate Submodular Function Minimization", arXiv:1907.05378, (2019).
[26] 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).
[27] 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, (2020).
[28] Chenyi Zhang and Tongyang Li, "Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions", arXiv:2212.03906, (2022).
[29] Ammar Daskin, "The quantum version of the shifted power method and its application in quadratic binary optimization", arXiv:1809.01378, (2018).
[30] Joran van Apeldoorn and Sander Gribling, "Simon's problem for linear functions", arXiv:1810.12030, (2018).
[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).
The above citations are from Crossref's cited-by service (last updated successfully 2023-05-29 15:25:36) and SAO/NASA ADS (last updated successfully 2023-05-29 15:25:37). 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.
Pingback: Ronald de Wolf | WaveMaker