{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T09:45:33Z","timestamp":1777974333400,"version":"3.51.4"},"reference-count":25,"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>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 <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:mn>1<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> quantum queries to a membership oracle, which is an exponential quantum speed-up over the <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:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> 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 <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> 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: <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> quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, 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:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> quantum separation queries are needed if it does not.<\/jats:p>","DOI":"10.22331\/q-2020-01-13-220","type":"journal-article","created":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T08:50:17Z","timestamp":1578905417000},"page":"220","source":"Crossref","is-referenced-by-count":33,"title":["Convex optimization using quantum oracles"],"prefix":"10.22331","volume":"4","author":[{"given":"Joran","family":"van Apeldoorn","sequence":"first","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Gily\u00e9n","sequence":"additional","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sander","family":"Gribling","sequence":"additional","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"QuSoft, CWI, Amsterdam, the Netherlands"},{"name":"University of Amsterdam, Amsterdam, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,1,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/SFFCS.1999.814606"},{"key":"1","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-99:15, 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. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 403-414, 2017.","DOI":"10.1109\/FOCS.2017.44"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Andris Ambainis and Robert \u0160palek. Quantum algorithms for matching and network flows. In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 172-183, 2006.","DOI":"10.1007\/11672142_13"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal onComputing, 26(5):1510-1523, 1997.","DOI":"10.1137\/S0097539796300933"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Peter B\u00fcrgisser, 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.","DOI":"10.1109\/FOCS.2018.00088"},{"key":"6","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-27:14, 2019.","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"7","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-426, 2017.","DOI":"10.1109\/FOCS.2017.45"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S\u00e9bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357, 2015.","DOI":"10.1561\/2200000050"},{"key":"9","unstructured":"Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization , 2018."},{"key":"10","unstructured":"Christoph D\u00fcrr and Peter H\u00f8yer. A quantum algorithm for finding the minimum , 1996."},{"key":"11","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-1328, 2006.","DOI":"10.1137\/050644719"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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.","DOI":"10.1137\/1.9781611975482.87"},{"key":"13","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":"14","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-219, 1996.","DOI":"10.1145\/237814.237866"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Andreas Griewank and Andrea Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, second edition, 2008.","DOI":"10.1137\/1.9780898717761"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Peter H\u00f8yer, Troy Lee, and Robert \u0160palek. Negative weights make adversaries stronger. In Proceedings of the 39th ACM Symposium on the Theory of Computing (STOC), pages 526-535, 2007.","DOI":"10.1145\/1250790.1250867"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95(5):050501, 2005.","DOI":"10.1103\/PhysRevLett.95.050501"},{"key":"18","unstructured":"Stephen P. Jordan. Quantum Computation Beyond the Circuit Model. PhD thesis, Massachusetts Institute of Technology, 2008."},{"key":"19","unstructured":"Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs , 2018."},{"key":"20","unstructured":"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."},{"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. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1049-1065, 2015.","DOI":"10.1109\/FOCS.2015.68"},{"key":"22","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":"23","doi-asserted-by":"publisher","unstructured":"M\u00e1ri\u00f3 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.","DOI":"10.1109\/FOCS.2004.53"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/800116.803749"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-01-13-220\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T14:04:59Z","timestamp":1579269899000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-01-13-220\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,13]]},"references-count":25,"URL":"https:\/\/doi.org\/10.22331\/q-2020-01-13-220","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,13]]},"article-number":"220"}}