1QuSoft, CWI, Amsterdam, the Netherlands
2University of Amsterdam, Amsterdam, the Netherlands
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
► 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.
a
rXiv: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] Patrick Rebentrost and Seth Lloyd, “Quantum computational finance: quantum algorithm for portfolio optimization”, arXiv:1811.03975.
[3] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, “Quantum SDP-Solvers: Better upper and lower bounds”, arXiv:1705.01843.
[4] Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and Miklos Santha, “Quantum and Classical Algorithms for Approximate Submodular Function Minimization”, arXiv:1907.05378.
[5] Joran van Apeldoorn and Sander Gribling, “Simon’s problem for linear functions”, arXiv:1810.12030.
[6] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost, “Near-term quantum algorithms for linear systems of equations”, arXiv:1909.07344.
[7] Ammar Daskin, “The quantum version of the shifted power method and its application in quadratic binary optimization”, arXiv:1809.01378.
[8] 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.
The above citations are from Crossref’s cited-by service (last updated successfully 2020-01-22 13:52:21) and SAO/NASA ADS (last updated successfully 2020-01-22 13:52:22). 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.
Source: https://quantum-journal.org/papers/q-2020-01-13-220/
