# Quantum Perceptron Revisited: Computational-Statistical Tradeoffs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Quantum Perceptron Models](https://mlsanity.com/paper/1602.04799/) (2016)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [Simulating a perceptron on a quantum computer](https://mlsanity.com/paper/1412.3635/) (2014)
- [Quantum Expectation-Maximization for Gaussian Mixture Models](https://mlsanity.com/paper/1908.06657/) (2019)
- [Quantum Boosting](https://mlsanity.com/paper/2002.05056/) (2020)
- [Perceptron Mistake Bounds](https://mlsanity.com/paper/1305.0208/) (2013)
- [Quantum Machine Learning Algorithm for Knowledge Graphs](https://mlsanity.com/paper/2001.01077/) (2020)
- [The Grover search as a naturally occurring phenomenon](https://mlsanity.com/paper/1908.11213/) (2019)

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

- [Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey](https://mlsanity.com/paper/2409.07626/) (2024)
- [Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems](https://mlsanity.com/paper/2502.11173/) (2025)
- [Position: Quantum Kernel Machines Should Move Beyond Scalar-Valued Kernels to Realize Their Potential](https://mlsanity.com/paper/2506.03779/) (2025)
- [Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes](https://mlsanity.com/paper/2308.12304/) (2023)
- [On Quantum Perceptron Learning via Quantum Search](https://mlsanity.com/paper/2503.17308/) (2025)

## Abstract (arXiv)

Quantum machine learning algorithms could provide significant speed-ups over their classical counterparts; however, whether they could also achieve good generalization remains unclear. Recently, two quantum perceptron models which give a quadratic improvement over the classical perceptron algorithm using Grover's search have been proposed by Wiebe et al. arXiv:1602.04799 . While the first model reduces the complexity with respect to the size of the training set, the second one improves the bound on the number of mistakes made by the perceptron. In this paper, we introduce a hybrid quantum-classical perceptron algorithm with lower complexity and better generalization ability than the classical perceptron. We show a quadratic improvement over the classical perceptron in both the number of samples and the margin of the data. We derive a bound on the expected error of the hypothesis returned by our algorithm, which compares favorably to the one obtained with the classical online perceptron. We use numerical experiments to illustrate the trade-off between computational complexity and statistical accuracy in quantum perceptron learning and discuss some of the key practical issues surrounding the implementation of quantum perceptron models into near-term quantum devices, whose practical implementation represents a serious challenge due to inherent noise. However, the potential benefits make correcting this worthwhile.