# The complexity of quantum support vector machines

arXiv: https://arxiv.org/abs/2203.00031 · HTML: https://mlsanity.com/paper/2203.00031/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 28 Feb 2022.

## Builds on (most cited first, 12 of 12)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [The Inductive Bias of Quantum Kernels](https://mlsanity.com/paper/2106.03747/) (2021)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Training Quantum Embedding Kernels on Near-Term Quantum Computers](https://mlsanity.com/paper/2105.02276/) (2021)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [Higgs analysis with quantum classifiers](https://mlsanity.com/paper/2104.07692/) (2021)

## Built on by (most cited first, 23 of 23)

- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning](https://mlsanity.com/paper/2301.09138/) (2023)
- [Quantum Kernel Alignment with Stochastic Gradient Descent](https://mlsanity.com/paper/2304.09899/) (2023)
- [Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications](https://mlsanity.com/paper/2307.00908/) (2023)
- [CompressedMediQ: Hybrid Quantum Machine Learning Pipeline for High-Dimensional Neuroimaging Data](https://mlsanity.com/paper/2409.08584/) (2024)
- [Quantum Kernel-Based Long Short-term Memory](https://mlsanity.com/paper/2411.13225/) (2024)
- [Consensus-based Distributed Quantum Kernel Learning for Speech Recognition](https://mlsanity.com/paper/2409.05770/) (2024)
- [Quantum Computing for Climate Resilience and Sustainability Challenges](https://mlsanity.com/paper/2407.16296/) (2024)
- [Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey](https://mlsanity.com/paper/2409.07626/) (2024)
- [Efficient Parameter Optimisation for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training](https://mlsanity.com/paper/2401.02879/) (2024)
- [Quantum-Enhanced Support Vector Machine for Large-Scale Stellar Classification with GPU Acceleration](https://mlsanity.com/paper/2311.12328/) (2023)
- [Quantum Support Vector Machine for Prostate Cancer Detection: A Performance Analysis](https://mlsanity.com/paper/2403.07856/) (2024)
- [Modeling Quantum Machine Learning for Genomic Data Analysis](https://mlsanity.com/paper/2501.08193/) (2025)
- [Data-Dependent Generalization Bounds for Parameterized Quantum Models Under Noise](https://mlsanity.com/paper/2412.11451/) (2024)
- [Probabilistic Quantum SVM Training on Ising Machine](https://mlsanity.com/paper/2503.16363/) (2025)
- [Embedding-Aware Quantum-Classical SVMs for Scalable Quantum Machine Learning](https://mlsanity.com/paper/2508.00024/) (2025)
- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations](https://mlsanity.com/paper/2605.22275/) (2026)
- [On Neural Quantum Support Vector Machines](https://mlsanity.com/paper/2308.08467/) (2023)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [Triplet Loss Based Quantum Encoding for Class Separability](https://mlsanity.com/paper/2509.15705/) (2025)
- [Maritime object classification with SAR imagery using quantum kernel methods](https://mlsanity.com/paper/2512.11367/) (2025)
- [Beyond the Gegenbauer Paradigm: q-Orthogonal Kernels for Machine Learning](https://mlsanity.com/paper/2608.03482/) (2026)

## Abstract (arXiv)

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(M4.67/varepsilon2) quantum circuit evaluations, where M denotes the size of the data set and varepsilon 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  M2/varepsilon6, , 1/varepsilon10 ) 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.