On Quantum Perceptron Learning via Quantum Search

Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, and Hachem Kadri · 2025

Read On Quantum Perceptron Learning via Quantum Search by Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, and Hachem Kadri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17308.txt.

Introduction

Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, and Hachem Kadri revisit how fast a quantum computer could train a perceptron, the simplest learning unit. An earlier quantum version of the training method was thought to scale well. The team found a flaw in that claim: the cost quietly depends on the size of the data space.

In high dimensions, the earlier method can slow far more than advertised. The authors then build two improved training methods on known quantum tricks, including Grover's search and quantum walks. They lay out the designs and count their costs under ideal, noise-free machines. The results sort out when quantum help truly pays, balancing data size, margin, and machine resources. The work is theory, meant to guide future quantum learning design.

Catalog record

CREATORXiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, and Hachem Kadri
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-17308

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Quantum Perceptron Learning via Quantum Search Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, and Hachem Kadri Abstract 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 quantum advantages. Two quantum perceptron algorithms based on Grover’s search , were developed in [ 18 ] to accelerate training and improve statistical efficiency in perceptron learning. This paper points out and corrects a mistake in the proof of [ 18 , Theorem 2] . Specifically, we show that the probability of sampling from a normal distribution for a D D -dimensional hyperplane that perfectly classifies the data scales as Ω ⁡ ( γ D ) \Omega(\gamma^{D}) instead of Θ ⁡ ( γ ) \Theta({\gamma}) , where γ \gamma is the margin. We then revisit two well-established linear programming algorithms—the ellipsoid method and the cutting plane random walk algorithm—in the context of perceptron learning, and show how quantum search algorithms can be leveraged to enhance the overall complexity. Specifically, both algorithms gain a sub-linear speed-up O ⁡ ( N ) O(\sqrt{N}) in the number of data points N N as a result of Grover’s algorithm and an additional O ⁡ ( D 1.5 ) O(D^{1.5}) speed-up is possible for cutting plane random walk algorithm employing quantum walk search. I Introduction With the great development of computational power and algorithms, machine learning has gained more and more attention in the modern stage with the increasing demand to learn from big data of high feature space dimension and generalize to unseen data, which greatly motivates the use of quantum computing in machine learning. This growing interest has stimulated the emergence of quantum machine learning inter-discipline [ 3 , 33 ] . Originating from the suggestion to use quantum hardware to simulate quantum dynamics with exponential overhead [ 9 ] , quantum computing integrated knowledge from quantum algorithms, quantum information processing and experimental quantum systems. There is growing interest in utilizing quantum mechanics to assist machine learning based on the following facts. First, the unique superposition property allows a qubit to be |0\rangle and |1\rangle simultaneously, equipping qubit systems with an exponentially compact representation compared to bit systems. Classical data can be mapped to quantum states with their probability distributions encoded into amplitudes. This can be extremely useful in handling big data, in which the number of features D can be in the millions. Second, quantum operation inherits quantum parallelism naturally, which allows the use of quantum basic linear algebra subroutines such as quantum Fourier transform [ 29 ] and HHL algorithm [ 15 ] that operate in polylog(D) time, or some others subroutines with quadratic speed-up, such as Grover’s search [ 13 ] and its extension quantum counting algorithm [ 5 ] . Third, it is argued that since quantum mechanics can produce distributions that are intricate to produce by classical computers, it possibly has a stronger ability to recognize patterns [ 3 ] , which could be privileged with quantum data. In supervised machine learning, classification requires algorithms/models to give the correct label to unseen (test) data based on knowledge recognized from labelled training data. The simplest task in classification is likely binary classification on linearly separable data, which is known can be solved by the online perceptron algorithm [ 32 ] with tight update bound that only depends on the geometric margin of data [ 30 , 4 ] . Although the perceptron algorithm is straightforward, it is the basic building unit of multilayer perceptron (MLP), i.e. the single-layer perceptron, which is also the simplest feedforward neural network (FNN). Due to its elementariness and simplicity, it has been considered a good example to study for potential quantum speed-ups on the training complexity and the statistical efficiency of machine learning algorithms [ 18 ] . The rest of our paper is organized as follows: in Section II , we review the connections between perceptron learning, version space and feasible region. We also re-examine two algorithms, online quantum perceptron and quantum version space perceptron proposed in [ 18 ] and their extensions in [ 31 , 22 ] . In Section III , we correct a mistake in the quantum version space perceptron [ 18 ] . Specifically, the probability of sampling for a D -dimensional hyperplane from a normal distribution that perfectly classifies the data scales as \Omega(\gamma^{D}) instead of \Theta(\gamma) , with \gamma denoting the margin. Additionally, we provide a simulation validating our theoretical result. In Section IV , we show how the quantum analogues of two linear programming algorithms —ellipsoidal algorithm and cutting plane random walk algorithm can be used to speed up perceptron learning under a weak online learning setup. Section V provides a cutting plane quantum hit-and-run algorithm, elaborating on how to use quantum walk search [ 25 ] to further speed up sampling. Section VI concludes the paper and also discusses the possibility of acquiring statistical advantages in quantum machine learning. II Background II-A Perceptron Learning Here we follow a deterministic setup, a sample \mathcal{S}=(\bm{x}_{1},\ldots,\bm{x}_{N})\sim\mathcal{D}^{N} is a sequence of instances drawn i.i.d. according to a distribution \mathcal{D} and the labels y_{i}=f(\bm{x}_{i}) are uniquely determined by some measurable function f . We use the notation \{(\bm{x}_{i},y_{i})_{i\in[N]}\} to refer to a sequence of N pairs of training dataset \{(\bm{x}_{1},y_{1}),\ldots,(\bm{x}_{N},y_{N})\} . A hyperplane \bm{w}^{T}\bm{x}+b=0 in the D dimensional space can be defined by a normal vector \bm{w}\in\mathbb{R}^{D} and an intercept b . Here, we only consider the case where b=0 , which is easily achieved by redefining \bm{w}^{\prime T}=(\bm{w}^{T},b) in the enlarged D+1 dimensional space. In the separable case, there exists a hyperplane \bm{w} separating two classes of data with their correspondence labels perfectly, i.e., \bm{w}^{T}\bm{x}_{i}y_{i}>0 , \forall i\in[N] . 1 1 1 In here and the rest of the paper, we refer to a hyperplane \bm{w}^{T}\bm{x}=0 defined by its normal vector \bm{w} as a hyperplane \bm{w} for short. Moreover, when there is a maximal margin hyperplane \bm{u} separating the two classes with a maximal geometric margin \gamma>0 such that \bm{u}^{T}\bm{x}_{i}y_{i}\geq\gamma for all i\in[N] , the vector \bm{u} is called the support vector machine (SVM) solution. Now, given N normalized linearly separable training examples \{\bm{x}_{1},.,\bm{x}_{N}\}\in\mathbb{R}^{D} , ||\bm{x}_{i}||=1 , 2 2 2 We use ||\cdot|| to represent the \ell_{2} norm throughout the paper. with corresponding labels \{y_{1},..,y_{N}\},y_{i}\in\{+1,-1\} . The perceptron model \bm{w} is a weight vector (hyperplane) that follows a prediction rule \hat{y}_{i}=\text{sgn}(\bm{w}^{T}\bm{x}_{i}) for every unlabelled instance \bm{x}_{i} . 3 3 3 We take the sgn function such that \text{sgn}(x)=1 , if x>0 ; and \text{sgn}(x)=-1 , if x\leq 0 . Perceptron learning aims to find a hyperplane \bm{w}^{T}\bm{x}_{i}y_{i}>0 , \forall i\in[N] , such that the perceptron solution has the correct prediction on every example. In the parameter space, the set of hyperplanes satisfying all these N inequalities is called version space \mathcal{VS}:=\{\bm{w}\mid\bm{w}^{T}\bm{x}_{i}y_{i}>0,\forall i\in[N]\} . As only directions of \bm{w} matter for classification, we can limit the length of ||\bm{w}||\leq 1 . Geometrically, the \mathcal{VS} is a bounded polyhedron (a polytope) satisfying N half-spaces constraints, which is also known as a feasible set in the context of convex optimization. When training into converge, the well-known perceptron algorithm [ 32 ] yields a point inside the \mathcal{VS} , and

Read the complete text