Quantum Alphatron: quantum advantage for learning with kernels and noise

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 \textit{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.

38 pages, published in Quantum, metadata updated

References in corpus (14)

• Quantum Computing in the NISQ era and beyond
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum machine learning in feature Hilbert spaces
• Quantum random access memory
• Efficient Learning for Deep Quantum Neural Networks
• Quantum Data Fitting
• Architectures for a quantum random access memory
• Creating superpositions that correspond to efficiently integrable probability distributions
• A quantum-inspired classical algorithm for recommendation systems
• Quantum Neuron: an elementary building block for machine learning on quantum computers
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Quantum algorithms for hedging and the learning of Ising models