Optimal quantum agnostic sample complexity lower bound

Open

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

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/10)$ , every quantum $(\varepsilon,\delta)$ -agnostic learner for $C$ using $T$ examples satisfies

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

This matches the classical agnostic sample complexity up to constants.

Formalization Note $C_0$ and $d_0$ are quantified before every other object. The source's proof is internally inconsistent in its parameter $\alpha$ ( $20\varepsilon$ in the text, $10\varepsilon$ in Lemma 7.5.9); the theorem, an $\Omega$ -statement, is stated as written.

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.Arunachalam

open QAlgorithms.Learning



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

The constant `C₀` and the threshold `d₀` are absolute (before every other object). The proof's
parameter choice is inconsistent (the text picks `α = 20ε`, Lemma 7.5.9 computes with `α = 10ε`);
the theorem is stated as written. -/
theorem quantumAgnostic_sample_lower_bound_optimal :
    ∃ C₀ : ℝ, 0 < C₀ ∧ ∃ d₀ : ℕ,
      ∀ (n : ℕ) (C : Finset (Qubits n → Bool)) (d : ℕ), vcDimClass C = d → d₀ ≤ d →
        ∀ δ ε : ℝ, 0 < δ → δ < 1 / 2 → 0 < ε → ε < 1 / 10 →
          ∀ (T : ℕ) (M : {c // c ∈ C} →
              Matrix (Fin T → Qubits n × Bool) (Fin T → Qubits n × Bool) ℂ),
            IsQAgnosticLearner C ε δ T M →
              C₀ * ((d : ℝ) / ε ^ 2 + Real.log (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. 178, Theorem 7.5.8. 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 class $C$ of Boolean functions on $\{0,1\}^n$ , and any $d \ge d_0$ such that the VC dimension of $C$ equals $d$ . Here the VC dimension is that of the family of sets $\{x : c(x) = 1\}$ , $c \in C$ . Take any reals $0 < \delta < 1/2$ and $0 < \varepsilon < 1/10$ , any $T \in \mathbb{N}$ , and any family $(M_c)_{c \in C}$ of complex matrices on the space indexed by $(\{0,1\}^n \times \{0,1\})^T$ . Here the outcomes are exactly the elements of $C$ .

Suppose $M$ is a quantum agnostic learner, meaning:

each $M_c$ is positive semidefinite and $\sum_{c \in C} M_c = I$ ;
for every distribution $D$ on $\{0,1\}^n \times \{0,1\}$ ,

\sum_{c \in C \,:\, \mathrm{err}_D(c) \le \mathrm{opt}_D(C) + \varepsilon} \operatorname{Re}\operatorname{Tr}\big(M_c\,|\phi_D^{\otimes T}\rangle\langle\phi_D^{\otimes T}|\big) \ge 1-\delta.

In this condition:

$\mathrm{err}_D(h) = \sum_{(x,b) : h(x) \ne b} D(x,b)$ ;
$\mathrm{opt}_D(C) = \inf_{c \in C} \mathrm{err}_D(c)$ , which would be $0$ by convention if $C$ were empty;
$\phi_D$ has amplitude $\sqrt{D(x,b)}$ at $(x,b)$ , and $\phi_D^{\otimes T}$ has amplitude $\prod_i \phi_D(z_i)$ .

If $C$ is empty, the condition $\sum_c M_c = I$ cannot hold, so the hypothesis is unsatisfiable. Then

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

The constants $C_0, d_0$ are uniform in $n$ , $C$ , $\delta$ , $\varepsilon$ , $T$ and $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