{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T08:46:27Z","timestamp":1770453987054,"version":"3.49.0"},"reference-count":28,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T00:00:00Z","timestamp":1578873600000},"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>While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-dimensional convex body using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mover><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">~<\/mml:mo><\/mml:mover><\/mml:mrow><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mover><mml:mi mathvariant=\"normal\">\u03a9<\/mml:mi><mml:mo stretchy=\"false\">~<\/mml:mo><\/mml:mover><\/mml:mrow><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msqrt><mml:mi>n<\/mml:mi><\/mml:msqrt><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> evaluation queries and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a9<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msqrt><mml:mi>n<\/mml:mi><\/mml:msqrt><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> membership queries.<\/jats:p>","DOI":"10.22331\/q-2020-01-13-221","type":"journal-article","created":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T14:45:53Z","timestamp":1578926753000},"page":"221","source":"Crossref","is-referenced-by-count":27,"title":["Quantum algorithms and lower bounds for convex optimization"],"prefix":"10.22331","volume":"4","author":[{"given":"Shouvanik","family":"Chakrabarti","sequence":"first","affiliation":[{"name":"Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland"}]},{"given":"Andrew M.","family":"Childs","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland"}]},{"given":"Tongyang","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland"}]},{"given":"Xiaodi","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science, University of Maryland"}]}],"member":"9598","published-online":{"date-parts":[[2020,1,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Andris Ambainis and Ashley Montanaro, Quantum algorithms for search with wildcards and combinatorial group testing, Quantum Information and Computation 14 (2014), no. 5&6, 439-453.","DOI":"10.26421\/QIC14.5-6"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n, Improvements in quantum SDP-solving with applications, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 99:1-99:15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"2","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, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, 2017.","DOI":"10.1109\/FOCS.2017.44"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Joran van Apeldoorn, Andr\u00e1s Gily\u00e9n, Sander Gribling, and Ronald de Wolf, Convex optimization using quantum oracles, Quantum, 2019.","DOI":"10.22331\/q-2020-01-13-220"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"5","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, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 27:1-27:14, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o and Krysta Svore, Quantum speed-ups for solving semidefinite programs, Proceedings of the 58th Annual Symposium on Foundations of Computer Science, pp. 415-426, 2017.","DOI":"10.1109\/FOCS.2017.45"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Gilles Brassard, Peter H\u00f8yer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305 (2002), 53-74.","DOI":"10.1090\/conm\/305\/05215"},{"key":"8","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 (2017), no. 6, 1920-1950.","DOI":"10.1137\/16M1087072"},{"key":"9","unstructured":"George B. Dantzig and Mukund N. Thapa, Linear programming 2: Theory and extensions, Springer, 2006."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Srinivasan Arunachalam, and Nathan Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1425-1444, Society for Industrial and Applied Mathematics, 2019.","DOI":"10.1137\/1.9781611975482.87"},{"key":"11","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2, Springer, 2012."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, Quantum algorithm for linear systems of equations, Physical Review Letters 103 (2009), no. 15, 150502.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"13","unstructured":"Lars H\u00f6rmander, The analysis of linear partial differential operators: Distribution theory and Fourier analysis, Springer-Verlag, 1990."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005), no. 5, 050501.","DOI":"10.1103\/PhysRevLett.95.050501"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Adam T. Kalai and Santosh Vempala, Simulated annealing for convex optimization, Mathematics of Operations Research 31 (2006), no. 2, 253-266.","DOI":"10.1287\/moor.1060.0194"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Narendra Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 302-311, 1984.","DOI":"10.1145\/800057.808695"},{"key":"17","doi-asserted-by":"publisher","unstructured":"James E. Kelley, Jr., The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics 8 (1960), no. 4, 703-712.","DOI":"10.1137\/0108053"},{"key":"18","unstructured":"Iordanis Kerenidis and Anupam Prakash, Quantum gradient descent for linear systems and least squares, 2017."},{"key":"19","unstructured":"Yin Tat Lee, personal communication, 2018."},{"key":"20","unstructured":"Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala, Efficient convex optimization with membership oracles, Proceedings of the 31st Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 75, pp. 1292-1294, 2018."},{"key":"21","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, Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp. 1049-1065, 2015.","DOI":"10.1109\/FOCS.2015.68"},{"key":"22","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Santosh Vempala, Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 57-68, 2006.","DOI":"10.1109\/FOCS.2006.28"},{"key":"23","unstructured":"Arkadi S. Nemirovski, Information-based complexity of convex programming, lecture notes, 1995."},{"key":"24","unstructured":"Arkadi S. Nemirovski and David B. Yudin, Problem complexity and method efficiency in optimization, Wiley, 1983."},{"key":"25","unstructured":"Yurii Nesterov, Introductory lectures on convex optimization: A basic course, Applied Optimization, vol. 87, Springer, 2013."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, Quantum gradient descent and Newton's method for constrained polynomial optimization, New Journal of Physics 21 (2019), no. 7, 073023, IOP Publishing.","DOI":"10.1088\/1367-2630\/ab2a9e"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 338-343, 1989.","DOI":"10.1109\/SFCS.1989.63500"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-01-13-221\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T14:45:57Z","timestamp":1578926757000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-01-13-221\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,13]]},"references-count":28,"URL":"https:\/\/doi.org\/10.22331\/q-2020-01-13-221","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,13]]},"article-number":"221"}}