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

doi:10.22331/q-2021-04-08-427

2021-04-08

Iordanis Kerenidis *

Anupam Prakash

Dániel Szilágyi

DOI：10.22331/q-2021-04-08-427

原文链接

原文求助

摘要

En 中文

We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time (O) over tilde (n root r zeta kappa/delta 2 log (1/epsilon) where r is the rank and n the dimension of the SOCP, zeta bounds the distance of intermediate solutions from the cone boundary, zeta is a parameter upper bounded by root 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, w 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.

Keyword:

INTERIOR-POINT METHODS