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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mover><mml:mi>O</mml:mi><mml:mo>~</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mi>n</mml:mi><mml:msqrt><mml:mi>r</mml:mi></mml:msqrt><mml:mfrac><mml:mrow><mml:mi>ζ</mml:mi><mml:mi>κ</mml:mi></mml:mrow><mml:msup><mml:mi>δ</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mfrac><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>ϵ</mml:mi></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:math> where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>r</mml:mi></mml:math> is the rank and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> the dimension of the SOCP, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>δ</mml:mi></mml:math> bounds the distance of intermediate solutions from the cone boundary, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ζ</mml:mi></mml:math> is a parameter upper bounded by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt></mml:math>, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>δ</mml:mi></mml:math>-approximate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math>-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math>. 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>ω</mml:mi><mml:mo>+</mml:mo><mml:mn>0.5</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> (here, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ω</mml:mi></mml:math> is the matrix multiplication exponent, with a value of roughly <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>2.37</mml:mn></mml:math> in theory, and up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>3</mml:mn></mml:math> in practice). For the case of random SVM (support vector machine) instances of size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>, the quantum algorithm scales as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mi>k</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>, where the exponent <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> is estimated to be <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>2.59</mml:mn></mml:math> using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>3.31</mml:mn></mml:math> while that for a state-of-the-art SVM solver is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>3.11</mml:mn></mml:math>.

Topics & Concepts