Optimal quantum PAC sample complexity lower bound

Open

QAlgorithms.Arunachalam.quantumPAC_sample_lower_bound_optimal

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

arunachalamlecture-notesquantum-information

Let $C\subseteq\{c:\{0,1\}^n\to\{0,1\}\}$ be a concept class with $\mathrm{VC\text{-}dim}(C)=d+1$ . A quantum $(\varepsilon,\delta)$ -PAC learner using $T$ examples is a POVM $\{M_h\}$ , indexed by hypotheses $h:\{0,1\}^n\to\{0,1\}$ , acting on $T$ copies of the quantum example $|\psi_{c,D}\rangle=\sum_x\sqrt{D(x)}\,|x,c(x)\rangle$ , such that for every $c\in C$ and every distribution $D$ on $\{0,1\}^n$ it outputs an $h$ with $\Pr_{x\sim D}[h(x)\neq c(x)]\le\varepsilon$ with probability at least $1-\delta$ .

There are absolute constants $C_0>0$ and $d_0$ such that for all $n$ , all such $C$ with $d\ge d_0$ , all $\delta\in(0,1/2)$ and $\varepsilon\in(0,1/20)$ , every quantum $(\varepsilon,\delta)$ -PAC learner for $C$ using $T$ examples satisfies

T\ \ge\ C_0\left(\frac{d}{\varepsilon}+\frac{\log(1/\delta)}{\varepsilon}\right).

Together with the classical upper bound, this shows that quantum examples do not reduce the sample complexity of PAC learning by more than a constant factor.

Formalization Note The constant of the $\Omega$ and the threshold for "sufficiently large $d$ " are quantified before every other object, so they are uniform in $n$ , $C$ , $\delta$ , $\varepsilon$ and the learner. The logarithm is natural; its base only changes the constant.

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.Arunachalam

open QAlgorithms.Learning

/-- Arunachalam p.175–177, Theorem 7.5.6: let `C` be a concept class with `VC-dim(C) = d + 1`, for
sufficiently large `d`. Then for every `δ ∈ (0, 1/2)` and `ε ∈ (0, 1/20)`, every `(ε, δ)`-PAC
quantum learner for `C` has sample complexity `Ω(d/ε + (1/ε) log(1/δ))`.

The constant `C₀` of the `Ω` and the threshold `d₀` of "sufficiently large `d`" are absolute:
they come before `n`, `C`, `d`, `δ`, `ε` and the learner. -/
theorem quantumPAC_sample_lower_bound_optimal :
    ∃ C₀ : ℝ, 0 < C₀ ∧ ∃ d₀ : ℕ,
      ∀ (n : ℕ) (C : Finset (Qubits n → Bool)) (d : ℕ), vcDimClass C = d + 1 → d₀ ≤ d →
        ∀ δ ε : ℝ, 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 →
              C₀ * ((d : ℝ) / ε + Real.log (1 / δ) / ε) ≤ (T : ℝ) := by
  sorry






end QAlgorithms.Arunachalam

Source

Srinivasan Arunachalam, Quantum Algorithms and Learning Theory — Part II, 2018 thesis, ILLC DS-2018-08, PDF p. 175, Theorem 7.5.6. https://ir.cwi.nl/pub/27536/Thesis_S_Arunachalam

Read-back

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

There exist a real constant $C_0 > 0$ and a natural number $d_0$ such that the following holds. Take any $n \in \mathbb{N}$ , any finite concept class $C$ of Boolean functions $c : \{0,1\}^n \to \{0,1\}$ , and any $d \in \mathbb{N}$ with $d \ge d_0$ such that the VC dimension of $C$ equals $d+1$ . Here the VC dimension is that of the family of sets $\{x : c(x) = 1\}$ , $c \in C$ . Take any reals $\delta, \varepsilon$ with $0 < \delta < 1/2$ and $0 < \varepsilon < 1/20$ , any $T \in \mathbb{N}$ , and any family $(M_h)$ of complex matrices on the space indexed by $(\{0,1\}^n \times \{0,1\})^T$ . The family has one matrix for every Boolean function $h : \{0,1\}^n \to \{0,1\}$ , not only for $h \in C$ .

Suppose $M$ is a quantum PAC learner for $C$ with parameters $(\varepsilon, \delta)$ using exactly $T$ examples, meaning:

each $M_h$ is positive semidefinite and $\sum_h M_h = I$ ;
for every $c \in C$ and every distribution $D$ on $\{0,1\}^n$ (nonnegative weights summing to $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.

In this condition:

$\mathrm{err}_D(c,h) = \sum_{x : h(x) \ne c(x)} D(x)$ ;
$\psi_{c,D}$ is the vector on $\{0,1\}^n \times \{0,1\}$ with amplitude $\sqrt{D(x)}$ at $(x, c(x))$ and $0$ at $(x, 1-c(x))$ ;
$\psi^{\otimes T}$ has amplitude $\prod_{i=1}^T \psi(z_i)$ at $(z_1,\dots,z_T)$ .

Then

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

The constants $C_0, d_0$ do not depend on $n$ , $C$ , $\delta$ , $\varepsilon$ , $T$ or $M$ . The case $T = 0$ is included: then the state space is one-dimensional.

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