1QCWare, Palo Alto, California
2Université de Paris, CNRS, IRIF, F-75006, Paris, France
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time $widetilde{O} left( nsqrt{r} frac{zeta kappa}{delta^2} log left(1/epsilonright) right)$ where $r$ is the rank and $n$ the dimension of the SOCP, $delta$ bounds the distance of intermediate solutions from the cone boundary, $zeta$ is a parameter upper bounded by $sqrt{n}$, and $kappa$ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a $delta$-approximate $epsilon$-optimal solution of the given problem.
Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision $epsilon$. We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time $O(n^{omega+0.5})$ (here, $omega$ is the matrix multiplication exponent, with a value of roughly $2.37$ in theory, and up to $3$ in practice). For the case of random SVM (support vector machine) instances of size $O(n)$, the quantum algorithm scales as $O(n^k)$, where the exponent $k$ is estimated to be $2.59$ using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is $3.31$ while that for a state-of-the-art SVM solver is $3.11$.
► BibTeX data
► References
[1] F. Alizadeh and D. Goldfarb. Second-order cone programming. Math. Program., 95 (1, Ser. B): 3–51, 2003. ISSN 0025-5610. 10.1007/s10107-002-0339-5. ISMP 2000, Part 3 (Atlanta, GA).
https://doi.org/10.1007/s10107-002-0339-5
[2] Jonathan Allcock and Chang-Yu Hsieh. A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time. Quantum, 4: 342, October 2020. ISSN 2521-327X. 10.22331/q-2020-10-15-342.
https://doi.org/10.22331/q-2020-10-15-342
[3] Tomasz Arodz and Seyran Saeedi. Quantum sparse support vector machines, 2019. URL https://arxiv.org/abs/1902.01879.
arXiv:1902.01879
[4] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory Comput., 8: 121–164, 2012. 10.4086/toc.2012.v008a006.
https://doi.org/10.4086/toc.2012.v008a006
[5] Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001. ISBN 0-89871-491-5. 10.1137/1.9780898718829. Analysis, algorithms, and engineering applications.
https://doi.org/10.1137/1.9780898718829
[6] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2004. ISBN 0-521-83378-7. 10.1017/CBO9780511804441.
https://doi.org/10.1017/CBO9780511804441
[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 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 27, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. 10.4230/LIPICS.ICALP.2019.27.
https://doi.org/10.4230/LIPICS.ICALP.2019.27
[8] Fernando G. S L. Brandão, Richard Kueng, and Daniel Stilck França. Faster quantum and classical sdp approximations for quadratic binary optimization, 2020. URL https://arxiv.org/abs/1909.04613.
arXiv:1909.04613
[9] Fernando G.S.L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, pages 415–426. IEEE Computer Soc., Los Alamitos, CA, 2017. 10.1109/focs.2017.45.
https://doi.org/10.1109/focs.2017.45
[10] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8 (3-4): 231–357, 2015. 10.1561/2200000050.
https://doi.org/10.1561/2200000050
[11] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 33, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. 10.4230/LIPICS.ICALP.2019.33.
https://doi.org/10.4230/LIPICS.ICALP.2019.33
[12] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2 (3): 1–27, April 2011. 10.1145/1961189.1961199.
https://doi.org/10.1145/1961189.1961199
[13] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 938–942. ACM, New York, 2019. 10.1145/3313276.3316303.
https://doi.org/10.1145/3313276.3316303
[14] Hilary Dollar. Iterative linear algebra for constrained optimization. PhD thesis, University of Oxford, 2005. URL https://www.numerical.rl.ac.uk/people/hsd/thesismain.pdf.
https://www.numerical.rl.ac.uk/people/hsd/thesismain.pdf
[15] Alexander Domahidi, Eric Chu, and Stephen Boyd. ECOS: An SOCP solver for embedded systems. In 2013 European Control Conference (ECC). IEEE, July 2013. 10.23919/ecc.2013.6669541.
https://doi.org/10.23919/ecc.2013.6669541
[16] Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. LIBLINEAR: A library for large linear classification. Journal of machine learning research, 9 (Aug): 1871–1874, 2008. URL https://www.jmlr.org/papers/volume9/fan08a/fan08a.
https://www.jmlr.org/papers/volume9/fan08a/fan08a
[17] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1425–1444. SIAM, Philadelphia, PA, 2019a. 10.1137/1.9781611975482.87.
https://doi.org/10.1137/1.9781611975482.87
[18] 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 STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204. ACM, New York, 2019b. 10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366
[19] András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension, 2018. URL https://arxiv.org/abs/1811.04909.
arXiv:1811.04909
[20] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pages 212–219. ACM, New York, 1996. 10.1145/237814.237866.
https://doi.org/10.1145/237814.237866
[21] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103 (15), October 2009. 10.1103/physrevlett.103.150502.
https://doi.org/10.1103/physrevlett.103.150502
[22] Thorsten Joachims. Training linear SVMs in linear time. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06, page 217–226, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933395. 10.1145/1150402.1150429.
https://doi.org/10.1145/1150402.1150429
[23] N. Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC ’84, pages 302–311. ACM Press, 1984. 10.1145/800057.808695.
https://doi.org/10.1145/800057.808695
[24] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-029-3. 10.4230/LIPIcs.ITCS.2017.49.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
[25] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Phys. Rev. A, 101: 022316, Feb 2020a. 10.1103/PhysRevA.101.022316.
https://doi.org/10.1103/PhysRevA.101.022316
[26] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 1 (1), October 2020b. ISSN 2643-6809. 10.1145/3406306.
https://doi.org/10.1145/3406306
[27] Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2140–2157, Phoenix, USA, 25–28 Jun 2019. PMLR. URL http://proceedings.mlr.press/v99/lee19a.html.
http://proceedings.mlr.press/v99/lee19a.html
[28] Renato D. C. Monteiro and Takashi Tsuchiya. Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Math. Program., 88 (1, Ser. A): 61–83, 2000. ISSN 0025-5610. 10.1007/PL00011378.
https://doi.org/10.1007/PL00011378
[29] Yu. E. Nesterov and M. J. Todd. Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res., 22 (1): 1–42, 1997. ISSN 0364-765X. 10.1287/moor.22.1.1.
https://doi.org/10.1287/moor.22.1.1
[30] Yu. E. Nesterov and M. J. Todd. Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim., 8 (2): 324–364, 1998. ISSN 1052-6234. 10.1137/S1052623495290209.
https://doi.org/10.1137/S1052623495290209
[31] John Neter, Michael H Kutner, Christopher J Nachtsheim, and William Wasserman. Applied linear statistical models, volume 4. Irwin Chicago, 1996.
[32] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2009. 10.1017/cbo9780511976667.
https://doi.org/10.1017/cbo9780511976667
[33] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113 (13), September 2014. 10.1103/physrevlett.113.130503.
https://doi.org/10.1103/physrevlett.113.130503
[34] Yousef Saad. Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, second edition, 2003. ISBN 0-89871-534-2. 10.1137/1.9780898718003.
https://doi.org/10.1137/1.9780898718003
[35] Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994), pages 124–134. IEEE Comput. Soc. Press, Los Alamitos, CA, 1994. 10.1109/SFCS.1994.365700.
https://doi.org/10.1109/SFCS.1994.365700
[36] Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13 (4): 354–356, August 1969. 10.1007/bf02165411.
https://doi.org/10.1007/bf02165411
[37] J.A.K. Suykens and J. Vandewalle. Least squares support vector machine classifiers. Neural Processing Letters, 9 (3): 293–300, 1999. 10.1023/a:1018628609742.
https://doi.org/10.1023/a:1018628609742
[38] J.A.K. Suykens, J. De Brabanter, L. Lukas, and J. Vandewalle. Weighted least squares support vector machines: robustness and sparse approximation. Neurocomputing, 48 (1-4): 85–105, October 2002. 10.1016/s0925-2312(01)00644-0.
https://doi.org/10.1016/s0925-2312(01)00644-0
[39] Daniel Szilagyi, Iordanis Kerenidis, and Anupam Prakash. Quantum SVM via SOCP experiment logs. Mar 2021. 10.6084/m9.figshare.11778189.v1.
https://doi.org/10.6084/m9.figshare.11778189.v1
[40] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 99, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. 10.4230/LIPICS.ICALP.2019.99.
https://doi.org/10.4230/LIPICS.ICALP.2019.99
[41] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, October 2017. 10.1109/focs.2017.44.
https://doi.org/10.1109/focs.2017.44
[42] Yinyu Ye, Michael J. Todd, and Shinji Mizuno. An $O(sqrt{n}L)$-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res., 19 (1): 53–67, 1994. ISSN 0364-765X. 10.1287/moor.19.1.53.
https://doi.org/10.1287/moor.19.1.53
Cited by
[1] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, “Prospects and challenges of quantum finance”, arXiv:2011.06492.
[2] Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao, “Efficient State Read-out for Quantum Machine Learning Algorithms”, arXiv:2004.06421.
[3] Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li, “Quantum Algorithm for Online Convex Optimization”, arXiv:2007.15046.
[4] Jonathan Allcock and Chang-Yu Hsieh, “A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time”, arXiv:2006.10299.
The above citations are from SAO/NASA ADS (last updated successfully 2021-04-10 01:55:44). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2021-04-10 01:55:42).
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-2021-04-08-427/
- access
- algorithm
- algorithms
- analysis
- applications
- April
- Art
- Atlanta
- authors
- barriers
- BEST
- cambridge
- chicago
- classification
- computer science
- computing
- Conference
- copyright
- Current
- data
- data mining
- Database
- Den
- Dimension
- discovery
- distance
- Dollar
- editor
- Engineering
- European
- experiment
- family
- FAST
- Fe
- finance
- General
- Germany
- harvard
- here
- HTTPS
- IEEE
- industrial
- information
- institutions
- International
- JavaScript
- July
- knowledge
- Languages
- large
- Law
- learning
- Library
- License
- List
- LPs
- machine learning
- Machines
- math
- mathematics
- Mining
- Neural
- New York
- NY
- online
- open
- Oxford
- Paper
- paris
- philadelphia
- phoenix
- power
- Precision
- present
- press
- Program
- Programming
- Programs
- Quantum
- quantum computing
- regression
- research
- review
- Risk
- Run
- scaling
- Science
- Search
- Series
- simulation
- Size
- Society
- Solutions
- State
- support
- Systems
- Technology
- time
- Training
- Transactions
- Transformation
- university
- University of Oxford
- Update
- USA
- value
- volume
- W
- works
- wu
- year
- Yuan
