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

Two new results about quantum exact learning

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf

Published Nov 24, 2021• 23 citations
arXivHTMLPDF

Abstract

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(log⁡k)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(Q2log⁡Qlog⁡|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log⁡Q -factor.

DOI
10.22331/q-2021-11-24-587

Related papers

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

Zekun Ye

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 $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ 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.

quant-pharXiv:2610.17648•Oct 14, 2026•0 citations

Two New Results About Quantum Exact Learning

Srinivasan Arunachalam, Sourav Chakraborty, Troy J. Lee +6 more

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.

•Jan 1, 2019•13 citations

Optimal Quantum-Classical Separations for Exact Learning

Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande

We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted $\mathsf{D}(\mathcal C)$, $\mathsf{R}(\mathcal C)$, and $\mathsf{Q}(\mathcal C)$, respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture $$ \mathsf{R}(\mathcal C)=O(\mathsf{Q}(\mathcal C)^2+\mathsf{Q}(\mathcal C)\log N). $$ We first refute this conjecture by constructing concept classes $\mathcal C$ and $\mathcal C'$ satisfying \[ \mathsf{R}(\mathcal C)=Ω\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log N). \] 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.

quant-pharXiv:2609.38073•Sep 30, 2026•1 citation

Polynomial-Time Exact Learning of Fourier-Sparse Boolean Functions from Nearly Linear Quantum Samples

Daniel Fredriksen

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.

•Nov 10, 2026•0 citations

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

Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

Linear threshold functions (LTFs) are $\{-1,1\}$-valued functions $f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)$, where $w\in\mathbb R^n$ has unit norm, $θ\in\mathbb R$, and $x\in\mathbb R^n$ or $\{-1,1\}^n$. If $θ=0$, the LTF is homogeneous, denoted $f_w=f_{w,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 $f_{w,θ}(x)$ at any chosen $x\in\mathbb R^n$, we learn an LTF with classification error at most $\varepsilon$ under the standard Gaussian distribution using $O(\log(n/\varepsilon))$ queries and $\widetilde{O}(n)$ other gates. Classically, $Ω(n\log(1/\varepsilon))$ queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF $f_w$ 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(\log k)$ queries, exponentially improving Belovs' $O(k^{1/4})$ upper bound. Our algorithm uses $O(n\log n\log k)$ gates and has $O(\log n\log k)$ non-oracle depth. Classical algorithms require $Ω(k\log(n/k))$ queries. (3) Suppose a unitary $U$ prepares discretized Gaussian quantum examples, corresponding to $\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx$. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most $\varepsilon$ under the Gaussian distribution using $O(n^{1/4}/\sqrt{\varepsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})$ other gates. Classically, $Ω(n/\varepsilon)$ 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.

quant-pharXiv:2609.40331•Oct 1, 2026•0 citations
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(log⁡k)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(Q2log⁡Qlog⁡|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log⁡Q -factor.
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most kkk nonzero Fourier coefficients. We give a learner with near-optimal O~(k)\widetilde{O}(k)O(k) sample complexity independent of the input length nnn. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log⁡2k)O(k^{3/2}\log^2 k)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)Θ(nk)Θ(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\mathcal C\subseteq\{0,1\}^NC⊆{0,1}N, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted D(C)\mathsf{D}(\mathcal C)D(C), R(C)\mathsf{R}(\mathcal C)R(C), and Q(C)\mathsf{Q}(\mathcal C)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)log⁡N). \mathsf{R}(\mathcal C)=O(\mathsf{Q}(\mathcal C)^2+\mathsf{Q}(\mathcal C)\log N). R(C)=O(Q(C)2+Q(C)logN). We first refute this conjecture by constructing concept classes C\mathcal CC and C′\mathcal C'C′ satisfying R(C)=Ω ⁣(Q(C)3log⁡Nlog⁡Q(C))andD(C′)=Ω(Q(C′)3log⁡N). \mathsf{R}(\mathcal C)=Ω\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log N). 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}\{-1,1\}{−1,1}-valued functions fw,θ(x)=sgn(⟨w,x⟩−θ)f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)fw,θ​(x)=sgn(⟨w,x⟩−θ), where w∈Rnw\in\mathbb R^nw∈Rn has unit norm, θ∈Rθ\in\mathbb Rθ∈R, and x∈Rnx\in\mathbb R^nx∈Rn or {−1,1}n\{-1,1\}^n{−1,1}n. If θ=0θ=0θ=0, the LTF is homogeneous, denoted fw=fw,0f_w=f_{w,0}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)f_{w,θ}(x)fw,θ​(x) at any chosen x∈Rnx\in\mathbb R^nx∈Rn, we learn an LTF with classification error at most ε\varepsilonε under the standard Gaussian distribution using O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) queries and O~(n)\widetilde{O}(n)O(n) other gates. Classically, Ω(nlog⁡(1/ε))Ω(n\log(1/\varepsilon))Ω(nlog(1/ε)) queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF fwf_wfw​ over {−1,1}n\{-1,1\}^n{−1,1}n whose kkk nonzero weights are equal and positive is Majority on the support of www. We identify this hidden support exactly using O(log⁡k)O(\log k)O(logk) queries, exponentially improving Belovs' O(k1/4)O(k^{1/4})O(k1/4) upper bound. Our algorithm uses O(nlog⁡nlog⁡k)O(n\log n\log k)O(nlognlogk) gates and has O(log⁡nlog⁡k)O(\log n\log k)O(lognlogk) non-oracle depth. Classical algorithms require Ω(klog⁡(n/k))Ω(k\log(n/k))Ω(klog(n/k)) queries. (3) Suppose a unitary UUU prepares discretized Gaussian quantum examples, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩ dx\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx∫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 ε\varepsilonε under the Gaussian distribution using O(n1/4/ε)O(n^{1/4}/\sqrt{\varepsilon})O(n1/4/ε​) applications of UUU and U†U^\daggerU† and O~ ⁣(n5/4ε+nε2)\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})O(ε​n5/4​+ε2n​) other gates. Classically, Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) examples are needed, giving a quartic quantum speedup in nnn. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.