Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.04695 · Physical Review A

Quadratic quantum speedup for perceptron training

Pengcheng Liao, Barry C. Sanders, Tim Byrnes

Published Dec 9, 2024• 6 citations
arXivHTMLPDF

Abstract

Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size $N$ and margin $\ensuremath{\gamma}$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})$ or $N/\sqrt{\ensuremath{\gamma}}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{N/\ensuremath{\gamma}}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.

DOI
10.1103/physreva.110.062412

Related papers

Quantum Perceptron Revisited: Computational-Statistical Tradeoffs

Mathieu Roget, Giuseppe Di Molfetta, Hachem Kadri

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.

arXiv:2106.02496•Jun 4, 2021•1 citation

Quantum Perceptron Revisited: Computational-Statistical Tradeoffs

Mathieu Roget, Giuseppe Di Molfetta, Hachem Kadri

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.

•Jan 1, 2022•0 citations

On quantum perceptron learning via quantum search

Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta +1 more

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 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.

arXiv:2503.17308•Quantum Machine Intelligence•Jun 19, 2026•0 citations

Quantum Circuit Design for Training Perceptron Models

Yu Zheng, Sicong Lu, Re-Bing Wu

Perceptron model is a fundamental linear classifier in machine learning and also the building block of artificial neural networks. Recently, Wiebe et al. (arXiv:1602.04799) proposed that the training of a perceptron can be quadratically speeded using Grover search with a quantum computer, which has potentially important big-data applications. In this paper, we design a quantum circuit for implementing this algorithm. The Grover oracle, the central part of the circuit, is realized by Quantum-Fourier-Transform based arithmetics that specifies whether an input weight vector can correctly classify all training data samples. We also analyze the required number of qubits and universal gates for the algorithm, as well as the success probability using uniform sampling, showing that it has higher possibility than spherical Gaussian distribution $N(0,1)$. The feasibility of the circuit is demonstrated by a testing example using the IBM-Q cloud quantum computer, where 16 qubits are used to classify four data samples.

arXiv:1802.05428•Feb 15, 2018•4 citations

Quantum Perceptron Models

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

We demonstrate how quantum computation can provide non-trivial improvements in the computational and statistical complexity of the perceptron model. We develop two quantum algorithms for perceptron learning. The first algorithm exploits quantum information processing to determine a separating hyperplane using a number of steps sublinear in the number of data points $N$, namely $O(\sqrt{N})$. The second algorithm illustrates how the classical mistake bound of $O(\frac{1}{γ^2})$ can be further improved to $O(\frac{1}{\sqrtγ})$ through quantum means, where $γ$ denotes the margin. Such improvements are achieved through the application of quantum amplitude amplification to the version space interpretation of the perceptron model.

arXiv:1602.04799•neural information processing systems•Feb 15, 2016•103 citations

A Quantum Machine Learning Approach Using an Optimized Application of Grover's Algorithm

Mohamed Yassine Cherif, Wided Lejouad Chaari, Olfa Belkahla Driss

This paper is about studying the application of quantum computing to develop machine learning methods, in order to optimize the time of calculation for processing extensive amounts of data, thanks to the use of the quantum superposition state of information, which enables to apply parallel computation for processing different parts of data simultaneously. In fact, we introduce a quantum approach, using Grover's algorithm, to search for the optimal parameters of a perceptron classifier as a fundamental element for developing a quantum neural network, with the proposition of the training process and the comparison with the related works. The proposed approach enables yielding the optimal parameters of a perceptron classifier with one application of Grover's search method rather than applying the iterative approaches that were previously introduced in the literature.

IEEE Afro-Mediterranean Conference on Artificial Intelligence (AMCAI)•Dec 13, 2023•2 citations
Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size NNN and margin \ensuremathγ\ensuremath{\gamma}\ensuremathγ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either (N/\ensuremathγ2)log(1/\ensuremathγ2)(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})(N​/\ensuremathγ2)log(1/\ensuremathγ2) or N/\ensuremathγN/\sqrt{\ensuremath{\gamma}}N/\ensuremathγ​, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as N/\ensuremathγ\sqrt{N/\ensuremath{\gamma}}N/\ensuremathγ​. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.
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.
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.
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 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.
Perceptron model is a fundamental linear classifier in machine learning and also the building block of artificial neural networks. Recently, Wiebe et al. (arXiv:1602.04799) proposed that the training of a perceptron can be quadratically speeded using Grover search with a quantum computer, which has potentially important big-data applications. In this paper, we design a quantum circuit for implementing this algorithm. The Grover oracle, the central part of the circuit, is realized by Quantum-Fourier-Transform based arithmetics that specifies whether an input weight vector can correctly classify all training data samples. We also analyze the required number of qubits and universal gates for the algorithm, as well as the success probability using uniform sampling, showing that it has higher possibility than spherical Gaussian distribution N(0,1)N(0,1)N(0,1). The feasibility of the circuit is demonstrated by a testing example using the IBM-Q cloud quantum computer, where 16 qubits are used to classify four data samples.
We demonstrate how quantum computation can provide non-trivial improvements in the computational and statistical complexity of the perceptron model. We develop two quantum algorithms for perceptron learning. The first algorithm exploits quantum information processing to determine a separating hyperplane using a number of steps sublinear in the number of data points NNN, namely O(N)O(\sqrt{N})O(N​). The second algorithm illustrates how the classical mistake bound of O(1γ2)O(\frac{1}{γ^2})O(γ21​) can be further improved to O(1γ)O(\frac{1}{\sqrtγ})O(γ​1​) through quantum means, where γγγ denotes the margin. Such improvements are achieved through the application of quantum amplitude amplification to the version space interpretation of the perceptron model.
This paper is about studying the application of quantum computing to develop machine learning methods, in order to optimize the time of calculation for processing extensive amounts of data, thanks to the use of the quantum superposition state of information, which enables to apply parallel computation for processing different parts of data simultaneously. In fact, we introduce a quantum approach, using Grover's algorithm, to search for the optimal parameters of a perceptron classifier as a fundamental element for developing a quantum neural network, with the proposition of the training process and the comparison with the related works. The proposed approach enables yielding the optimal parameters of a perceptron classifier with one application of Grover's search method rather than applying the iterative approaches that were previously introduced in the literature.