The complexity of quantum support vector machines
Gian Gentinetta, Arne Thomsen, David Sutter, Stefan Woerner
Abstract
Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models corresponds to solving a convex optimization problem either via its primal or dual formulation. Due to the probabilistic nature of quantum mechanics, the training algorithms are affected by statistical uncertainty, which has a major impact on their complexity. We show that the dual problem can be solved in <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>M</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>4.67</mml:mn></mml:mrow></mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:msup><mml:mi>&#x03B5;</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> quantum circuit evaluations, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>M</mml:mi></mml:math> denotes the size of the data set and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B5;</mml:mi></mml:math> the solution accuracy compared to the ideal result from exact expectation values, which is only obtainable in theory. We prove under an empirically motivated assumption that the kernelized primal problem can alternatively be solved in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo movablelimits="true" form="prefix">min</mml:mo><mml:mo fence="false" stretchy="false">{</mml:mo><mml:msup><mml:mi>M</mml:mi><mml:mn>2</mml:mn></mml:msup><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:msup><mml:mi>&#x03B5;</mml:mi><mml:mn>6</mml:mn></mml:msup><mml:mo>,</mml:mo><mml:mspace width="thinmathspace"/><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:msup><mml:mi>&#x03B5;</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mn>10</mml:mn></mml:mrow></mml:msup><mml:mo fence="false" stretchy="false">}</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math> evaluations by employing a generalization of a known classical algorithm called Pegasos. Accompanying empirical results demonstrate these analytical complexities to be essentially tight. In addition, we investigate a variational approximation to quantum support vector machines and show that their heuristic training achieves considerably better scaling in our experiments.