{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T04:28:48Z","timestamp":1781584128638,"version":"3.54.5"},"reference-count":45,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Brand\u00e3o and Svore \\cite{brandao2016QSDPSpeedup} 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> of the problem and the number <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><\/mml:math> 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:math> when <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><mml:mo>\u2248<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:math>, which is the same as classical.<\/jats:p>","DOI":"10.22331\/q-2020-02-14-230","type":"journal-article","created":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T09:28:56Z","timestamp":1581672536000},"page":"230","source":"Crossref","is-referenced-by-count":73,"title":["Quantum SDP-Solvers: Better upper and lower bounds"],"prefix":"10.22331","volume":"4","author":[{"given":"Joran","family":"van Apeldoorn","sequence":"first","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e1s","family":"Gily\u00e9n","sequence":"additional","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sander","family":"Gribling","sequence":"additional","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"QuSoft, CWI and University of Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2020,2,14]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing , 8(6):121\u2013164, 2012.","DOI":"10.4086\/toc.2012.v008a006"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM , 63(2):12:1\u201312:35, 2016. Earlier version in STOC'07.","DOI":"10.1145\/2837020"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing , 37(1):210\u2013239, 2007. Earlier version in FOCS'04. arXiv: quant-ph\/0311001.","DOI":"10.1137\/S0097539705447311"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 99:1\u201399:15, 2019. arXiv: 1804.05058.","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"4","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n. Quantum algorithms for zero-sum games. arXiv: 1904.03180, 2019."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Andr\u00e1s Gily\u00e9n, 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\u2013414, 2017. arXiv: 1705.01843.","DOI":"10.1109\/FOCS.2017.44"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Andr\u00e1s Gily\u00e9n, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum , 4:220, 2020. arXiv: 1809.00643.","DOI":"10.22331\/q-2020-01-13-220"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008.","DOI":"10.1002\/0471722154"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Michel Boyer, Gilles Brassard, Peter H\u00f8yer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4\u20135):493\u2013505, 1998. arXiv: quant-ph\/9605034.","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters , 114(9):090502, 2015. arXiv: 1412.4687.","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 792\u2013809, 2015. arXiv: 1501.01715.","DOI":"10.1109\/FOCS.2015.54"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter H\u00f8yer, 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\u201374. AMS, 2002. arXiv: quant-ph\/0005055.","DOI":"10.1090\/conm\/305\/05215"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brand\u00e3o, 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\u201327:14, 2019. arXiv: 1710.02581.","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brand\u00e3o 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\u2013426, 2017. arXiv: 1609.05537.","DOI":"10.1109\/FOCS.2017.45"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2020-01-13-221"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society A , 454(1969):339\u2013354, 1998. arXiv: quant-ph\/9708016.","DOI":"10.1098\/rspa.1998.0164"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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(6):1920\u20131950, 2017. arXiv: 1511.02306.","DOI":"10.1137\/16M1087072"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quantum Information and Computation , 17(1&2):41\u201364, 2017. arXiv: 1603.02940.","DOI":"10.26421\/QIC17.1-2"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation , 12(11&12):901\u2013924, 2012. arXiv: 1202.5822.","DOI":"10.26421\/QIC12.11-12"},{"key":"19","unstructured":"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\u2013347. John Wiley & Sons Inc., New York, N. Y., 1951."},{"key":"20","unstructured":"Christoph D\u00fcrr and Peter H\u00f8yer. A quantum algorithm for finding the minimum. arXiv: quant-ph\/9607014, 1996."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Christoph D\u00fcrr, Mark Heiligman, Peter H\u00f8yer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing , 35(6):1310\u20131328, 2006. Earlier version in ICALP'04. arXiv: quant-ph\/0401091.","DOI":"10.1137\/050644719"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica , 1(2):169\u2013197, 1981.","DOI":"10.1007\/BF02579273"},{"key":"23","doi-asserted-by":"crossref","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"24","unstructured":"Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv: quant-ph\/0208112, 2002."},{"key":"25","doi-asserted-by":"publisher","unstructured":"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\u2013219, 1996. arXiv: quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC) , pages 193\u2013204, 2019. arXiv: 1806.01838.","DOI":"10.1145\/3313276.3316366"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM , 42(6):1115\u20131145, 1995. Earlier version in STOC'94.","DOI":"10.1145\/227683.227684"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters , 103(15):150502, 2009. arXiv: 0811.3171.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Shelby Kimmel. Quantum adversary (upper) bound. Chicago Journal of Theoretical Computer Science , 2013:4:1\u201314, 2013. Earlier version in ICALP'12. arXiv: 1101.0797.","DOI":"10.4086\/cjtcs.2013.004"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O\u2019Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing , 37(1):319\u2013357, 2007. Earlier version in FOCS'04.","DOI":"10.1137\/S0097539705447372"},{"key":"31","unstructured":"Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. arXiv: 1808.09266, 2018."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters , 118(1):010501, 2017. arXiv: 1606.02685.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum , 3:163, 2019. arXiv: 1610.06546.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"34","doi-asserted-by":"publisher","unstructured":"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\u20131065, 2015. arXiv: 1508.04874.","DOI":"10.1109\/FOCS.2015.68"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.","DOI":"10.1017\/CBO9780511976667"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1137\/1.9781611970791"},{"key":"37","doi-asserted-by":"publisher","unstructured":"David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Physical Review Letters , 102(13):130503, 2009. arXiv: 0809.2705.","DOI":"10.1103\/PhysRevLett.102.130503"},{"key":"38","doi-asserted-by":"publisher","unstructured":"David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Physical Review Letters , 103(22):220502, 2009. arXiv: 0905.2199.","DOI":"10.1103\/PhysRevLett.103.220502"},{"key":"39","doi-asserted-by":"publisher","unstructured":"James Renegar. ``Efficient'' subgradient methods for general convex optimization. SIAM Journal on Computing , 26(4):2649\u20132676, 2016. arXiv: 1605.08712.","DOI":"10.1137\/15M1027371"},{"key":"40","doi-asserted-by":"publisher","unstructured":"James Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Programming, 173(1):1\u201335, 2019. arXiv: 1512.07569.","DOI":"10.1007\/s10107-017-1203-y"},{"key":"41","unstructured":"Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA, 1986."},{"key":"42","doi-asserted-by":"publisher","unstructured":"Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484\u20131509, 1997. Earlier version in FOCS'94. arXiv: quant-ph\/9508027.","DOI":"10.1137\/S0097539795293172"},{"key":"43","unstructured":"Koji Tsuda, Gunnar R\u00e4tsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995\u20131018, 2005. Earlier version in NIPS'04."},{"key":"44","doi-asserted-by":"publisher","unstructured":"Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning, 87(1):1\u201332, 2012. Earlier version in COLT'06.","DOI":"10.1007\/s10994-011-5269-0"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-02-14-230\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,15]],"date-time":"2020-02-15T05:43:41Z","timestamp":1581745421000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-02-14-230\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,14]]},"references-count":45,"URL":"https:\/\/doi.org\/10.22331\/q-2020-02-14-230","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,14]]},"article-number":"230"}}