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.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.38403Oct 1, 20260 citations

Quantum DNF Learnability Revisited

Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami

We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^{3}/ε+ s^{2}/ε^{2})$ , where $s$ is the size of DNF formula and $ε$ is the PAC error accuracy. If $s$ and $1/ε$ are comparable, this gives a modest improvement over a previously known classical query complexity of $\tilde{O}(ns^{2}/ε^{2})$ . We also show a lower bound of $Ω(s\log n/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF of size $s$ with $n$ inputs under the uniform distribution.We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of $\tilde{O}(s^{3}/ε+ s^{2}/ε^{2})$, where $s$ is the size of DNF formula and $ε$ is the PAC error accuracy. If $s$ and $1/ε$ are comparable, this gives a modest improvement over a previously known classical query complexity of $\tilde{O}(ns^{2}/ε^{2})$. We also show a lower bound of $Ω(s\log n/n)$ on the query complexity of any quantum PAC algorithm for learning a DNF of size $s$ with $n$ inputs under the uniform distribution.

arXiv:quant-ph/0202066Feb 12, 20020 citations

Improved Bounds on Quantum Learning Algorithms

Alp Atıcı, Rocco A. Servedio

arXiv:quant-ph/0411140Quantum Information ProcessingOct 18, 200567 citations

Quantum query algorithms and lower bounds

Andris Ambainis

Springer eBooksNov 2, 200726 citations

Characterizing Algorithmic Efficiencies through Concentration

Hung Pham

Understanding inherent bottlenecks to efficient algorithm design lies at the heart of computer science. This question is significant both in the classical computing domain as well as in the emerging context of quantum computing. In this thesis, my goal is to characterize bottlenecks in designing efficient algorithms through the lens of a parameter called concentration of functions, starting with the domain of quantum information. My primary focus is probabilistically approximately correct (PAC) learning. I chose this domain since it allows us to approach the important subject of supervised learning in a rigorous and principled manner. For PAC learning, I propose a quantum algorithm to learn the class of concentrated Boolean functions with complexity $ O(\frac{M}{\epsilon^2})$ which offers an advantage over the best known classical PAC algorithms with complexity $\tilde{O}(n^2M)$ , where M denotes the number of the concentration terms. I also show a lower bound $\Omega(M)$ to PAC learn this class of functions in distribution-independent settings. All this work is done in the context of the standard query model for PAC learning where the complexity measure is the number of queries, dubbed query complexity. I extend this work to include the learning model where functions are learned without any error, which is often called exact learning, and prove a query complexity lower bound of $\Omega(\frac{\epsilon \log M}{n} 2^n)$ in exact learning the class of concentrated Boolean functions. In the next part of the thesis, I focus my work on classical algorithms and explore a combinatorial counterpart of concentration called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel algorithm in polynomial time using a quasi-polynomial number of processors for the Graph Isomorphism problem. My work builds on Babai’s celebrated quasi-polynomial algorithm and is work-preserving. The idea behind the parallelization explores the symmetry of the input structure for easier parallelization.Understanding inherent bottlenecks to efficient algorithm design lies at the heart of computer science. This question is significant both in the classical computing domain as well as in the emerging context of quantum computing. In this thesis, my goal is to characterize bottlenecks in designing efficient algorithms through the lens of a parameter called concentration of functions, starting with the domain of quantum information. My primary focus is probabilistically approximately correct (PAC) learning. I chose this domain since it allows us to approach the important subject of supervised learning in a rigorous and principled manner. For PAC learning, I propose a quantum algorithm to learn the class of concentrated Boolean functions with complexity $ O(\frac{M}{\epsilon^2})$ which offers an advantage over the best known classical PAC algorithms with complexity $\tilde{O}(n^2M)$, where M denotes the number of the concentration terms. I also show a lower bound $\Omega(M)$ to PAC learn this class of functions in distribution-independent settings. All this work is done in the context of the standard query model for PAC learning where the complexity measure is the number of queries, dubbed query complexity. I extend this work to include the learning model where functions are learned without any error, which is often called exact learning, and prove a query complexity lower bound of $\Omega(\frac{\epsilon \log M}{n} 2^n)$ in exact learning the class of concentrated Boolean functions. In the next part of the thesis, I focus my work on classical algorithms and explore a combinatorial counterpart of concentration called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel algorithm in polynomial time using a quasi-polynomial number of processors for the Graph Isomorphism problem. My work builds on Babai’s celebrated quasi-polynomial algorithm and is work-preserving. The idea behind the parallelization explores the symmetry of the input structure for easier parallelization.

Aug 1, 20210 citations

We describe a quantum PAC learning algorithm for DNF formulae under the uniform distribution with a query complexity of

\tilde{O}(s^{3}/ε+ s^{2}/ε^{2})

, where

s

is the size of DNF formula and

ε

is the PAC error accuracy. If

s

and

1/ε

are comparable, this gives a modest improvement over a previously known classical query complexity of

\tilde{O}(ns^{2}/ε^{2})

. We also show a lower bound of

Ω(s\log n/n)

on the query complexity of any quantum PAC algorithm for learning a DNF of size

s

with

n

inputs under the uniform distribution.

\tilde{O}(n^2M)

, where M denotes the number of the concentration terms. I also show a lower bound

\Omega(M)

to PAC learn this class of functions in distribution-independent settings. All this work is done in the context of the standard query model for PAC learning where the complexity measure is the number of queries, dubbed query complexity. I extend this work to include the learning model where functions are learned without any error, which is often called exact learning, and prove a query complexity lower bound of

\Omega(\frac{\epsilon \log M}{n} 2^n)

in exact learning the class of concentrated Boolean functions. In the next part of the thesis, I focus my work on classical algorithms and explore a combinatorial counterpart of concentration called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel algorithm in polynomial time using a quasi-polynomial number of processors for the Graph Isomorphism problem. My work builds on Babai’s celebrated quasi-polynomial algorithm and is work-preserving. The idea behind the parallelization explores the symmetry of the input structure for easier parallelization.