# Quantum algorithms for Second-Order Cone Programming and Support Vector Machines

arXiv: https://arxiv.org/abs/1908.06720 · HTML: https://mlsanity.com/paper/1908.06720/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2019.

## Built on by (most cited first, 4 of 4)

- [Quantum Machine Learning for Finance](https://mlsanity.com/paper/2109.04298/) (2021)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)

## Abstract (arXiv)

We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time widetildeO left( n√r fraczeta kappaδ2 log left(1/εright) right) where r is the rank and n the dimension of the SOCP, δ bounds the distance of intermediate solutions from the cone boundary, zeta is a parameter upper bounded by √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 δ-approximate ε-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 ε. 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ω+0.5) (here, ω 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(nk), 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.