Quantum agnostic sample complexity lower bound (information-theoretic)

Open

QAlgorithms.Arunachalam.quantumAgnostic_sample_lower_bound_info

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\ge1$ . For a distribution $D$ on $\{0,1\}^n\times\{0,1\}$ write $\mathrm{err}_D(h)=\Pr_{(x,b)\sim D}[h(x)\ne b]$ and $\mathrm{opt}_D(C)=\min_{c\in C}\mathrm{err}_D(c)$ . A quantum $(\varepsilon,\delta)$ -agnostic learner using $T$ examples is a POVM $\{M_h\}_{h\in C}$ on $T$ copies of $|\psi_D\rangle=\sum_{(x,b)}\sqrt{D(x,b)}\,|x,b\rangle$ that, for every $D$ , outputs $h\in C$ with $\mathrm{err}_D(h)\le\mathrm{opt}_D(C)+\varepsilon$ with probability at least $1-\delta$ .

For every $\delta_0\in(0,1/2)$ there is a constant $C_0>0$ such that for all $n$ , all such $C$ , all $\delta\in(0,\delta_0]$ and $\varepsilon\in(0,1/4)$ , every quantum $(\varepsilon,\delta)$ -agnostic learner for $C$ using $T$ examples satisfies

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

with logarithms to base 2.

This is the agnostic analogue of Theorem 7.4.6, again tight up to the $\log(d/\varepsilon)$ factor.

Formalization Note The constant may depend on an upper bound $\delta_0<1/2$ for $\delta$ , and $d\ge1$ is assumed: for $d=0$ the class has a single concept, which is output with no samples.

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.Arunachalam

open QAlgorithms.Learning


/-- Arunachalam p.169–170, Theorem 7.4.7: let `C` be a concept class with `VC-dim(C) = d`. Then
for every `δ ∈ (0, 1/2)` and `ε ∈ (0, 1/4)`, every `(ε, δ)`-agnostic quantum learner for `C` has
sample complexity `Ω(d/(ε² log(d/ε)) + log(1/δ)/ε²)`.

Recorded corrections (trap 30), as for Theorem 7.4.4: the constant may depend on an upper bound
`δ₀ < 1/2` on `δ`, and `d ≥ 1` (at `d = 0` the class has a single concept, which is output with no
samples). The constant is uniform over `n`, `C`, `d`, `δ ∈ (0, δ₀]` and `ε`. -/
theorem quantumAgnostic_sample_lower_bound_info (δ₀ : ℝ) (hδ₀ : 0 < δ₀) (hδ₀' : δ₀ < 1 / 2) :
    ∃ C₀ : ℝ, 0 < C₀ ∧
      ∀ (n : ℕ) (C : Finset (Qubits n → Bool)) (d : ℕ), vcDimClass C = d → 1 ≤ d →
        ∀ δ ε : ℝ, 0 < δ → δ ≤ δ₀ → 0 < ε → ε < 1 / 4 →
          ∀ (T : ℕ) (M : {c // c ∈ C} →
              Matrix (Fin T → Qubits n × Bool) (Fin T → Qubits n × Bool) ℂ),
            IsQAgnosticLearner C ε δ T M →
              C₀ * ((d : ℝ) / (ε ^ 2 * Real.logb 2 ((d : ℝ) / ε)) +
                  Real.logb 2 (1 / δ) / ε ^ 2) ≤ (T : ℝ) := by
  sorry





end QAlgorithms.Arunachalam

Source

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

Read-back

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

Fix a real number $\delta_0$ with $0 < \delta_0 < \tfrac12$ . The theorem asserts that there is a constant $C_0 > 0$ , depending only on $\delta_0$ , such that the following holds for:

every $n \in \mathbb{N}$ ;
every finite concept class $C$ of functions $\{0,1\}^n \to \{0,1\}$ ;
every $d \in \mathbb{N}$ ;
all reals $\delta, \varepsilon$ with $0 < \delta \le \delta_0$ and $0 < \varepsilon < \tfrac14$ ;
every $T \in \mathbb{N}$ and every family $(M_c)_{c \in C}$ of complex square matrices indexed by the elements of $C$ . The matrices act on the space with basis $(\{0,1\}^n \times \{0,1\})^T$ .

The hypotheses are:

VC dimension. The VC dimension of $C$ (that of the supports $\{x : c(x)=1\}$ ) equals $d$ , and $d \ge 1$ .
$M$ is a quantum agnostic $(\varepsilon,\delta)$ -learner for $C$ using $T$ examples. This means:
- $M$ is a POVM: each $M_c$ is positive semidefinite and $\sum_{c \in C} M_c = I$ .
- For every probability distribution $D$ on $\{0,1\}^n \times \{0,1\}$ (nonnegative, summing to $1$ ), we have

\sum_{h \in C \,:\, \mathrm{err}_D(h) \le \mathrm{opt}_D(C) + \varepsilon} \operatorname{Re}\operatorname{Tr}\!\big(M_h\,|\Psi_D\rangle\langle\Psi_D|\big) \;\ge\; 1-\delta.

Here $\mathrm{err}_D(h) = \sum_{(x,b) : h(x) \ne b} D(x,b)$ , and $\mathrm{opt}_D(C) = \inf_{c \in C} \mathrm{err}_D(c)$ .
The state is $|\Psi_D\rangle = |\psi_D\rangle^{\otimes T}$ , with coordinates $\prod_i \sqrt{D(x_i,b_i)}$ .

No non-triviality hypothesis on $C$ is imposed. VC dimension $\ge 1$ forces $|C| \ge 2$ .

The conclusion is

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

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