Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
1QCWare, Palo Alto, California
2Université de Paris, CNRS, IRIF, F-75006, Paris, France
Published: | 2021-04-08, volume 5, page 427 |
Eprint: | arXiv:1908.06720v4 |
Doi: | https://doi.org/10.22331/q-2021-04-08-427 |
Citation: | Quantum 5, 427 (2021). |
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( n\sqrt{r} \frac{\zeta \kappa}{\delta^2} \log \left(1/\epsilon\right) \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] Marco Pistoia, Syed Farhan Ahmad, Akshay Ajagekar, Alexander Buts, Shouvanik Chakrabarti, Dylan Herman, Shaohan Hu, Andrew Jena, Pierre Minssen, Pradeep Niroula, Arthur Rattew, Yue Sun, and Romina Yalovetzky, 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD) 1 (2021) ISBN:978-1-6654-4507-8.
[2] Camille Grange, Michael Poss, and Eric Bourreau, "An introduction to variational quantum algorithms for combinatorial optimization problems", 4OR 21 3, 363 (2023).
[3] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).
[4] Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao, "Quantum Gram-Schmidt processes and their application to efficient state readout for quantum algorithms", Physical Review Research 3 4, 043095 (2021).
[5] Iram Manan, Faisal Rehman, Hanan Sharif, Naveed Riaz, Muhammad Atif, and Muhammad Aqeel, 2022 3rd International Conference on Innovations in Computer Science & Software Engineering (ICONICS) 1 (2022) ISBN:978-1-6654-6141-2.
[6] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", INFORMS Journal on Computing 35 2, 266 (2023).
[7] Sander Gribling, Iordanis Kerenidis, and Dániel Szilágyi, "An Optimal Linear-combination-of-unitaries-based Quantum Linear System Solver", ACM Transactions on Quantum Computing 5 2, 1 (2024).
[8] Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino, Tamas Terlaky, and Arielle Carr, 2022 IEEE/ACM 7th Symposium on Edge Computing (SEC) 375 (2022) ISBN:978-1-6654-8611-8.
[9] Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Xiu Yang, and Tamás Terlaky, "An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization", Entropy 25 2, 330 (2023).
[10] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).
[11] Giacomo Nannicini, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.
[12] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga, "Quantum Interior Point Methods for Semidefinite Optimization", Quantum 7, 1110 (2023).
[13] Zidong Lin, Hongfeng Liu, Kai Tang, Yidai Liu, Liangyu Che, Xinyue Long, Xiangyu Wang, Yu-ang Fan, Keyi Huang, Xiaodong Yang, Tao Xin, Xinfang Nie, and Dawei Lu, "Hardware-efficient quantum principal component analysis for medical image recognition", Frontiers of Physics 19 5, 51202 (2024).
[14] Thomas Morstyn and Xiangyue Wang, "Opportunities for quantum computing within net-zero power system optimization", Joule 8 6, 1619 (2024).
[15] Linshu Chen, Tao Li, Yuxiang Chen, Xiaoyan Chen, Marcin Wozniak, Neal Xiong, and Wei Liang, "Design and analysis of quantum machine learning: a survey", Connection Science 36 1, 2312121 (2024).
[16] Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, and Tamás Terlaky, "Efficient Use of Quantum Linear System Algorithms in Inexact Infeasible IPMs for Linear Optimization", Journal of Optimization Theory and Applications 202 1, 146 (2024).
[17] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).
[18] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, "Prospects and challenges of quantum finance", arXiv:2011.06492, (2020).
[19] Jianhao He, Feidiao Yang, Jialin Zhang, and Lvzhou Li, "Quantum algorithm for online convex optimization", Quantum Science and Technology 7 2, 025022 (2022).
[20] Jonathan Allcock and Chang-Yu Hsieh, "A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time", Quantum 4, 342 (2020).
The above citations are from Crossref's cited-by service (last updated successfully 2024-08-31 20:15:33) and SAO/NASA ADS (last updated successfully 2024-08-31 20:15:34). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.