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

Quantum Perceptron Revisited: Computational-Statistical Tradeoffs

Mathieu Roget, Giuseppe Di Molfetta, Hachem Kadri

Published Jan 1, 2022• 0 citations
OpenAlex

Abstract

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.

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•2 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•1 citation

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•10 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•141 citations

A Grover-search based quantum learning scheme for classification

Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu +1 more

Abstract The hybrid quantum–classical learning scheme provides a prominent way to achieve quantum advantages on near-term quantum devices. A concrete example toward this goal is the quantum neural network (QNN), which has been developed to accomplish various supervised learning tasks such as classification and regression. However, there are two central issues that remain obscure when QNN is exploited to accomplish classification tasks. First, a quantum classifier that can well balance the computational cost such as the number of measurements and the learning performance is unexplored. Second, it is unclear whether quantum classifiers can be applied to solve certain problems that outperform their classical counterparts. Here we devise a Grover-search based quantum learning scheme (GBLS) to address the above two issues. Notably, most existing QNN-based quantum classifiers can be seamlessly embedded into the proposed scheme. The key insight behind our proposal is reformulating the classification tasks as the search problem. Numerical simulations exhibit that GBLS can achieve comparable performance with other quantum classifiers under various noise settings, while the required number of measurements is dramatically reduced. We further demonstrate a potential quantum advantage of GBLS over classical classifiers in the measure of query complexity. Our work provides guidance to develop advanced quantum classifiers on near-term quantum devices and opens up an avenue to explore potential quantum advantages in various classification tasks.

arXiv:1809.06056•New Journal of Physics•Jan 22, 2021•55 citations

Investigating Hybrid Algorithms for Quantum Computing in Machine Learning: Improving Data Processing Speed and Handling Complex Problems

K Nandini, Davinder Pal Singh, Velayutham Rethnagurusamy Kavitha +3 more

Quantum computers acting as ML accelerators have attracted considerable interest as a promising avenue for addressing the limitations of classical computing confronted with solving complex, high-dimensional problems and handling large data sets. The most exciting aspect of quantum computing lies in its quantum advantage via techniques such as quantum parallelism, superposition, and entanglement which allows not only for rapid data processing, but also a means to resolve complex optimization problems beyond the capacity of classical algorithms. Nevertheless, the usage of quantum computing in machine learning is still a fledgling domain, with challenges concerning quantum noise, hardware restrictions, and algorithmic development. In particular, this research is concerned with the development of and study on hybrid quantum-classical algorithms that target to improve ML models in terms of computational capabilities by making use of the best of both worlds. To address this, researchers are developing hybrid algorithms that leverage the strengths of quantum computing for specific tasks, like optimization and pattern recognition, while still relying on classical computing for more flexible and larger-scale processing, ultimately achieving more efficient machine learning systems that can handle large datasets and complex problem-solving more effectively. It includes potential hybrid approaches like quantum-enhanced optimization algorithms, quantum neural networks, and quantum support vector machines, and examines how such algorithms can be used for practical ML problems including data classification, regression and clustering. Furthermore, the paper proposes that hybrid quantum algorithms offer several advantages over their classical counterparts, such as faster convergence rates, higher accuracy in high-dimensional spaces, and improved handling of non-linear and complex problem landscapes. Key advancements in the area of data processing speed and efficiency in problem-solving with and without quantum in the machine learning workflow are also highlighted in the research through comparative analysis and simulation studies. Lastly, the paper concludes by outlining the obstacles yet to be surmounted and the opportunities that lie ahead for hybrid quantum-classical algorithms, such as further improvement of quantum hardware and error mitigation methods, as well as the design of new algorithmic paradigms that seamlessly integrates the classical and quantum computing spaces.

International Conference on Networks and Cryptology (NETCRYPT)•May 29, 2025•2 citations
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.
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.
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.
Abstract The hybrid quantum–classical learning scheme provides a prominent way to achieve quantum advantages on near-term quantum devices. A concrete example toward this goal is the quantum neural network (QNN), which has been developed to accomplish various supervised learning tasks such as classification and regression. However, there are two central issues that remain obscure when QNN is exploited to accomplish classification tasks. First, a quantum classifier that can well balance the computational cost such as the number of measurements and the learning performance is unexplored. Second, it is unclear whether quantum classifiers can be applied to solve certain problems that outperform their classical counterparts. Here we devise a Grover-search based quantum learning scheme (GBLS) to address the above two issues. Notably, most existing QNN-based quantum classifiers can be seamlessly embedded into the proposed scheme. The key insight behind our proposal is reformulating the classification tasks as the search problem. Numerical simulations exhibit that GBLS can achieve comparable performance with other quantum classifiers under various noise settings, while the required number of measurements is dramatically reduced. We further demonstrate a potential quantum advantage of GBLS over classical classifiers in the measure of query complexity. Our work provides guidance to develop advanced quantum classifiers on near-term quantum devices and opens up an avenue to explore potential quantum advantages in various classification tasks.
Quantum computers acting as ML accelerators have attracted considerable interest as a promising avenue for addressing the limitations of classical computing confronted with solving complex, high-dimensional problems and handling large data sets. The most exciting aspect of quantum computing lies in its quantum advantage via techniques such as quantum parallelism, superposition, and entanglement which allows not only for rapid data processing, but also a means to resolve complex optimization problems beyond the capacity of classical algorithms. Nevertheless, the usage of quantum computing in machine learning is still a fledgling domain, with challenges concerning quantum noise, hardware restrictions, and algorithmic development. In particular, this research is concerned with the development of and study on hybrid quantum-classical algorithms that target to improve ML models in terms of computational capabilities by making use of the best of both worlds. To address this, researchers are developing hybrid algorithms that leverage the strengths of quantum computing for specific tasks, like optimization and pattern recognition, while still relying on classical computing for more flexible and larger-scale processing, ultimately achieving more efficient machine learning systems that can handle large datasets and complex problem-solving more effectively. It includes potential hybrid approaches like quantum-enhanced optimization algorithms, quantum neural networks, and quantum support vector machines, and examines how such algorithms can be used for practical ML problems including data classification, regression and clustering. Furthermore, the paper proposes that hybrid quantum algorithms offer several advantages over their classical counterparts, such as faster convergence rates, higher accuracy in high-dimensional spaces, and improved handling of non-linear and complex problem landscapes. Key advancements in the area of data processing speed and efficiency in problem-solving with and without quantum in the machine learning workflow are also highlighted in the research through comparative analysis and simulation studies. Lastly, the paper concludes by outlining the obstacles yet to be surmounted and the opportunities that lie ahead for hybrid quantum-classical algorithms, such as further improvement of quantum hardware and error mitigation methods, as well as the design of new algorithmic paradigms that seamlessly integrates the classical and quantum computing spaces.