# Sublinear quantum algorithms for training linear and kernel-based classifiers

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2019.

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

- [Towards understanding the power of quantum kernels in the NISQ era](https://mlsanity.com/paper/2103.16774/) (2021)
- [Bandwidth Enables Generalization in Quantum Kernel Models](https://mlsanity.com/paper/2206.06686/) (2022)
- [The complexity of quantum support vector machines](https://mlsanity.com/paper/2203.00031/) (2022)
- [Concentration of Data Encoding in Parameterized Quantum Circuits](https://mlsanity.com/paper/2206.08273/) (2022)
- [Blind quantum machine learning with quantum bipartite correlator](https://mlsanity.com/paper/2310.12893/) (2023)
- [Quantum Machine Learning for Finance](https://mlsanity.com/paper/2109.04298/) (2021)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [Payoff-based learning with matrix multiplicative weights in quantum games](https://mlsanity.com/paper/2311.02423/) (2023)
- [Statistical Analysis of Quantum State Learning Process in Quantum Neural Networks](https://mlsanity.com/paper/2309.14980/) (2023)
- [A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity](https://mlsanity.com/paper/2402.15333/) (2024)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Quantum Semi-Supervised Kernel Learning](https://mlsanity.com/paper/2204.10700/) (2022)
- [Adiabatic Quantum Support Vector Machines](https://mlsanity.com/paper/2401.12485/) (2024)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games](https://mlsanity.com/paper/2510.16782/) (2025)

## Abstract (arXiv)

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given n d-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in tildeO(n+d) time. We design sublinear quantum algorithms for the same task running in tildeO(√n +√d) time, a quadratic improvement in both n and d. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of n-dimensional matrix zero-sum games with optimal complexity tildeTheta(√n).