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:2609.38073

Optimal Quantum-Classical Separations for Exact Learning

Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande

quant-phcs.CCcs.LGSubmitted Sep 29, 2026• Announced Sep 30, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks how much quantum membership queries can reduce the cost of exactly identifying an unknown concept in $\mathcal C\subseteq\{0,1\}^N$. It constructs families attaining the known general classical-simulation bounds, refuting the conjecture $\mathsf R(\mathcal C)=O(\mathsf Q(\mathcal C)^2+\mathsf Q(\mathcal C)\log N)$. The randomized separation has $\mathsf Q=\Theta(t)$, $\mathsf R=\Omega(t^3)$, and $N=\Theta(t^{14})$, attaining $\mathsf R=\Omega(\mathsf Q^3\log N/\log\mathsf Q)$. Its Boolean oracle hides truncated polynomial values at unique marked addresses, with values constant along lines of an unknown slope. Coherent Grover search and Fourier sampling recover the slope; a slope-indexed auxiliary “cheat sheet” then allows recovery of the polynomial coefficients. The classical lower bound uses Yao’s principle and hybrids replacing polynomial values by random-function values and then independent block labels. A supporting lemma bounds how well adaptive equality queries distinguish limited independence from full randomness. A separate construction hides a bilinear form in one of $q^2$ blocks, giving $\mathsf Q=\Theta(q)$, $\mathsf D=\Omega(q^4)$, and $\log N=\Theta(q)$, attaining $\mathsf D=\Omega(\mathsf Q^3\log N)$. Grover search and Bernstein–Vazirani give the quantum algorithm; linear constraints give the deterministic lower bound. This construction does not yield the randomized separation: randomness reduces its classical cost to $O(q^2)$. Additional results show that every concept class has a Boolean decision matching its quantum identification complexity up to constants, and relate fractional teaching and splitting parameters to query complexity. The tight randomized example occupies the regime $\log N=\Theta(\log\mathsf Q)$; the bounds concern query complexity.

Little sign of AI-generated textAI use disclosed
We used GPT-5.6 in the process of discovering most of our results, but notably the construction underlying our separation

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

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

Two new results about quantum exact learning

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +2 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(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.

arXiv:1810.00481•Quantum•Nov 24, 2021•23 citations

Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Andris Ambainis, Jānis Iraids, Martins Kokainis

We study how large the certificate complexity ${C}(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies ${R}_1(f) = Θ(\sqrt{{C}(f)})$. This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function $F$ with bounded-error quantum query complexity ${Q}(F) = \widetilde O({C}(F)^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are $\widetilde O(\sqrt{{C}(F)})$. We also prove matching lower bounds for these two measures on $F$.

quant-pharXiv:2609.11664•Sep 11, 2026•1 citation

Quantum Query Complexity for Nonstandard Oracles with Tight Bounds and Tradeoffs Beyond Grover

Yalla Jnan Devi Satya Prasad

Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.

•Dec 19, 2025•0 citations

Equivalences and Separations Between Quantum and Classical Learnability

Rocco A. Servedio, Steven J. Gortler

We consider quantum versions of two well-studied models of learning Boolean functions: Angluin's model of exact learning from membership queries and Valiant's probably approximately correct (PAC) model of learning from random examples. For each of these two learning models we establish a polynomial relationship between the number of quantum or classical queries required for learning. These results contrast known results that show that testing black-box functions for various properties, as opposed to learning, can require exponentially more classical queries than quantum queries. We also show that, under a widely held computational hardness assumption (the intractability of factoring Blum integers), there is a class of Boolean functions which is polynomial-time learnable in the quantum version but not the classical version of each learning model. For the model of exact learning from membership queries, we establish a stronger separation by showing that if any one-way function exists, then there is a class of functions which is polynomial-time learnable in the quantum setting but not in the classical setting. Thus, while quantum and classical learning are equally powerful from an information theory perspective, the models are different when viewed from a computational complexity perspective.

SIAM Journal on Computing•Jan 1, 2004•127 citations

Pseudo-deterministic Quantum Algorithms

Hugo Aaronson, Tom Gur, Jiawei Li

We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is $O(1)$ but is maximally hard for pseudo-deterministic quantum algorithms ($Ω(N)$ query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms ($O(\log(N))$ vs. $Θ(\sqrt{N})$), while the randomized query complexity is $O(1)$. Complementing these separations, we show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., $D(R) = \tilde O(psQ(R)^5)$. On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, $k$-sum, and graph collision.

quant-pharXiv:2602.17647•Leibniz international proceedings in informatics•Feb 20, 2026•2 citations
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 [ \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.
The paper asks how much quantum membership queries can reduce the cost of exactly identifying an unknown concept in C⊆{0,1}N\mathcal C\subseteq\{0,1\}^NC⊆{0,1}N. It constructs families attaining the known general classical-simulation bounds, refuting the 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).
The randomized separation has Q=Θ(t)\mathsf Q=\Theta(t)Q=Θ(t), R=Ω(t3)\mathsf R=\Omega(t^3)R=Ω(t3), and N=Θ(t14)N=\Theta(t^{14})N=Θ(t14), attaining R=Ω(Q3log⁡N/log⁡Q)\mathsf R=\Omega(\mathsf Q^3\log N/\log\mathsf Q)R=Ω(Q3logN/logQ). Its Boolean oracle hides truncated polynomial values at unique marked addresses, with values constant along lines of an unknown slope. Coherent Grover search and Fourier sampling recover the slope; a slope-indexed auxiliary “cheat sheet” then allows recovery of the polynomial coefficients. The classical lower bound uses Yao’s principle and hybrids replacing polynomial values by random-function values and then independent block labels. A supporting lemma bounds how well adaptive equality queries distinguish limited independence from full randomness.
A separate construction hides a bilinear form in one of q2q^2q2 blocks, giving Q=Θ(q)\mathsf Q=\Theta(q)Q=Θ(q), D=Ω(q4)\mathsf D=\Omega(q^4)D=Ω(q4), and log⁡N=Θ(q)\log N=\Theta(q)logN=Θ(q), attaining D=Ω(Q3log⁡N)\mathsf D=\Omega(\mathsf Q^3\log N)D=Ω(Q3logN). Grover search and Bernstein–Vazirani give the quantum algorithm; linear constraints give the deterministic lower bound. This construction does not yield the randomized separation: randomness reduces its classical cost to O(q2)O(q^2)O(q2).
Additional results show that every concept class has a Boolean decision matching its quantum identification complexity up to constants, and relate fractional teaching and splitting parameters to query complexity. The tight randomized example occupies the regime log⁡N=Θ(log⁡Q)\log N=\Theta(\log\mathsf Q)logN=Θ(logQ); the bounds concern query complexity.
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 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 how large the certificate complexity C(f){C}(f)C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function fff whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)){R}_1(f) = Θ(\sqrt{{C}(f)})R1​(f)=Θ(C(f)​). This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function FFF with bounded-error quantum query complexity Q(F)=O~(C(F)1/4){Q}(F) = \widetilde O({C}(F)^{1/4})Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O~(C(F))\widetilde O(\sqrt{{C}(F)})O(C(F)​). We also prove matching lower bounds for these two measures on FFF.
Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
We consider quantum versions of two well-studied models of learning Boolean functions: Angluin's model of exact learning from membership queries and Valiant's probably approximately correct (PAC) model of learning from random examples. For each of these two learning models we establish a polynomial relationship between the number of quantum or classical queries required for learning. These results contrast known results that show that testing black-box functions for various properties, as opposed to learning, can require exponentially more classical queries than quantum queries. We also show that, under a widely held computational hardness assumption (the intractability of factoring Blum integers), there is a class of Boolean functions which is polynomial-time learnable in the quantum version but not the classical version of each learning model. For the model of exact learning from membership queries, we establish a stronger separation by showing that if any one-way function exists, then there is a class of functions which is polynomial-time learnable in the quantum setting but not in the classical setting. Thus, while quantum and classical learning are equally powerful from an information theory perspective, the models are different when viewed from a computational complexity perspective.
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1)O(1)O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N)Ω(N)Ω(N) query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log⁡(N))O(\log(N))O(log(N)) vs. Θ(N)Θ(\sqrt{N})Θ(N​)), while the randomized query complexity is O(1)O(1)O(1). Complementing these separations, we show that for any total problem RRR, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., D(R)=O~(psQ(R)5)D(R) = \tilde O(psQ(R)^5)D(R)=O~(psQ(R)5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, kkk-sum, and graph collision.