Quantum PAC sample complexity lower bound (information-theoretic)

Open

QAlgorithms.Arunachalam.quantumPAC_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 non-trivial concept class (it has at least two concepts and is not of the form $\{c,1-c\}$ ) 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$ .

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)$ -PAC learner for $C$ using $T$ examples satisfies

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

with logarithms to base 2.

This is the information-theoretic quantum lower bound, tight up to the $\log(d/\varepsilon)$ factor; Section 7.5 later removes that factor.

Formalization Note The constant of the $\Omega$ is allowed to depend on an upper bound $\delta_0<1/2$ for $\delta$ , and non-triviality of $C$ is assumed (it matters only at $d=0$ ); both are the hypotheses of Lemma 7.4.1, which the proof invokes for the $\log(1/\delta)/\varepsilon$ term. At $d=0$ the first term evaluates to $0$ .

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.Arunachalam

open QAlgorithms.Learning

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

Recorded corrections (trap 30), as for Theorem 7.4.3: the constant of the `Ω` may depend on an
upper bound `δ₀ < 1/2` on `δ` (the `log(1/δ)/ε` part is Lemma 7.4.1, which cannot hold uniformly
as `δ → 1/2`), and `C` is non-trivial (the hypothesis of Lemma 7.4.1; binding only at `d = 0`). The
constant is uniform over `n`, `C`, `d`, `δ ∈ (0, δ₀]` and `ε`. -/
theorem quantumPAC_sample_lower_bound_info (δ₀ : ℝ) (hδ₀ : 0 < δ₀) (hδ₀' : δ₀ < 1 / 2) :
    ∃ C₀ : ℝ, 0 < C₀ ∧
      ∀ (n : ℕ) (C : Finset (Qubits n → Bool)) (d : ℕ), vcDimClass C = d + 1 →
        IsNontrivialClass C →
        ∀ δ ε : ℝ, 0 < δ → δ ≤ δ₀ → 0 < ε → ε < 1 / 4 →
          ∀ (T : ℕ) (M : (Qubits n → Bool) →
              Matrix (Fin T → Qubits n × Bool) (Fin T → Qubits n × Bool) ℂ),
            IsQPACLearner C ε δ T M →
              C₀ * ((d : ℝ) / (ε * Real.logb 2 ((d : ℝ) / ε)) + Real.logb 2 (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. 168, Theorem 7.4.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

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 concept class $C$ , a finite set of Boolean functions $c : \{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 = (M_h)_h$ of complex square matrices indexed by all functions $h : \{0,1\}^n \to \{0,1\}$ (not only those in $C$ ). Each $M_h$ acts on the space with basis indexed by $T$ -tuples $\big((x_1,b_1),\dots,(x_T,b_T)\big) \in (\{0,1\}^n \times \{0,1\})^T$ .

The hypotheses are:

VC dimension. The VC dimension of $C$ equals $d+1$ . Here the VC dimension is that of the family of supports $\{x : c(x) = 1\}$ , $c \in C$ . So $d$ is the VC dimension minus one, and $d = 0$ is allowed.
Non-triviality. $C$ is non-trivial: $|C| \ge 2$ , and $C$ is not of the form $\{c, \bar c\}$ for any function $c$ , where $\bar c(x) = 1 - c(x)$ .
$M$ is a quantum $(\varepsilon,\delta)$ -PAC learner for $C$ using $T$ examples. This means:
- $M$ is a POVM: each $M_h$ is positive semidefinite and $\sum_h M_h = I$ .
- For every $c \in C$ and every probability distribution $D$ on $\{0,1\}^n$ (that is, $D(x) \ge 0$ and $\sum_x D(x) = 1$ ), we have

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

Here $\mathrm{err}_D(c,h) = \sum_{x : h(x) \ne c(x)} D(x)$ , and $|\Psi\rangle = |\psi_{c,D}\rangle^{\otimes T}$ . The coordinates of $|\Psi\rangle$ are $\prod_{i=1}^T \psi_{c,D}(x_i,b_i)$ , where $\psi_{c,D}(x,b) = \sqrt{D(x)}$ if $b = c(x)$ and $0$ otherwise. For $T = 0$ this is the scalar $1$ on a one-dimensional space.

The conclusion is

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

When $d = 0$ the first summand evaluates to $0$ (it is $0$ divided by a junk value). When $d \ge 1$ , the condition $\varepsilon < \tfrac14$ gives $d/\varepsilon > 4$ , so the logarithm is positive.

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