Abstract
Second-order cone programs (SOCPs) are a class of convex optimization problems that generalize linear programs (LPs). We present a quantum interior-point method for SOCPs with n variables and r
conic constraints with running time $O( n^{1.5} r^{0.5} \kappa/ \delta^2)$ where $\delta$ bounds the distance of intermediate solutions from the cone boundary and $\kappa$ is an upper bound on the condition number of matrices arising in the classical interior-point method for SOCPs. We present experimental evidence that the proposed quantum algorithm achieves a polynomial speedup over classical SOCP solvers for the Support Vector Machine (SVM) and Portfolio Optimization problems, which are known to be reducible to SOCPs.