Unconditional Quantum PAC Learning Advantage in the Large Error Regime

Igor C. Oliveira

Source-linked AI summary

Unconditional Quantum PAC Learning Advantage in the Large Error Regime

Igor C. Oliveira

arXiv:2610.23268v1Oct 16, 2026cs.CCquant-ph

TL;DR

The paper asks whether quantum and classical learners can be separated for uniform-distribution PAC learning when agreement is only slightly above one half. It develops quantum learning algorithms and establishes an unconditional robust separation in this large-error regime, while an analogous separation in the small-error regime would imply NP ⊈ BPP.

Problem
The paper investigates whether polynomial-time learners can learn Boolean functions under the uniform distribution with only a small advantage over random guessing, a regime relevant to quantum learning separations and complexity lower bounds.
Source: §1 · p. 3
Method
The authors analyze a quantum learner’s sampled quadratic functions and use additional quantum random examples and running time to boost agreement and success probability.
Source: §1 · p. 4
Results
Theorem 1.5 establishes a robust unconditional super-polynomial separation: quantum learners use polynomial time and quantum random examples, while polynomial-time classical learners cannot achieve the same guarantee even with membership queries.
Source: §1.1 · p. 7
Takeaways & Limitations
The separation holds in the large-error regime, whereas an analogous robust separation in the small-error regime with classical circuit hypotheses would imply NP ⊈ BPP.
Source: §1 · p. 3, §1.1 · p. 7
An analogous robust separation at agreement 1/2 + λ(n), for λ(n) ≥ 1/poly(n), with classical circuit hypotheses would imply NP ⊈ BPP.
Source: §1.1 · p. 7

Abstract

from arXiv · show

We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $\lambda(n) = n^{-\omega(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $1/2+\lambda(n)$ with success probability at least $1-1/n^k$. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement $1/2 + \lambda(n)/n^k$ with success probability greater than $1/n^k$, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that $\mathsf{NP} \nsubseteq \mathsf{BPP}$.

1 Introduction

The paper establishes a robust quantum–classical learning separation for Boolean functions under the uniform distribution in the large-error regime, using quantum sampling techniques with quadratic hypotheses and amplification. It also situates the result among PAC-learning separations and notes that a similar robust separation in the small-error regime would imply NP ⊈ BPP.

1.1 Results

At advantage Ω(2^-n/2), a polynomial-time quantum learner using one quantum random example succeeds with probability above 1/2, whereas classical learners require Ω(2^n/2) membership queries to exceed that success threshold.The quantum learner outputs a deterministic classical circuit of size O(n^2).Source: §1 · p. 4, §1.1 · pp. 5–6

1.2 Techniques

The quantum method extends Fourier sampling from parities to quadratic hypotheses and uses interference to favor positively correlated hypotheses, with further examples and runtime boosting agreement and success probability.The amplified learner achieves advantage Ω(√m/2^n), failure probability O(1/m), and runtime m · poly(n).Source: §1 · p. 4, §1.1 · p. 5

1.1 Results

Classically surpassing success probability 1/2 at exponentially small advantage requires Ω(2^n/2) membership queries, regardless of running time; a computational lower bound for polynomial-size targets additionally assumes subexponentially secure one-way functions.The paper also states that the resulting quantum–classical PAC separation can be unconditional for arbitrary Boolean functions and conditional for a fixed polynomial-size circuit class.Source: §1.1 · p. 6
For every constructive λ in the stated range, a concept class admits polynomial-time quantum learning from quantum random examples, while classical polynomial-time learners with membership queries cannot match the robust agreement guarantee.If subexponentially secure one-way functions exist, the class can be chosen within polynomial-size circuits.Source: §1.1 · p. 7
A similar robust separation with classical circuit hypotheses at agreement 1/2 + λ(n), for λ(n) ≥ 1/poly(n), would imply NP ⊈ BPP.The paper relates this limitation to polynomial-time agnostic learning under DistNP ⊆ AvgBPP.Source: §1.1 · p. 7

1.2 Techniques

Classical learners can obtain correlation Ω(2^-n/2) without queries but have success probability at most 1/2; a 4-wise independent family yields a polynomial-size, zero-query learner with constant success probability no greater than 1/2.Limited independence reproduces the second- and fourth-moment calculations while keeping seeds and hypothesis circuits polynomial in size.Source: §1.2 · pp. 8–9
For random Boolean targets, q = o(N) classical queries cannot guarantee advantage Ω(N^-1/2) above 1/2: conditioned on the transcript, unseen labels remain unbiased.When the observed contribution is too small to reach the threshold, success requires a symmetric unseen contribution to be positive, with probability at most 1/2.Source: §1.2 · p. 9
A coherent reference branch makes quantum sampling favor positively correlated quadratic hypotheses: interference adds a term linear in signed correlation, unlike ordinary Fourier sampling.The quadratic family is 4-wise independent and has O(n^2)-size circuits; moment bounds and Paley–Zygmund yield correlation at least a fixed positive constant with probability above 1/2.Source: §1.2 · p. 10
Repeating the quantum sampler and taking a majority amplifies its pointwise bias, yielding correlation Ω(η) with failure probability O(η) using time and circuit size η^-1 poly(n).Pairwise independence across inputs lets the majority correlation concentrate around its positive mean.Source: §1.2 · p. 11
Padding reduces the inverse-superpolynomial-advantage separation to a core random function on d bits, with d = ω(log n) and d < n eventually.The quantum learner obtains the target advantage from the amplified learner; the classical transcript bound remains valid when hypotheses depend on padding bits.Source: §1.2 · p. 11
Quantum learning reaches advantage λ(n) with success at least 1 − 1/n^k, while no polynomial-time classical learner achieves advantage λ(n)/n^k with success greater than 1/n^k, even with membership queries.The construction pads targets so they depend on only d input bits; the classical lower bound controls the unseen core labels, and the quantum learner uses polynomially many examples.Source: §1.2 · pp. 11–12
Under subexponential one-way-function security, the separation transfers to polynomial-size circuit concepts by using pseudorandom functions and making correlation verification fit the security bound,.The quantum upper bound applies to every Boolean function; the reduced input dimension permits exhaustive correlation testing in the classical distinguisher reduction.Source: §1.2 · p. 12

1.3 Related Work

Prior work relates classical and quantum learning in distribution-free PAC and exact learning, while fixed-distribution parity learning and stronger quantum oracle access yield other advantages [AdW17, Section 5.3], [SSG24].Computational PAC separations also use assumptions such as factoring, discrete logarithm, or discrete cube roots, [LAT21], [JGM+24]; these differ from the unconditional large-error separation here.Source: §1.3 · pp. 12–13
Related separations include predictive learning of relations and quantum-memory settings, [HKP21], [CCHL22]; van Dam’s sampler biases signed correlation but outputs an exponential-size truth table [vD98].The present sampler instead produces a succinct classical hypothesis; its quadratic hypotheses connect to quadratic Goldreich–Levin algorithms [TW14], [CSBA+26, Theorem 1.5], [ADGG26, Theorem 1.3].Source: §1.3 · p. 13

2 Preliminaries

The preliminaries fix the uniform-distribution PAC setting and distinguish hypothesis agreement from learner success. They also introduce quantum random examples and the probability and independence tools used in the learning analysis.

2.1 Basic Notation

The notation section defines Boolean sign representations and relates agreement to correlation between the target and hypothesis.For a Boolean function h, its sign representation is H(x) = (−1)^h(x).Source: §2.1 · p. 14

2.2 Classical Learning Theory

PAC learning is considered under the uniform distribution, with success probability measuring whether the output hypothesis meets the required agreement with the target.The paper studies improper learners; a classical learner with membership queries can simulate uniform labeled examples.Source: §2.2 · p. 15

2.3 Quantum Learning Algorithms

A quantum random example is a coherent superposition of labeled inputs that can interfere under unitary transformations before measurement.The learners use copies of these states and make no quantum membership queries; their output is a deterministic classical Boolean circuit.Source: §2.3 · pp. 15–16

2.4 Probability

The Paley-Zygmund inequality converts moment bounds into a lower bound on the probability that a nonnegative random variable is not too small.The section includes a formulation and proof for later success-probability analysis.Source: §2.4 · p. 16

2.5 4-Wise Independence

A function family is k-wise independent when evaluations on any set of at most k distinct inputs are independent uniform bits.The analysis records moment bounds and a global sign-flip symmetry for 4-wise independent families.Source: §2.5 · pp. 17–18

2.6 Cryptography

A subexponentially secure one-way function is defined through inversion resistance against uniform randomized algorithms running in time at most 2^n^ε.The definition requires inversion success below the reciprocal of every positive polynomial for sufficiently large n.Source: §2.6 · p. 19

3 Quantum Learning Algorithms: Proof of Theorem 1.2

The proof section first establishes a classical baseline, then improves its success guarantee with a quantum algorithm. Both constructions use a suitable 4-wise independent function family.

3 Quantum Learning Algorithms: Proof of Theorem 1.2

Both the classical and quantum constructions rely on a suitable 4-wise independent function family.The section first describes the classical learner, then explains the quantum improvement.Source: §3 · p. 19
The initial classical learner has a weaker success-probability guarantee than the subsequent quantum algorithm.The classical construction is introduced first as a baseline for the quantum improvement.Source: §3 · p. 19
The proof strategy improves the learner's success probability beyond the classical baseline using a quantum algorithm.The passage does not specify the quantitative guarantee in this overview.Source: §3 · p. 19

3.1 Technical Background

The technical background constructs an efficient quadratic family with 4-wise independence and a global sign flip. It then uses that family for a classical zero-query learner whose success probability is at most one half.

3.1.1 Quadratic Functions: A Suitable 4-Wise Independent Family

The quadratic Boolean family is 4-wise independent, admits a global sign flip, and has hypotheses computable by deterministic circuits of size O(n^2).Its feature map is injective and efficiently computable with an efficiently computable inverse on its image.Source: §3.1.1 · pp. 19–21
The construction proves 4-wise independence by showing that every collection of at most four distinct feature vectors is linearly independent.A uniform seed then induces a uniform evaluation vector on those inputs.Source: §3.1.1 · p. 21

3.1.2 Derandomized Classical Learner with p⋆≤1/2

A randomized polynomial-time classical learner makes zero queries, samples a uniform seed, and outputs its associated deterministic circuit.For every target, its success probability is bounded by p⋆ ≤ 1/2.Source: §3.1.2 · pp. 21–22

3.2 The Correlation-Biased Quantum Sampler: Proof of Item 1

The quantum sampler encodes correlations into measurement amplitudes using a reference branch, then uses interference to favor positively correlated hypotheses. The analysis establishes a polynomial-time, one-example learner with success probability at least 0.53 and a deterministic classical circuit output.

3.2.1 Hypothesis Family H and Isometry W

A reference index and an efficiently computable injective feature map define an isometry that supports the sampler's hypothesis family.The family is assumed 4-wise independent and admits a distribution-preserving global sign flip.Source: §3.2.1 · pp. 22–23

3.2.2 Quantum Algorithm Q

The learner prepares a quantum example, transforms its label and input registers, applies W, measures a seed, and outputs the corresponding classical circuit.The reference and target branches remain unmeasured so they can interfere.Source: §3.2.2 · pp. 24–25
The linear term 2Za favors positive over negative correlations; interference changes the sampling distribution before measurement, making the positively correlated orientation intrinsically more likely, including for paired normalized correlations z and −z when z > 0.Source: §3.2.2 · p. 25

3.2.3 Correctness

The correctness proof applies Paley-Zygmund under the quantum measurement distribution to show that the learner outputs a positively correlated hypothesis with probability strictly above one half.The proof uses moment bounds for the normalized correlation under the uniform seed distribution.Source: §3.2.3 · pp. 25–27
The quantum learner uses one quantum random example and runs in polynomial time, succeeding with probability p⋆ ≥ 0.53.It outputs a deterministic classical Boolean circuit of size O(n^2).Source: §3.2.3 · pp. 25, 27

3.3 Boosting Correlation and Success Probability: Proof of Item 2

The section boosts the quantum learner’s positive correlation and success probability by combining independent hypotheses with majority. Pointwise bias and independence across distinct inputs support a guarantee with controlled failure probability.

3.3 Boosting Correlation and Success Probability: Proof of Item 2

Each run gives a small positive pointwise bias toward the target, and the resulting agreement indicators are independent across distinct input pairs.Majority increases the pointwise bias; independence then supports concentration of the overall correlation.Source: §3.3 · pp. 27–28
Majority over m independent runs of Q produces a deterministic classical circuit using m quantum random examples, in time m · poly(n).The output circuit has size m · poly(n).Source: §3.3 · p. 29
Choosing the number of runs from the desired failure probability yields time, circuit size, and quantum-example count proportional to poly(n)/η.The construction chooses the smallest odd m at least C0/η when η ≥ C/N.Source: §3.3 · p. 30

4 Limitations of Classical Learners: Proof of Theorem 1.4

The section establishes classical learning lower bounds, first for arbitrary Boolean targets and then, conditionally, for polynomial-size concepts. The latter uses strong pseudorandom functions derived from subexponentially secure one-way functions.

4.1 Unconditional Information Theoretic Lower Bound for C = ALL: Proof of Item 1

At correlation Ω(2^−n/2), achieving success probability strictly greater than 1/2 requires Ω(2^n/2) classical membership queries, even for adaptive learners with unrestricted running time and output size.For γ = c · 2^−n/2 with fixed c > 0, learners making q = o(2^n/2) queries are ruled out.Source: §4.1 · pp. 30–31
The unconditional lower bound uses a uniformly random target and applies regardless of the learner’s running time or output-circuit size.Conditioned on an adaptive query transcript, unqueried target signs remain independent and uniform.Source: §4.1 · p. 30

4.2.1 Strong Pseudorandom Functions

Subexponentially secure one-way functions imply strong pseudorandom function families whose members have polynomial-size Boolean circuits.The construction proceeds through an amplified one-way function and a pseudorandom generator.Source: §4.2.1 · pp. 31–32

4.2.2 Lower Bound

Assuming subexponentially secure one-way functions, no uniform randomized classical learner running in o(2^m/2) time with membership queries achieves the stated correlation and success guarantee on every target in SIZE[m^K].The proof replaces random targets with restrictions of strong pseudorandom functions, while keeping the concepts polynomial size.Source: §4.2.2 · pp. 32–33

5 Quantum PAC Learning Advantage: Proof of Theorem 1.5

The section proves an unconditional large-error quantum–classical learning separation by padding targets and bounding classical learners’ query-based success. It also gives a polynomial-size-concept separation under a one-way-function assumption.

5 Quantum PAC Learning Advantage: Proof of Theorem 1.5

For sufficiently large n, the amplified learner from Theorem 1.2 Item (ii) achieves advantage λ_n with success probability at least 1−1/n^k in polynomial time.A standard padding argument chooses targets that depend on only m of their n input bits.Source: §5 · p. 34

5.1 Refined Query Lower Bound for Padded Functions

For padded targets, a classical learner using q membership queries has a success-probability bound when its target advantage γ exceeds q/(2M).The bound applies even when the output circuit depends arbitrarily on the padding bits.Source: §5.1 · pp. 34–35

5.2 Unconditional Separation

At advantage λ_n/n^k, every polynomial-time classical learner has some target on which its success probability is at most 1/n^k for sufficiently large n.The proof applies the padded query lower bound to the class constructed for the unconditional separation.Source: §5.2 · p. 36

5.3 Conditional Separation for C ⊆SIZE[poly]

Under the assumption of subexponentially secure one-way functions, the separation extends to polynomial-size concepts via strong pseudorandom functions.For every sufficiently large n, some target in the constructed class limits classical success at advantage λ_n/n^k to at most 1/n^k.Source: §5.3 · pp. 37–38

A Fourier-Based Quantum Learner for C = ALL with p⋆≤1/2

Standard Fourier sampling uses quantum examples to sample parities according to squared Fourier coefficients. It can find a parity with substantial correlation, but does not reveal whether that parity or its negation is positively correlated.

A Fourier-Based Quantum Learner for C = ALL with p⋆≤1/2

With constant probability, a sampled parity or its negation has correlation Ω(2^−n/2) with the target.The cited review describes the standard learner’s correlation as at least γ · 2^−n/2.Source: A Fourier-Based Quantum Learner for C… · pp. 40–41
Because Fourier sampling loses the coefficient’s sign, guessing between a parity and its negation succeeds only half the time when the magnitude is sufficiently large.Consequently, the learner’s success probability is not greater than 1/2.Source: A Fourier-Based Quantum Learner for C… · p. 41
Fourier sampling from uniform quantum examples samples a parity χ_S with probability equal to its squared Fourier coefficient.The coefficient is the correlation between the target’s sign representation and χ_S.Source: A Fourier-Based Quantum Learner for C… · pp. 40–42

B Orienting a Weak Hypothesis is Hard

Orienting a known hypothesis means choosing its sign to make its correlation with the target positive, a task equivalent to gap majority. This task has an exponential worst-case quantum query lower bound, which the learner avoids by favoring positively correlated hypotheses in its measurement distribution.

B Orienting a Weak Hypothesis is Hard

Orienting H means choosing H or −H to obtain positive correlation, which reduces to deciding a gap-majority instance.Because H is known, query access to the target F and to the associated z are equivalent.Source: B Orienting a Weak Hypothesis is Hard · p. 42
Distinguishing the promised boundary weights requires quantum membership queries for any fixed success probability greater than 1/2 on every promised input.Consequently, orienting an arbitrary known H with that guarantee requires Ω(2^(n/2)) worst-case queries to F.Source: B Orienting a Weak Hypothesis is Hard · p. 42
The learner avoids this obstacle by biasing its measurement distribution toward positively correlated hypotheses instead of fixing a candidate and then determining its sign.Source: B Orienting a Weak Hypothesis is Hard · p. 42

C Limits of Parity Functions and of Pairwise Independence

The quadratic Boolean family supports constant-probability guarantees for both learners, but replacing it with affine parities does not preserve those guarantees. The examples show why pairwise independence alone is insufficient for the classical sampling analysis, and the quantum procedure also has limited success on a parity target.

C Limits of Parity Functions and of Pairwise Independence

Affine parities are efficiently computable, pairwise independent, and admit a global sign flip, yet replacing the quadratic family fails to preserve either learner’s success guarantee.Source: C Limits of Parity Functions and of… · pp. 42–43
With the quadratic family, the classical learner achieves agreement at least 1/2 + 1/(4N) with probability at least 3/32 for every target.Here N = 2^n.Source: C Limits of Parity Functions and of… · p. 43
For the classical sampling procedure, affine parities yield exact success probability 1/(2N), rather than a constant guarantee.The fourth-moment analysis gives only 9/(32N), showing pairwise independence does not suffice for constant success.Source: C Limits of Parity Functions and of… · p. 43
For the quadratic family, the fourth-moment bound E_U[Z^4] ≤ 3 yields the 3/32 success bound used in the classical learner’s analysis.Paley–Zygmund gives U[|Z| ≥ 1/2] ≥ 9/(16 E_U[Z^4]); global sign symmetry yields the corresponding one-sided bound.Source: C Limits of Parity Functions and of… · p. 43
For affine parities, the quantum measurement distribution is expressed using the target’s Fourier coefficients b_F(u) = E_x∼U[F(x)χ_u(x)].The affine feature map is injective and has an efficiently computable inverse on its image.Source: C Limits of Parity Functions and of… · pp. 43–44
On a parity target, the quantum procedure’s probability of meeting the theorem’s agreement threshold tends to 1/4, so it does not exceed 1/2.For F = χ_s, the only positively correlated output is H_s,0 = F.Source: C Limits of Parity Functions and of… · p. 44