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:2108.11670 · Quantum

Quantum Alphatron: quantum advantage for learning with kernels and noise

Siyi Yang, Naixu Guo, Miklós Sántha, Patrick Rebentrost

Published Nov 8, 2023• 3 citations
arXivHTMLPDF

Abstract

At the interface of machine learning and quantum computing, an important question is what distributions can be learned provably with optimal sample complexities and with quantum-accelerated time complexities. In the classical case, Klivans and Goel discussed the Alphatron , an algorithm to learn distributions related to kernelized regression, which they also applied to the learning of two-layer neural networks. In this work, we provide quantum versions of the Alphatron in the fault-tolerant setting. In a well-defined learning model, this quantum algorithm is able to provide a polynomial speedup for a large range of parameters of the underlying concept class. We discuss two types of speedups, one for evaluating the kernel matrix and one for evaluating the gradient in the stochastic gradient descent procedure. We also discuss the quantum advantage in the context of learning of two-layer neural networks. Our work contributes to the study of quantum learning with kernels and from samples.

DOI
10.22331/q-2023-11-08-1174

Related papers

Quantum Alphatron.

Patrick Rebentrost, Miklós Sántha, Siyi Yang

Many machine learning algorithms optimize a loss function with stochastic gradient descent and use kernel methods to extend linear learning tasks to non-linear learning tasks. Both ideas have been discussed in the context of quantum computing, especially for near-term quantum computing with variational methods and the use of the Hilbert space to encode features of data. In this work, we discuss a quantum algorithm with provable learning guarantee in the fault-tolerant quantum computing model. In a well-defined learning model, this quantum algorithm is able to provide a polynomial speedup for a large range of parameters of the underlying concept class. We discuss two types of speedups, one for evaluating the kernel matrix and one for evaluating the gradient in the stochastic gradient descent procedure. Our work contributes to the study of quantum learning with kernels and noise.

•Aug 26, 2021•1 citation

Provable Advantage in Quantum Phase Learning via Quantum Kernel Alphatron

Yusen Wu, Bujiao Wu, Jingbo Wang +1 more

Abstract The use of quantum computation to speed-up machine learning algorithms is among the most exciting prospective applications in the NISQ era. Here, we focus on the quantum phase learning problem, which is crucially important in understanding many-particle quantum systems. We prove that, under widely believed complexity theory assumptions, quantum phase learning problem cannot be efficiently solved by machine learning algorithms using classical resources and classical data. Whereas using quantum data, we prove the universality of quantum kernel Alphatron in efficiently predicting quantum phases, indicating clear quantum advantages in such learning problems. We numerically benchmark the algorithm for a variety of problems, including recognizing symmetry-protected topological phases and symmetry-broken phases. Our results highlight the capability of quantum machine learning in efficient prediction of quantum phases of many-particle systems.

•Jan 5, 2022•0 citations

Provable Advantage in Quantum Phase Learning via Quantum Kernel Alphatron

Wu Yusen, Bujiao Wu, Jingbo B. Wang +1 more

Abstract The use of quantum computation to speed-up machine learning algorithms is among the most exciting prospective applications in the NISQ era. Here, we focus on the quantum phase learning problem, which is crucially important in understanding many-particle quantum systems. We prove that, under widely believed complexity theory assumptions, quantum phase learning problem cannot be efficiently solved by machine learning algorithms using classical resources and classical data. Whereas using quantum data, we prove the universality of quantum kernel Alphatron in efficiently predicting quantum phases, indicating clear quantum advantages in such learning problems. We numerically benchmark the algorithm for a variety of problems, including recognizing symmetry-protected topological phases and symmetry-broken phases. Our results highlight the capability of quantum machine learning in efficient prediction of quantum phases of many-particle systems.

•Jan 5, 2022•2 citations

Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions

Hayata Yamasaki, Sathyawageeswar Subramanian, Sho Sonoda +1 more

Kernel methods augmented with random features give scalable algorithms for learning from big data. But it has been computationally hard to sample random features according to a probability distribution that is optimized for the data, so as to minimize the required number of features for achieving the learning to a desired accuracy. Here, we develop a quantum algorithm for sampling from this optimized distribution over features, in runtime $O(D)$ that is linear in the dimension $D$ of the input data. Our algorithm achieves an exponential speedup in $D$ compared to any known classical algorithm for this sampling task. In contrast to existing quantum machine learning algorithms, our algorithm circumvents sparsity and low-rank assumptions and thus has wide applicability. We also show that the sampled features can be combined with regression by stochastic gradient descent to achieve the learning without canceling out our exponential speedup. Our algorithm based on sampling optimized random features leads to an accelerated framework for machine learning that takes advantage of quantum computers.

arXiv:2004.10756•Apr 22, 2020•9 citations

Quantum advantage for learning shallow neural networks with natural data distributions

L. Lewis, Dar Gilboa, Jarrod R. McClean

Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.

arXiv:2503.20879•Nature Communications•Dec 31, 2025•1 citation

Hybrid Quantum Classical Acceleration of Machine Learning Algorithms: A Performance Study

Mahesh V, Ramkumar Krishnamoorthy, Diwakara Vasuman M S +2 more

The recent rise in the number of data-intensive applications has revealed some inherent limitations of traditional machine learning, such as high training costs, slow convergence rates, and the uncapable of scalability of traditional machine learning in high-dimensional spaces. Bottlenecks are caused by the iterative optimization procedure, kernel evaluations, and similarity computations that are not efficiently supported by traditional hardware. Although recent advances in quantum computing, such as the Variational Quantum Algorithm, quantum kernels, and parameterized quantum circuits, hold promise for acceleration, the application of quantum speedup is presently hindered by noisy intermediate-scale quantum computing. This research provides a hybrid quantum-classical acceleration method that integrates quantum methods with selected computationally intensive components of classical machine learning systems rather than attempting to entirely replace them. Carried out a comprehensive analysis of the performance of well-known algorithms like Support Vector Machines, k-means clustering, and gradient-based neural networks in classical and quantum-assisted hybrid scenarios. The quantum resources are greatly beneficial for particular sub-tasks such as optimization, approximation of similarity, and exploration of the feature space, with the remaining learning process performed classically. Our analysis reveals that hybrid methods can offer a tangible acceleration and improved convergence behaviour in particular scenarios without sacrificing accuracy. Moreover, the analysis investigates the trade-offs associated with the utilization of quantum resources, robustness to noise, and orchestration costs.

EPJ Web of Conferences•Jan 1, 2026•0 citations
At the interface of machine learning and quantum computing, an important question is what distributions can be learned provably with optimal sample complexities and with quantum-accelerated time complexities. In the classical case, Klivans and Goel discussed the Alphatron , an algorithm to learn distributions related to kernelized regression, which they also applied to the learning of two-layer neural networks. In this work, we provide quantum versions of the Alphatron in the fault-tolerant setting. In a well-defined learning model, this quantum algorithm is able to provide a polynomial speedup for a large range of parameters of the underlying concept class. We discuss two types of speedups, one for evaluating the kernel matrix and one for evaluating the gradient in the stochastic gradient descent procedure. We also discuss the quantum advantage in the context of learning of two-layer neural networks. Our work contributes to the study of quantum learning with kernels and from samples.
Many machine learning algorithms optimize a loss function with stochastic gradient descent and use kernel methods to extend linear learning tasks to non-linear learning tasks. Both ideas have been discussed in the context of quantum computing, especially for near-term quantum computing with variational methods and the use of the Hilbert space to encode features of data. In this work, we discuss a quantum algorithm with provable learning guarantee in the fault-tolerant quantum computing model. In a well-defined learning model, this quantum algorithm is able to provide a polynomial speedup for a large range of parameters of the underlying concept class. We discuss two types of speedups, one for evaluating the kernel matrix and one for evaluating the gradient in the stochastic gradient descent procedure. Our work contributes to the study of quantum learning with kernels and noise.
Abstract The use of quantum computation to speed-up machine learning algorithms is among the most exciting prospective applications in the NISQ era. Here, we focus on the quantum phase learning problem, which is crucially important in understanding many-particle quantum systems. We prove that, under widely believed complexity theory assumptions, quantum phase learning problem cannot be efficiently solved by machine learning algorithms using classical resources and classical data. Whereas using quantum data, we prove the universality of quantum kernel Alphatron in efficiently predicting quantum phases, indicating clear quantum advantages in such learning problems. We numerically benchmark the algorithm for a variety of problems, including recognizing symmetry-protected topological phases and symmetry-broken phases. Our results highlight the capability of quantum machine learning in efficient prediction of quantum phases of many-particle systems.
Abstract The use of quantum computation to speed-up machine learning algorithms is among the most exciting prospective applications in the NISQ era. Here, we focus on the quantum phase learning problem, which is crucially important in understanding many-particle quantum systems. We prove that, under widely believed complexity theory assumptions, quantum phase learning problem cannot be efficiently solved by machine learning algorithms using classical resources and classical data. Whereas using quantum data, we prove the universality of quantum kernel Alphatron in efficiently predicting quantum phases, indicating clear quantum advantages in such learning problems. We numerically benchmark the algorithm for a variety of problems, including recognizing symmetry-protected topological phases and symmetry-broken phases. Our results highlight the capability of quantum machine learning in efficient prediction of quantum phases of many-particle systems.
Kernel methods augmented with random features give scalable algorithms for learning from big data. But it has been computationally hard to sample random features according to a probability distribution that is optimized for the data, so as to minimize the required number of features for achieving the learning to a desired accuracy. Here, we develop a quantum algorithm for sampling from this optimized distribution over features, in runtime O(D)O(D)O(D) that is linear in the dimension DDD of the input data. Our algorithm achieves an exponential speedup in DDD compared to any known classical algorithm for this sampling task. In contrast to existing quantum machine learning algorithms, our algorithm circumvents sparsity and low-rank assumptions and thus has wide applicability. We also show that the sampled features can be combined with regression by stochastic gradient descent to achieve the learning without canceling out our exponential speedup. Our algorithm based on sampling optimized random features leads to an accelerated framework for machine learning that takes advantage of quantum computers.
Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.
The recent rise in the number of data-intensive applications has revealed some inherent limitations of traditional machine learning, such as high training costs, slow convergence rates, and the uncapable of scalability of traditional machine learning in high-dimensional spaces. Bottlenecks are caused by the iterative optimization procedure, kernel evaluations, and similarity computations that are not efficiently supported by traditional hardware. Although recent advances in quantum computing, such as the Variational Quantum Algorithm, quantum kernels, and parameterized quantum circuits, hold promise for acceleration, the application of quantum speedup is presently hindered by noisy intermediate-scale quantum computing. This research provides a hybrid quantum-classical acceleration method that integrates quantum methods with selected computationally intensive components of classical machine learning systems rather than attempting to entirely replace them. Carried out a comprehensive analysis of the performance of well-known algorithms like Support Vector Machines, k-means clustering, and gradient-based neural networks in classical and quantum-assisted hybrid scenarios. The quantum resources are greatly beneficial for particular sub-tasks such as optimization, approximation of similarity, and exploration of the feature space, with the remaining learning process performed classically. Our analysis reveals that hybrid methods can offer a tangible acceleration and improved convergence behaviour in particular scenarios without sacrificing accuracy. Moreover, the analysis investigates the trade-offs associated with the utilization of quantum resources, robustness to noise, and orchestration costs.