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

ACM SIGACT News

Guest Column

Srinivasan Arunachalam, Ronald de Wolf

Published Jun 12, 2017• 152 citations
Publisher

Abstract

This paper surveys quantum learning theory: the theoretical aspects of machine learning using quantum computers. We describe the main results known for three models of learning: exact learning from membership queries, and Probably Approximately Correct (PAC) and agnostic learning from classical or quantum examples.
DOI
10.1145/3106700.3106710

Related papers

A Survey of Quantum Learning Theory

Srinivasan Arunachalam, Ronald de Wolf

This paper surveys quantum learning theory: the theoretical aspects of machine learning using quantum computers. We describe the main results known for three models of learning: exact learning from membership queries, and Probably Approximately Correct (PAC) and agnostic learning from classical or quantum examples.

arXiv:1701.06806•Jan 24, 2017•44 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

Advances in quantum computational learning theory

Rocco A. Servedio, Alp Atıcı

This dissertation explores results at the intersection of two important branches of theoretical computer science: quantum computation, which studies the power of devices based on quantum physical phenomena, and computational theory, which studies the foundations of machine algorithms. We refer to the area of research at this intersection as quantum computational theory. Like its classical counterpart, quantum computational theory aims to understand the computational and information theoretic requirements of problems and algorithms. However unlike the classical models, the models for quantum learners generally involve quantum sources of information and quantum gates employing quantum physical phenomena such as superposition and entanglement, which do not have classical equivalents. Our results can be summarized as follows: (1) In Chapter 3, we study the information theoretic requirements of quantum learning, partition and Probably Approximately Correct (PAC) learning. First, we develop a new general quantum algorithm, resolving a conjecture by Hunziker et al. [HMP+03]. Next, we present positive and negative results towards the rather general problem of partition of which both exact learning and computing a binary property are special cases. Finally, we derive an improved lower bound on the number of quantum examples required for PAC learning. (2) In Chapter 4, we consider the problem of unions of high dimensional rectangles over the domain [b]n using membership queries and uniform quantum examples. These classes oral generalizations of classes of DNF formulae over {0,1}n that have been extensively studied in the theory literature. (3) In Chapter 5, we develop quantum algorithms for and testing juntas (Boolean functions that depend on a few variables) and sparse functions. These algorithms are based on the quantum subroutine due to Bshouty and Jackson [BJ99] that enables sampling from the Fourier spectrum.

•Jan 1, 2006•2 citations

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Natsuto Isogai, Satoshi Yoshida, Mio Murao

Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.

quant-pharXiv:2609.38403•Oct 1, 2026•0 citations

A Survey on Machine Learning Techniques Using Quantum Computing

T N Manjunath, Adarsh Hiremath, Mudligiriyappa Niranjanamurthy +3 more

Over the course of the last seven decades the world of computing has taken revolutionary reformations in the scope of classical computing. Classical computers manipulate ones and zeroes to crunch through operations given to them by users. An innovative strategy known as quantum computing leverages the concepts of quantum physics to solve issues that are too complex for conventional computers to handle. Two of the domains of science that are now progressing the fastest are theoretical machine learning and quantum computing theory. In recent years, researchers have begun examining how classic machine learning techniques may be improved by quantum computing. Hybrid techniques that integrate conventional and quantum algorithms are part of quantum machine learning. Instead of using standard data, quantum techniques may be utilized to examine quantum states. However, quantum algorithms have the potential to greatly expand current data science techniques. In this paper we review the contribution carried out by various researchers in the field of Quantum Machine Learning and later we look at certain techniques associated with it for its use.

International Conference on Emerging Research in Electronics, Computer Science and Technology (ICERECT)•Dec 26, 2022•10 citations

Is Quantum Advantage the Right Goal for Quantum Machine Learning?

Maria Schuld, Nathan Killoran

Machine learning is frequently listed among the most promising applications for quantum computing. This is in fact a curious choice: Today's machine learning algorithms are notoriously powerful in practice, but remain theoretically difficult to study. Quantum computing, in contrast, does not offer practical benchmarks on realistic scales, and theory is the main tool we have to judge whether it could become relevant for a problem. In this perspective we explain why it is so difficult to say something about the practical power of quantum computers for machine learning with the tools we are currently using. We argue that these challenges call for a critical debate on whether quantum advantage and the narrative of 'beating' classical machine learning should continue to dominate the literature the way it does, and highlight examples for how other perspectives in existing research provide an important alternative to the focus on advantage.

arXiv:2203.01340•PRX Quantum•Jul 14, 2022•215 citations
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
This dissertation explores results at the intersection of two important branches of theoretical computer science: quantum computation, which studies the power of devices based on quantum physical phenomena, and computational theory, which studies the foundations of machine algorithms. We refer to the area of research at this intersection as quantum computational theory. Like its classical counterpart, quantum computational theory aims to understand the computational and information theoretic requirements of problems and algorithms. However unlike the classical models, the models for quantum learners generally involve quantum sources of information and quantum gates employing quantum physical phenomena such as superposition and entanglement, which do not have classical equivalents. Our results can be summarized as follows: (1) In Chapter 3, we study the information theoretic requirements of quantum learning, partition and Probably Approximately Correct (PAC) learning. First, we develop a new general quantum algorithm, resolving a conjecture by Hunziker et al. [HMP+03]. Next, we present positive and negative results towards the rather general problem of partition of which both exact learning and computing a binary property are special cases. Finally, we derive an improved lower bound on the number of quantum examples required for PAC learning. (2) In Chapter 4, we consider the problem of unions of high dimensional rectangles over the domain [b]n using membership queries and uniform quantum examples. These classes oral generalizations of classes of DNF formulae over {0,1}n that have been extensively studied in the theory literature. (3) In Chapter 5, we develop quantum algorithms for and testing juntas (Boolean functions that depend on a few variables) and sparse functions. These algorithms are based on the quantum subroutine due to Bshouty and Jackson [BJ99] that enables sampling from the Fourier spectrum.
Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.
Over the course of the last seven decades the world of computing has taken revolutionary reformations in the scope of classical computing. Classical computers manipulate ones and zeroes to crunch through operations given to them by users. An innovative strategy known as quantum computing leverages the concepts of quantum physics to solve issues that are too complex for conventional computers to handle. Two of the domains of science that are now progressing the fastest are theoretical machine learning and quantum computing theory. In recent years, researchers have begun examining how classic machine learning techniques may be improved by quantum computing. Hybrid techniques that integrate conventional and quantum algorithms are part of quantum machine learning. Instead of using standard data, quantum techniques may be utilized to examine quantum states. However, quantum algorithms have the potential to greatly expand current data science techniques. In this paper we review the contribution carried out by various researchers in the field of Quantum Machine Learning and later we look at certain techniques associated with it for its use.
Machine learning is frequently listed among the most promising applications for quantum computing. This is in fact a curious choice: Today's machine learning algorithms are notoriously powerful in practice, but remain theoretically difficult to study. Quantum computing, in contrast, does not offer practical benchmarks on realistic scales, and theory is the main tool we have to judge whether it could become relevant for a problem. In this perspective we explain why it is so difficult to say something about the practical power of quantum computers for machine learning with the tools we are currently using. We argue that these challenges call for a critical debate on whether quantum advantage and the narrative of 'beating' classical machine learning should continue to dominate the literature the way it does, and highlight examples for how other perspectives in existing research provide an important alternative to the focus on advantage.