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

Abstract

We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time $\tilde{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$.

final version for Quantum

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time

Cited by in corpus (11)

• Quantum computing for finance
• Quantum Machine Learning for Finance
• Prospects and challenges of quantum finance
• Quantum Interior Point Methods for Semidefinite Optimization
• An introduction to variational quantum algorithms for combinatorial optimization problems
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Synergies Between Operations Research and Quantum Information Science
• Quantum Algorithm for Online Convex Optimization
• A New Quantum Approach to Binary Classification