# On Quantum Perceptron Learning via Quantum Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 64 references that are in the map.
- First posted on arXiv 21 Mar 2025.

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

- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Quantum Perceptron Models](https://mlsanity.com/paper/1602.04799/) (2016)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [Quantum algorithm for estimating volumes of convex bodies](https://mlsanity.com/paper/1908.03903/) (2019)
- [Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage](https://mlsanity.com/paper/2307.00523/) (2023)
- [Quantum Speedups for Approximating the John Ellipsoid](https://mlsanity.com/paper/2408.14018/) (2024)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [A Sublinear-Time Quantum Algorithm for Approximating Partition Functions](https://mlsanity.com/paper/2207.08643/) (2022)
- [Quantum speedups for linear programming via interior point methods](https://mlsanity.com/paper/2311.03215/) (2023)
- [From Cutting Planes Algorithms to Compression Schemes and Active Learning](https://mlsanity.com/paper/1508.02986/) (2015)
- [Faster quantum mixing for slowly evolving sequences of Markov chains](https://mlsanity.com/paper/1503.01334/) (2015)

## Abstract (arXiv)

With the growing interest in quantum machine learning, the perceptron, a fundamental building block in traditional machine learning, has emerged as a valuable model for exploring the potential of quantum algorithms. In this work, we make two principal contributions. First, we revisit the quantum version space perceptron algorithm proposed by Kapoor et al. (2016), by identifying and correcting a flawed complexity assumption. We show that the query complexity of the algorithm is dimension-dependent, which has significant implications for its behaviour in high-dimensional regimes under worst-case scenarios. Second, we propose and analyse two quantum-enhanced cutting-plane algorithms for perceptron learning. Specifically, we leverage established quantum subroutines such as Grover's search and quantum walk search, and provide detailed algorithmic constructions together with query and arithmetic complexity analyses. Our results establish improved complexity bounds under an idealised implementation framework and noise-free quantum computational models, offering insights into the trade-offs between margin dependence, dimensional dependence, and quantum resources. These findings provide a refined understanding of quantum perceptron models and their theoretical computational complexity properties.