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:2503.17308 · Quantum Machine Intelligence

On quantum perceptron learning via quantum search

Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, Hachem Kadri

Published Jun 19, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s42484-026-00406-4

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.

•Jan 1, 2022•0 citations

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

Simulation of a Variational Quantum Perceptron using Grover's Algorithm

Nouhaila Innan, Mohamed Bennai

The quantum perceptron, the variational circuit, and the Grover algorithm have been proposed as promising components for quantum machine learning. This paper presents a new quantum perceptron that combines the quantum variational circuit and the Grover algorithm. However, this does not guarantee that this quantum variational perceptron with Grover's algorithm (QVPG) will have any advantage over its quantum variational (QVP) and classical counterparts. Here, we examine the performance of QVP and QVP-G by computing their loss function and analyzing their accuracy on the classification task, then comparing these two quantum models to the classical perceptron (CP). The results show that our two quantum models are more efficient than CP, and our novel suggested model QVP-G outperforms the QVP, demonstrating that the Grover can be applied to the classification task and even makes the model more accurate, besides the unstructured search problems.

arXiv:2305.11040•May 18, 2023•0 citations

Machine Learning in the Quantum Era

Sachin Khurana, Manisha J. Nene

Machine Learning (ML) has been extensively utilized in various scientific and engineering domains. But the inherent constraints and computational complexity that arise in classical machine learning are particularly evident when dealing with large-scale, high-dimensional datasets or when attempting to solve intricate optimisation problems. Quantum systems exhibit unconventional patterns that are typically not effectively generated by traditional systems and can also tackle high dimensional and large size datasets efficiently. Therefore, it is believed that quantum computing systems may outperform traditional computing devices in machine learning tasks. Quantum Machine Learning (QML) has emerged as a rapidly developing field that combines the concepts of quantum mechanics and machine learning to solve complex problems across various disciplines. The domain of quantum machine learning investigates the development and execution of quantum software with the potential to facilitate machine learning at a much superior pace compared to traditional computers. However, the major challenges encountered are hardware limitations, noise, and development of quantum algorithms. The objective of this paper is to provide an insight on the foundational principles, essential algorithms, various associated platforms, potential applications and challenges being faced by QML. As data continues to grow in size and complexity, together with the emergence of nonlinear and high-dimensional real-world situations, the computing benefits offered by QML have the potential to facilitate significant advancements in the fields of healthcare, finance, robotics, logistics, communication, and cyber security. This paper presents the basis for future research work related to development of quantum algorithms in the domain of machine learning.

International Conference on Futuristic Technologies (INCOFT)•Nov 24, 2023•4 citations

Quadratic quantum speedup for perceptron training

Pengcheng Liao, Barry C. Sanders, Tim Byrnes

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.

arXiv:2109.04695•Physical Review A•Dec 9, 2024•6 citations
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.
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.
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.
The quantum perceptron, the variational circuit, and the Grover algorithm have been proposed as promising components for quantum machine learning. This paper presents a new quantum perceptron that combines the quantum variational circuit and the Grover algorithm. However, this does not guarantee that this quantum variational perceptron with Grover's algorithm (QVPG) will have any advantage over its quantum variational (QVP) and classical counterparts. Here, we examine the performance of QVP and QVP-G by computing their loss function and analyzing their accuracy on the classification task, then comparing these two quantum models to the classical perceptron (CP). The results show that our two quantum models are more efficient than CP, and our novel suggested model QVP-G outperforms the QVP, demonstrating that the Grover can be applied to the classification task and even makes the model more accurate, besides the unstructured search problems.
Machine Learning (ML) has been extensively utilized in various scientific and engineering domains. But the inherent constraints and computational complexity that arise in classical machine learning are particularly evident when dealing with large-scale, high-dimensional datasets or when attempting to solve intricate optimisation problems. Quantum systems exhibit unconventional patterns that are typically not effectively generated by traditional systems and can also tackle high dimensional and large size datasets efficiently. Therefore, it is believed that quantum computing systems may outperform traditional computing devices in machine learning tasks. Quantum Machine Learning (QML) has emerged as a rapidly developing field that combines the concepts of quantum mechanics and machine learning to solve complex problems across various disciplines. The domain of quantum machine learning investigates the development and execution of quantum software with the potential to facilitate machine learning at a much superior pace compared to traditional computers. However, the major challenges encountered are hardware limitations, noise, and development of quantum algorithms. The objective of this paper is to provide an insight on the foundational principles, essential algorithms, various associated platforms, potential applications and challenges being faced by QML. As data continues to grow in size and complexity, together with the emergence of nonlinear and high-dimensional real-world situations, the computing benefits offered by QML have the potential to facilitate significant advancements in the fields of healthcare, finance, robotics, logistics, communication, and cyber security. This paper presents the basis for future research work related to development of quantum algorithms in the domain of machine learning.
Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size NNN 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.