Quantum PAC learning needs Ω(d/ε + log(1/δ)/ε) quantum examples

Open

QAlgorithms.LearningSurvey.quantumPAC_sampleLowerBound

by Goku · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

learning-surveylecture-notesquantum-information

This is the optimal lower bound on the quantum sample complexity of PAC learning, with the threshold on the VC dimension that the proof requires.

Let $C$ be a concept class of Boolean functions $c:\{0,1\}^n\to\{0,1\}$ with VC dimension $d+1$ . For a distribution $D$ on $\{0,1\}^n$ and $c\in C$ , a quantum example is the state $\sum_x\sqrt{D(x)}\,|x,c(x)\rangle$ . An $(\varepsilon,\delta)$ -quantum PAC learner for $C$ with $T$ examples is a POVM $\{M_h\}$ on $T$ copies of the quantum example, with one outcome for every hypothesis $h:\{0,1\}^n\to\{0,1\}$ , such that for every $c\in C$ and every distribution $D$ the outcome $h$ satisfies $\Pr_{x\sim D}[h(x)\neq c(x)]\le\varepsilon$ with probability at least $1-\delta$ .

There are an absolute constant $K>0$ and a threshold $d_0$ such that for all $n$ , all $d\ge d_0$ , every concept class $C$ of VC dimension $d+1$ , all $\delta\in(0,1/2)$ and $\varepsilon\in(0,1/20)$ , every $(\varepsilon,\delta)$ -quantum PAC learner for $C$ uses

T\ \ge\ K\Big(\frac{d}{\varepsilon}+\frac{1}{\varepsilon}\log\frac{1}{\delta}\Big)

examples.

Together with the classical upper bound, this shows that quantum examples give no advantage in the distribution-free PAC model.

Formalization Note The source prints the bound for every $d$ ; at small $d$ and $\delta$ close to $1/2$ it is false (for two concepts differing at one point, one quantum example measured in the computational basis, with a fair coin when the distinguishing point is not seen, is an $(\varepsilon, 1/2-\varepsilon/2)$ -learner). The threshold $d_0$ is the source's own " $d$ a sufficiently large constant" from the proof. Ancillas and internal randomness are absorbed into the POVM.

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.LearningSurvey

open MeasureTheory QAlgorithms.Learning

/-- survey p.13, Theorem 4.12 ([AW17]): optimal quantum PAC sample-complexity lower bound.
Let `C` be a concept class on `{0,1}^n` with VC dimension `d + 1`. For every `δ ∈ (0, 1/2)` and
`ε ∈ (0, 1/20)`, every `(ε, δ)`-quantum PAC learner for `C` (a POVM on `T` copies of the quantum
example, one outcome per hypothesis, correct for every `c ∈ C` and every distribution `D`) uses
`T = Ω(d/ε + (1/ε) log(1/δ))` copies.

Corrected statement (trap 30): the `Ω` carries a threshold `d₀` on `d` (the source's proof needs
"`d` a sufficiently large constant", p.13; this is also the run's asymptotic convention). Without
it the printed statement is false: for `C = {c₁, c₂}` differing at one point (VC dimension 1,
`d = 0`), one copy measured in the computational basis, with a fair coin when the distinguishing
point is not seen, is an `(ε, 1/2 − ε/2)`-learner, while `K log(1/δ)/ε → ∞` as `ε → 0`. -/
theorem quantumPAC_sampleLowerBound :
    ∃ K : ℝ, 0 < K ∧ ∃ d₀ : ℕ, ∀ (n d : ℕ) (C : Finset (Qubits n → Bool)), d₀ ≤ d →
      vcDimClass C = d + 1 →
      ∀ δ ε : ℝ, 0 < δ → δ < 1 / 2 → 0 < ε → ε < 1 / 20 →
      ∀ (T : ℕ) (M : (Qubits n → Bool) →
          Matrix (Fin T → Qubits n × Bool) (Fin T → Qubits n × Bool) ℂ),
        IsQPACLearner C ε δ T M →
        K * ((d : ℝ) / ε + (1 / ε) * Real.log (1 / δ)) ≤ (T : ℝ) := by sorry




end QAlgorithms.LearningSurvey

Source

Srinivasan Arunachalam and Ronald de Wolf, A Survey of Quantum Learning Theory, 2017, v3, PDF p. 13, Theorem 4.12. https://arxiv.org/pdf/1701.06806v3

Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

There exist a real constant $K > 0$ and a threshold $d_0 \in \mathbb{N}$ such that the following holds for all natural numbers $n, d$ with $d_0 \le d$ and every finite concept class $C$ of Boolean functions $c : \{0,1\}^n \to \{0,1\}$ whose VC dimension equals $d + 1$ .

Here the VC dimension of $C$ is computed as follows. Each $c \in C$ is replaced by its set of positives $\{x : c(x) = 1\}$ . The VC dimension is then the largest size of a set $S \subseteq \{0,1\}^n$ shattered by this family, meaning every subset of $S$ arises as $S \cap \{x : c(x)=1\}$ for some $c \in C$ . Since a shattered set has at most $2^n$ elements, the hypothesis forces $d + 1 \le 2^n$ ; for smaller $n$ the statement is vacuous.

For all reals $\delta, \varepsilon$ with $0 < \delta < 1/2$ and $0 < \varepsilon < 1/20$ , take every $T \in \mathbb{N}$ (including $T = 0$ ) and every family $M = (M_h)_h$ of complex square matrices. The family is indexed by all functions $h : \{0,1\}^n \to \{0,1\}$ , not only those in $C$ , and each $M_h$ acts on the space with basis $(\{0,1\}^n \times \{0,1\})^T$ . If $M$ is a quantum PAC learner for $C$ with parameters $(\varepsilon, \delta, T)$ , then

K\left(\frac{d}{\varepsilon} + \frac{1}{\varepsilon}\ln\frac{1}{\delta}\right) \le T .

Being a quantum PAC learner means two things:

$M$ is a POVM. Each $M_h$ is positive semidefinite and $\sum_h M_h = I$ .
Success on every target. For every $c \in C$ and every $D : \{0,1\}^n \to \mathbb{R}$ with $D \ge 0$ and $\sum_x D(x) = 1$ ,

\sum_{h \,:\, \mathrm{err}_D(c,h) \le \varepsilon} \operatorname{Re}\operatorname{Tr}\!\big(M_h\, |\psi_{c,D}^{\otimes T}\rangle\langle\psi_{c,D}^{\otimes T}|\big) \;\ge\; 1 - \delta .

The symbols in this condition are defined as follows:

The error of a hypothesis $h$ is $\mathrm{err}_D(c,h) = \sum_{x : h(x) \ne c(x)} D(x)$ .
The example state $\psi_{c,D}$ has amplitude $\sqrt{D(x)}$ at $(x, c(x))$ and $0$ at $(x, 1 - c(x))$ .
The $T$ -fold tensor power has amplitude $\prod_{i=1}^T \psi_{c,D}(z_i)$ at $z = (z_1,\dots,z_T)$ .
For $T = 0$ , this tensor power is the single basis vector of a one-dimensional space.

The constants $K$ and $d_0$ are fixed before $n$ , $d$ , $C$ , $\delta$ , $\varepsilon$ , $T$ , $M$ .

Human review

Endorsed by Shuze Chen · Oct 13, 2026
Confirmed by the moderator at approval.
Endorsed by Goku · Oct 13, 2026
Confirmed by the mission captain (proposal self-audit).

View graph