Source-linked AI summary
Optimal Quantum-Classical Separations for Exact Learning
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
TL;DR
The paper asks how classical and quantum query complexities for exact learning compare. It constructs concept classes that combine Grover search and Bernstein–Vazirani, refuting a longstanding conjecture with a cubic-logarithmic deterministic separation.
Problem
The paper asks what the optimal relationship is between classical and quantum query complexity for exact learning.
Source: §1 · p. 2Method
The construction hides a Bernstein–Vazirani-amenable object at one of many locations, making classical costs multiply while quantum costs add.
Source: §1.1.1 · p. 3Results
There exists a concept class with Q(C) = ω(1) and D(C) = Ω(Q(C)^3 log N), refuting the conjectured classical-versus-quantum bound.
Source: §1 · p. 3Takeaways & Limitations
The results characterize the optimal relationship between classical and quantum learning in both deterministic and randomized settings, up to constant factors.
Source: §1 · p. 3The new combinatorial-measure bound is randomized and replaces ETD(C) with the potentially smaller quantity fETD(C).
Source: §1.3.2 · p. 12
Abstract
from arXiv · showhide
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)=\Omega\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=\Omega(\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.
1 Introduction
The introduction asks how classical and quantum query complexities for exact learning relate, then presents constructions that refute a longstanding conjecture and establish an optimal relationship up to constant factors.
Background
- Exact learning identifies an unknown Boolean concept through membership queries, with deterministic, randomized, and bounded-error quantum query complexities denoted D(C), R(C), and Q(C).A classical membership query at x returns the target concept's value at x.Source: §1 · p. 2
- Grover search gives a quadratic randomized-versus-quantum separation for point functions, while Fourier sampling learns parity functions with one quantum query versus O(log N) randomized queries.These canonical examples motivated the search for further separations that account for domain size.Source: §1 · p. 2
Main result
- The paper refutes the conjecture that classical learning requires O(Q(C)^2 + Q(C) log N) queries and establishes an optimal classical–quantum relationship up to constant factors.The introduction identifies the conjecture as two decades old and attributes it to Atıci and Servedio.Source: §1 · p. 3
- There exists a concept class with Q(C) = ω(1) and D(C) = Ω(Q(C)^3 log N).This deterministic separation matches the upper bound of Servedio and Gortler [SICOMP'04], as described in the paper context.Source: §1 · p. 3
1.1 Deterministic separation
The deterministic construction hides a bilinear form in one of many blocks: quantumly, the block can be found with Grover search and its matrix recovered with Bernstein–Vazirani, while deterministic learners face a much larger query cost.
1.1.1 High-level overview
- The construction hides a Bernstein–Vazirani-amenable bilinear form at one of q^2 locations, so classical costs multiply while quantum costs add.Classical queries reveal one constraint at a time; quantum queries can access many coordinates simultaneously.Source: §1.1.1 · p. 3
- D(C) = Ω(q^4) while Q(C) = O(q), yielding D(C) = Ω(Q(C)^3 log N) because log N = Θ(q).Here N = q^2 2^(q^2), and the class has q^2 possible blocks.Source: §1.1.1 · p. 3
1.1.2 Quantum and classical bounds
- After locating the hidden block, the quantum learner recovers each matrix column with one Bernstein–Vazirani query, using q additional queries in total.Amplitude amplification locates the block with O(q) queries.Source: §1.1.2 · p. 4
Deterministic lower bound.
- Fewer than q^4 deterministic queries leave some block with fewer than q^2 queries, whose constraints admit a nonzero matrix consistent with the all-zero transcript.Thus the transcript remains consistent with both the all-zero concept and a concept with a hidden block.Source: Deterministic lower bound · pp. 4–5
1.2 Randomized separation
The section constructs a concept class whose randomized query complexity is cubic in the parameter, while quantum learning uses linear queries. Randomized lower bounds hide both the marked block addresses and the slope; a cheat sheet lets the quantum learner recover the remaining polynomial.
1.2.1 High-level overview
- The earlier deterministic construction does not yield a randomized separation: random queries find its hidden block, after which q^2 queries recover A, giving R(C) = O(q^2).The same class has D(C) = Ω(q^4).Source: §1.2.1 · p. 5
- A polynomial of degree t needs a different inner problem from Bernstein–Vazirani to retain a one-versus-t quantum-classical gap with a polynomial-size domain.The construction turns to a hidden-line problem over a finite field.Source: §1.2.1 · p. 5
- Each block hides one marked address among t^2 choices, and t blocks with distinct hidden inputs suggest a randomized cost of Ω(t^3).The address is a truncated polynomial value, Ptrunc(c + xs).Source: §1.2.1 · p. 6, Figure 1 · p. 7
- Random degree-t polynomial coefficients make values at any t distinct inputs independent and uniform, keeping a new marked address unpredictable.This is the construction’s first device for establishing the randomized lower bound.Source: §1.2.1 · p. 6
- With fewer than t distinct underlying inputs exposed, polynomial values remain independent and uniform, while collisions among those inputs are unlikely to reveal the slope.Source: §1.2.1 · p. 6
1.2.2 Quantum and classical bounds
- After recovering the slope s, the quantum learner uses the uniquely active cheat sheet to recover P’s coefficients, completing learning with O(t) queries.The active sheet contains Hadamard encodings of the coefficients, each recoverable with one query.Source: §1.2.1 · p. 6, §1.2.2 · p. 8
- For D = ⌊t^3/10⌋, success is below 2/3 for sufficiently large t, yielding a randomized lower bound of Ω(t^3) by Yao’s principle.The construction’s randomized separation refutes Conjecture 1.3.Source: §1.2.1 · p. 5, §1.2.2 · p. 10
- Q(Ct) = Θ(t), log N = Θ(log Q(Ct)), and the construction matches the general simulation upper bound.Its domain has N = Θ(t^14) coordinates and |Ct| = t^6(t+1).Source: §1.2.2 · p. 10
1.3 Other results
The section asks whether learning a concept can be matched by a Boolean decision, and whether combinatorial measures of exact learning align after fractionalization. It gives affirmative quantum Booleanization for every promise domain and relates fractional measures to quantum and classical query bounds.
1.3.1 Booleanization of quantum learnability
- Every concept class admits a Boolean decision whose quantum query complexity matches the complexity of learning the class, including on arbitrary promise domains.The corresponding statement for randomized query complexity is false in a strong sense.Source: §1.3.1 · p. 11
1.3.2 A new combinatorial measure
- Fractionalizing the splitting parameter and extended teaching dimension makes their distinction disappear, paralleling the collapse of fractional block sensitivity and certificate complexity.The analogy is natural because a specifying set plays the role of a certificate.Source: §1.3.2 · p. 11
- The fractional extended teaching dimension captures, up to constant factors, the same combinatorial quantity as the splitting parameter underlying the Servedio-Gortler quantum lower bound.The result refines a classical lower bound using fγ and refines the randomized simulation of Arunachalam et al. [ACL+21, Theorem 10].Source: §1.3.2 · p. 12
- The new randomized bound differs from Hegedűs's deterministic bound and replaces ETD(C) with the potentially smaller, more refined fETD(C).Its framework is inspired by [ACL+21, Theorem 10].Source: §1.3.2 · p. 12
2.1 Warm up
The warm-up construction uses membership queries to learn a hidden binary matrix. Grover search and Bernstein-Vazirani give a quantum learning procedure, while a Yao-style argument establishes a classical lower bound; setting the parameters equal yields a separation.
2.1 Warm up
- The quantum learner recovers each matrix row by coherently Grover-searching for Az and then applying Bernstein-Vazirani to the resulting phase oracle.The search is over 2^(m-i+1) candidates for row i, with a unique correct value.Source: §2.1 · pp. 13–14
- Under the uniform matrix distribution, each nonredundant query answered 1 increases the determined subspace dimension, limiting each transcript to at most ℓ such answers.The decision-tree argument and Yao's minimax principle establish the randomized lower bound.Source: §2.1 · p. 14
- For ℓ=m, the class has domain size N = 2^(2m), so log N = 2m, and the quantum and classical bounds yield a separation.The section presents this construction as a simpler refutation of the Atıci-Servedio conjecture.Source: §2.1 · pp. 13–14
2.2 The concept class
The class encodes a polynomial and a hidden slope across block and cheat-sheet parts: the slope selects the active sheet, which stores the polynomial coefficients. The useful facts establish that the encoding is injective and that evaluations at distinct inputs have independent truncated values.
2.2 The concept class
- Each concept cP,s has a block part with one marked address per block and a cheat-sheet part where only sheet s is active and its rows encode P's coefficients.The marked address in each block is Ptrunc(c + xs); the active sheet's jth row is the linear function determined by coefficient aj.Source: §2.2 · p. 15, Figure 3 · p. 16
2.2.1 Useful facts
- The encoding (P, s) ↦ cP,s is injective, giving the class size |Ct| = t^(6(t+1)).The polynomial has t independently chosen coefficients in Ft6, and s has t6 possible values.Source: §2.2.1 · p. 17
- For any r ≤ t distinct inputs, the values Ptrunc(y1), …, Ptrunc(yr) are independent and uniform in {0,1}^(2 log t).This follows from polynomial interpolation and the uniformity of truncation.Source: §2.2.1 · pp. 16–17
2.3 Quantum upper bound
The quantum learner first recovers the hidden slope from the block part and then learns the polynomial from the active cheat sheet. This takes O(t) membership queries and succeeds with bounded error.
2.3 Quantum upper bound
- A Fourier sample determines s whenever β ≠ 0; the learner recovers s with probability at least 1 − 1/t.Once s is known, the learner identifies the active cheat sheet.Source: §2.3 · p. 19
- Each active-sheet row is a Bernstein-Vazirani instance whose hidden string is one coefficient aj, so one quantum membership query recovers that coefficient exactly.Repeating for j = 0, …, t−1 recovers all coefficients of P.Source: §2.3 · p. 19
- Q(Ct) = O(t): the learner uses O(t) queries to recover s, then t Bernstein-Vazirani queries to recover all coefficients of P, with failure probability at most 1/t.The only possible failure is a Fourier sample with β = 0.Source: §2.3 · p. 19
2.4 Randomized lower bound
The randomized lower bound uses Yao’s minimax principle and three hybrid experiments to show that learners making fewer than order t^3 queries cannot identify the target with probability at least 2/3.
2.4 Randomized lower bound
- The proof samples the hidden slope and polynomial coefficients uniformly, then compares the learner’s real execution with three simpler experiments that progressively remove dependence on the slope.If D ≪ t^3, the final experiment is easy to analyze because its transcript is independent of the hidden slope.Source: §2.4 · pp. 19–20
2.4.1 Hybrid 1
- In Hybrid 1, cheat-sheet queries are answered with 0, reducing success in the real experiment to querying the active sheet or outputting its slope.The real and modified executions agree until the active sheet is queried.Source: §2.4 · p. 20, §2.4.1 · p. 21
2.4.2 Hybrid 2
- Hybrid 2 replaces the truncated polynomial labels with a random function, with only a small change in transcript probabilities for learners making D ≪ t^3 queries.The replacement is justified because each block query tests whether a function value equals one specified address, despite the learner possibly querying more than t inputs.Source: §2.4 · p. 20, §2.4.2 · p. 22
2.4.3 Hybrid 3
- Hybrid 3 assigns independent marked addresses to blocks, making the transcript independent of the slope except when distinct queried blocks collide on a hidden input.The Hybrid 2 and Hybrid 3 transcript distributions differ by at most the collision bound stated in Lemma 2.11.Source: §2.4.3 · p. 24
2.4.4 Putting hybrids together
- Combining the hybrid bounds makes every deterministic learner using at most t^3/10 queries succeed with probability below 2/3 under the chosen distribution.Yao’s minimax principle then yields R(Ct) = Ω(t^3).Source: §2.4.4 · p. 25
2.4 Putting hybrids together
- R(Ct) = Ω(t^3): for all sufficiently large t, Yao’s principle gives a randomized query lower bound from the three-hybrid analysis.At D = ⌊t^3/10⌋, the success probability is less than 2/3.Source: §2.4 · p. 20, §2.4.4 · p. 25
2.5 Putting it all together
The section relates the constructed class Ct’s quantum query complexity to its domain size, then applies the randomized lower bound to establish a separation.
2.5 Putting it all together
- Theorem 1.5 asserts a separation for a concept class with quantum query complexity growing without bound and a randomized lower bound.The supplied theorem statement is truncated after “R(C) = Ω”.Source: §2.5 · p. 26
- |Ct| = t^6(t + 1) and Nt = Θ(t^14), as used to relate the domain size to the quantum complexity.The passage also invokes the standard quantum lower bound for exact learning [SG04, Theorem 10].Source: §2.5 · p. 26
- Q(Ct) = Θ(t), and log Nt = Θ(log Q(Ct)), combining the quantum upper bound with the class’s domain-size relation.The proof then applies the randomized lower bound for Ct to obtain the theorem’s separation.Source: §2.5 · p. 26
3 Optimal quantum-deterministic separation
The section constructs a class combining a hidden location with a bilinear-form concept, yielding an O(q) quantum learner and a matching cubic-log deterministic separation.
3.1 The concept class
- The class hides a nonzero bilinear form x⊤Ay in one of q^2 blocks, while all other blocks are identically zero.The hidden block is indexed by b and the unknown nonzero matrix is A.Source: §3.1 · p. 26
3 Optimal quantum-deterministic separation
- The construction combines Grover search and Bernstein-Vazirani: quantumly the costs add, while deterministic queries must rule out candidate blocks one at a time.The section’s summary describes each zero answer within a block as imposing only one linear constraint on A’s q^2 entries.Source: §3.1 · p. 26
3.2 Quantum upper bound
- The quantum learner first finds the unique nonzero block using O(q) queries, then recovers A with Bernstein-Vazirani queries, for O(q) total.For each column Aej, one Bernstein-Vazirani query recovers it exactly.Source: §3.2 · pp. 26–27
3.3 Deterministic lower bound
- Fewer than q^4 deterministic queries leave some block with fewer than q^2 zero-answer constraints, allowing a nonzero matrix consistent with those answers.That hidden-block concept and the all-zero concept then produce the same transcript, so the learner cannot identify both correctly.Source: §3.3 · p. 27
3.4 Putting it all together
- D(Cq) ≥ q^4 and Q(Cq) = O(q), with log Nq = Θ(q), establish D(Cq) = Ω(Q(Cq)^3 log N).This matches the general deterministic simulation upper bound of Servedio and Gortler [SG04, Theorem 1] for this family.Source: §3.4 · pp. 27–28
4 Further results
This section develops further relationships between exact-learning complexity and Boolean decision complexity, including a characterization of quantum learning complexity and the possibility that randomized Booleanization is easier than learning. It also introduces fractional combinatorial parameters, derives an expected-depth bound, and combines earlier results to obtain Theorem 1.6.
4.1 Booleanization of exact learning
- Every concept class admits a Boolean decision whose quantum query complexity matches exact learning up to a constant factor.The decision asks whether the unknown concept belongs to a selected subset of the class.Source: §4.1 · pp. 28–29
- For every integer m ≥ 2, there is a concept class C_m ⊆ {0,1}^{2m} of size m with Rbool(C_m) = 1, while R(C_m) = Ω(log m).Source: §4.1 · p. 29
4.2.1 Existing parameters
- The existing parameters satisfy DEN(C) ≤ 1/gamma(C) ≤ 2 DEN(C) and 1/gamma(C) = O(ETD(C)).The splitting parameter captures the fraction of a remaining consistent set eliminated by a query, regardless of its answer.Source: §4.2.1 · p. 30
4.2.2 Fractional measures
- The fractional relaxations satisfy 1/gamma(C) ≤ 1/fgamma(C), fETD(C) ≤ ETD(C), and fETD(C) ≤ 1/fgamma(C) ≤ 2fETD(C).They generalize the splitting and teaching-dimension formulations by allowing distributions with no atom above 1/2 and nonnegative coordinate weights.Source: §4.2.2 · pp. 31, 33
4.2.3 Bounds in terms of fractional measures
- The fractional extended teaching dimension lower-bounds quantum query complexity quadratically for every concept class.The proof applies the positive-weight adversary bound to a distribution over concepts with no individual mass greater than 1/2.Source: §4.2.3 · pp. 33–34
- An entropy-based, Yao-style decision tree yields a randomized upper bound in terms of fETD(C), stopping at posterior mass 5/6 and querying to maximize worst-case posterior-mass decrease.The analysis bounds expected tree depth before truncation to obtain a bounded-error decision tree.Source: §4.2.3 · pp. 34–35
- At internal nodes, the query decreases conditional entropy in expectation by at least δ; leaf transcripts incur no further decrease.The proof averages these decreases over transcripts to derive the expected-depth bound.Source: §4.2.3 · p. 36
- The expected-depth bound involves fETD(C), log(fETD(C) + 1), and log |C|; Lemma 4.9 and Theorems 4.11 and 4.12 yield Theorem 1.6.Source: §4.2.3 · p. 36