1QuSoft, Amsterdam, the Netherlands.
2University of Amsterdam, the Netherlands.
3University of Amsterdam, the Netherlands.
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Brandão and Svore [14] recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension $n$ of the problem and the number $m$ of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.
We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with $mn$ when $mapprox n$, which is the same as classical.
Popular summary
► BibTeX data
► References
[1] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. toc, 8(6):121–164, 2012.
https://doi.org/10.4086/toc.2012.v008a006
[2] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. jacm, 63(2):12:1–12:35, 2016. Earlier version in STOC’07.
https://doi.org/10.1145/2837020
[3] Andris Ambainis. Quantum walk algorithm for element distinctness. siamjc, 37(1):210–239, 2007. Earlier version in FOCS’04. arXiv: quant-ph/0311001?.
https://doi.org/10.1137/S0097539705447311
arXiv:quant-ph/0311001
[4] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In icalp46th, pages 99:1–99:15, 2019. arXiv: 1804.05058?.
https://doi.org/10.4230/LIPIcs.ICALP.2019.99
arXiv:1804.05058
[5] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. arXiv: 1904.03180?, 2019.
arXiv:1904.03180
[6] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In focs58th, pages 403–414, 2017. arXiv: 1705.01843?.
https://doi.org/10.1109/FOCS.2017.44
arXiv:1705.01843
[7] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. quantum, 4:220, 2020. arXiv: 1809.00643?.
https://doi.org/10.22331/q-2020-01-13-220
arXiv:1809.00643
[8] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008.
https://doi.org/10.1002/0471722154
[9] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/9605034?.
arXiv:quant-ph/9605034
[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. prl, 114(9):090502, 2015. arXiv: 1412.4687?.
https://doi.org/10.1103/PhysRevLett.114.090502
arXiv:1412.4687
[11] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In focs56th, pages 792–809, 2015. arXiv: 1501.01715?.
https://doi.org/10.1109/FOCS.2015.54
arXiv:1501.01715
[12] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53–74. AMS, 2002. arXiv: quant-ph/0005055?.
https://doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055
[13] 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 icalp46th, pages 27:1–27:14, 2019. arXiv: 1710.02581?.
https://doi.org/10.4230/LIPIcs.ICALP.2019.27
arXiv:1710.02581
[14] Fernando G. S. L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In focs58th, pages 415–426, 2017. arXiv: 1609.05537?.
https://doi.org/10.1109/FOCS.2017.45
arXiv:1609.05537
[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. quantum, 4:221, 2020. arXiv: 1809.01731?.
https://doi.org/10.22331/q-2020-01-13-221
arXiv:1809.01731
[16] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. rspa, 454(1969):339–354, 1998. arXiv: quant-ph/9708016?.
https://doi.org/10.1098/rspa.1998.0164
arXiv:quant-ph/9708016
[17] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. siamjc, 46(6):1920–1950, 2017. arXiv: 1511.02306?.
https://doi.org/10.1137/16M1087072
arXiv:1511.02306
[18] Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. qic, 17(1&2):41–64, 2017. arXiv: 1603.02940?.
https://doi.org/10.26421/QIC17.1-2
arXiv:1603.02940
[19] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. qic, 12(11&12):901–924, 2012. arXiv: 1202.5822?.
https://doi.org/10.26421/QIC12.11-12
arXiv:1202.5822
[20] George B. Dantzig. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, pages 339
–347. John Wiley & Sons Inc., New York, N. Y., 1951.
[21] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv: quant-ph/9607014?, 1996.
arXiv:quant-ph/9607014
[22] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. siamjc, 35(6):1310–1328, 2006. Earlier version in ICALP’04. arXiv: quant-ph/0401091?.
https://doi.org/10.1137/050644719
arXiv:quant-ph/0401091
[23] Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. comb, 1(2):169–197, 1981.
https://doi.org/10.1007/BF02579273
[24] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.
[25] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv: quant-ph/0208112?, 2002.
arXiv:quant-ph/0208112
[26] Lov K. Grover. A fast quantum mechanical algorithm for database search. In stoc28th, pages 212–219, 1996. arXiv: quant-ph/9605043?.
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043
[27] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In stoc51st, pages 193–204, 2019. arXiv: 1806.01838?.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838
[28] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. jacm, 42(6):1115–1145, 1995. Earlier version in STOC’94.
https://doi.org/10.1145/227683.227684
[29] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. prl, 103(15):150502, 2009. arXiv: 0811.3171?.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171
[30] Shelby Kimmel. Quantum adversary (upper) bound. cjtcs, 2013:4:1–14, 2013. Earlier version in ICALP’12. arXiv: 1101.0797?.
https://doi.org/10.4086/cjtcs.2013.004
arXiv:1101.0797
[31] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? siamjc, 37(1):319–357, 2007. Earlier version in FOCS’04.
https://doi.org/10.1137/S0097539705447372
[32] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. arXiv: 1808.09266?, 2018.
arXiv:1808.09266
[33] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. prl, 118(1):010501, 2017. arXiv: 1606.02685?.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685
[34] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. quantum, 3:163, 2019. arXiv: 1610.06546?.
https://doi.org/10.22331/q-2019-07-12-163
arXiv:1610.06546
[35] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In focs56th, pages 1049–1065, 2015. arXiv: 1508.04874?.
https://doi.org/10.1109/FOCS.2015.68
arXiv:1508.04874
[36] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.
https://doi.org/10.1017/CBO9780511976667
[37] Y. Nesterov and A. Nemirovski. Interior-point polynomial algorithms in convex programming, volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), 1994.
https://doi.org/10.1137/1.9781611970791
[38] David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. prl, 102(13):130503, 2009. arXiv: 0809.2705?.
https://doi.org/10.1103/PhysRevLett.102.130503
arXiv:0809.2705
[39] David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. prl, 103(22):220502, 2009. arXiv: 0905.2199?.
https://doi.org/10.1103/PhysRevLett.103.220502
arXiv:0905.2199
[40] James Renegar. “Efficient” subgradient methods for general convex optimization. siamjc, 26(4):2649–2676, 2016. arXiv: 1605.08712?.
https://doi.org/10.1137/15M1027371
arXiv:1605.08712
[41] James Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Programming, 173(1):1–35, 2019. arXiv: 1512.07569?.
https://doi.org/10.1007/s10107-017-1203-y
arXiv:1512.07569
[42] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA, 1986.
[43] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. siamjc, 26(5):1484–1509, 1997. Earlier version in FOCS’94. arXiv: quant-ph/9508027?.
https://doi.org/10.1137/S0097539795293172
arXiv:quant-ph/9508027
[44] Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. Earlier version in NIPS’04.
http://jmlr.csail.mit.edu/papers/volume6/tsuda05a/tsuda05a.pdf
[45] Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning, 87(1):1–32, 2012. Earlier version in COLT’06.
https://doi.org/10.1007/s10994-011-5269-0
Cited by
[1] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, “Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics”, arXiv:1806.01838.
[2] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig, “Quantum machine learning: a classical perspective”, Proceedings of the Royal Society of London Series A 474 2209, 20170551 (2018).
[3] Patrick Rebentrost and Seth Lloyd, “Quantum computational finance: quantum algorithm for portfolio optimization”, arXiv:1811.03975.
[4] Joran van Apeldoorn and András Gilyén, “Quantum algorithms for zero-sum games”, arXiv:1904.03180.
[5] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, “Optimizing quantum optimization algorithms via faster quantum gradient computation”, arXiv:1711.00465.
[6] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, “Quantum gradient descent and Newton’s method for constrained polynomial optimization”, arXiv:1612.01789.
[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”, arXiv:1710.02581.
[8] Joran van Apeldoorn and András Gilyén, “Improvements in Quantum SDP-Solving with Applications”, arXiv:1804.05058.
[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang, “Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches”, arXiv:1901.03254.
[10] Simon Apers, “Quantum Walk Sampling by Growing Seed Sets”, arXiv:1904.11446.
[11] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, “Convex optimization using quantum oracles”, arXiv:1809.00643.
[12] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, “Quantum algorithms and lower bounds for convex optimization”, arXiv:1809.01731.
[13] Yimin Ge, Jordi Tura, and J. Ignacio Cirac, “Faster ground state preparation and high-precision ground energy estimation with fewer qubits”, arXiv:1712.03193.
[14] Ivan Bardet and Cambyse Rouzé, “Hypercontractivity and logarithmic Sobolev Inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates”, arXiv:1803.05379.
[15] Ashley Montanaro, “Quantum speedup of branch-and-bound algorithms”, arXiv:1906.10375.
[16] Johannes Bausch, Sathyawageeswar Subramanian, and Stephen Piddock, “A Quantum Search Decoder for Natural Language Processing”, arXiv:1909.05023.
The above citations are from SAO/NASA ADS (last updated successfully 2020-02-14 09:28:14). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2020-02-14 09:28:13: Could not fetch cited-by data for 10.22331/q-2020-02-14-230 from Crossref. This is normal if the DOI was registered recently.
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-02-14-230/
