The complexity of quantum support vector machines

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 $O(M^{4.67}/{\epsilon }^2)$ quantum circuit evaluations, where $M$ denotes the size of the data set and $\epsilon$ 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 $O(\min \{M^2/{\epsilon }^6,1/{\epsilon }^{10}\})$ 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.

v2: published version

References in corpus (8)

• Variational Quantum Algorithms
• Kernel methods in machine learning
• A rigorous and robust quantum speed-up in supervised machine learning
• Training Quantum Embedding Kernels on Near-Term Quantum Computers
• Higgs analysis with quantum classifiers
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Noisy Quantum Kernel Machines
• Exponential concentration in quantum kernel methods

Cited by in corpus (8)

• Variational Quantum Time Evolution without the Quantum Geometric Tensor
• Provable bounds for noise-free expectation values computed from noisy samples
• Quantum Kernel Alignment with Stochastic Gradient Descent
• Efficient Parameter Optimisation for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training
• Solving The Vehicle Routing Problem via Quantum Support Vector Machines
• Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
• Reconstructing charged particle track segments with a quantum-enhanced support vector machine
• Data-Dependent Generalization Bounds for Parameterized Quantum Models Under Noise