We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k -Fourier-sparse n -bit Boolean function from O(k1.5(logk)2) uniform quantum examples for that function. This improves over the bound of Θ~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our O~(k1.5) upper bound by proving an improvement of Chang's lemma for k -Fourier-sparse Boolean functions. Second, we show that if a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned using O(Q2logQlog|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a logQ -factor.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k -Fourier-sparse n -bit Boolean function from O(k1.5(logk)2) uniform quantum examples for that function. This improves over the bound of Θ~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our O~(k1.5) upper bound by proving an improvement of Chang's lemma for k -Fourier-sparse Boolean functions. Second, we show that if a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned using O(Q2logQlog|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a logQ -factor.
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most k nonzero Fourier coefficients. We give a learner with near-optimal O(k) sample complexity independent of the input length n. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log2k) upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk) by combining known sparse-recovery and lower-bound results.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform quantum examples for that function. This improves over the bound of Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang’s lemma for sparse Boolean functions. Second, we show that if a concept class {C} can be exactly learned using Q quantum membership queries, then it can also be learned using O ({Q^2}/{log Q} * log|C|) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.
We study exact learning with membership queries for concept classes C⊆{0,1}N, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted D(C), R(C), and Q(C), respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture R(C)=O(Q(C)2+Q(C)logN). We first refute this conjecture by constructing concept classes C and C′ satisfying R(C)=Ω(logQ(C)Q(C)3logN)andD(C′)=Ω(Q(C′)3logN). The first bound matches the upper bound of Arunachalam et al.~[Quantum'21] up to constant factors, while the second matches the upper bound of Servedio and Gortler~[SICOMP'04]. In particular, this shows that the saving in the randomized upper bound of Arunachalam et al. fundamentally relies on randomness. Apart from characterizing the optimal relationship between classical and quantum query complexity, our results are the first to show that quantum speedups for learning can go beyond the Grover and Bernstein-Vazirani paradigms.
Research manuscript with PDF, LaTeX and review records. An algorithm exactly recovers every k-Fourier-sparse Boolean function with success at least 2/3 using O(k log^3(2k)) independent supplied uniform quantum examples and fixed-polynomial total computation and live space. Fresh residual estimates construct a queryable sign-majority hypothesis; known-function Fourier search and original-target certification contract missing Fourier energy. The theorem uses no target membership query or state-preparation inverse. All samples, adaptive refits and exact rational bit costs are charged. This complements Ye's smaller sample bound with a polynomial computational guarantee. No optimal logarithmic factor, practical implementation, noise robustness, exhaustive novelty, independent peer review, formal certification or BPP/BQP result is claimed. OpenAI Codex assisted derivation, source comparison, drafting and internal checking. Separate model reviews were obtained through Grok, Claude and AGY (configured with Gemini), with findings dispositioned in the archive. These are AI reviews, not independent human peer review.
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.
Linear threshold functions (LTFs) are {−1,1}-valued functions fw,θ(x)=sgn(⟨w,x⟩−θ), where w∈Rn has unit norm, θ∈R, and x∈Rn or {−1,1}n. If θ=0, the LTF is homogeneous, denoted fw=fw,0. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating fw,θ(x) at any chosen x∈Rn, we learn an LTF with classification error at most ε under the standard Gaussian distribution using O(log(n/ε)) queries and O(n) other gates. Classically, Ω(nlog(1/ε)) queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF fw over {−1,1}n whose k nonzero weights are equal and positive is Majority on the support of w. We identify this hidden support exactly using O(logk) queries, exponentially improving Belovs' O(k1/4) upper bound. Our algorithm uses O(nlognlogk) gates and has O(lognlogk) non-oracle depth. Classical algorithms require Ω(klog(n/k)) queries. (3) Suppose a unitary U prepares discretized Gaussian quantum examples, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩dx. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most ε under the Gaussian distribution using O(n1/4/ε) applications of U and U† and O(εn5/4+ε2n) other gates. Classically, Ω(n/ε) examples are needed, giving a quartic quantum speedup in n. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.