Classical (N,M)-query complexity of exact learning is Θ(min{M,N})

Open

QAlgorithms.LearningSurvey.classical_NM_exact_theta

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

learning-surveylecture-notesquantum-information

This is the folklore characterization of the classical $(N,M)$ -query complexity of exact learning.

Let $N=2^n$ and let $M$ be an integer with $2\le M\le 2^N$ . The classical $(N,M)$ -query complexity $D(N,M)$ is the maximum, over all concept classes $C\subseteq\{0,1\}^N$ with $|C|=M$ , of the classical membership query complexity of exactly learning $C$ (randomized learners, success probability at least $2/3$ on every target, worst-case number of queries). There are absolute constants $c_1,c_2>0$ such that for all such $n$ and $M$

c_1\min\{M,N\}\ \le\ D(N,M)\ \le\ c_2\min\{M,N\}.

It is the classical benchmark against which Kothari's quantum characterization (Theorem 4.6) is compared.

Formalization Note $N$ is restricted to powers of two, as throughout §4.1. The case $M=1$ is excluded: the only class has one concept and needs no queries, so the lower bound of the $\Theta$ is meant for $M\ge 2$ . The bound $M\le 2^N$ excludes sizes for which no class exists.

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.LearningSurvey

universe u



/-- **Theorem 4.5** (folklore; survey p.10). The classical `(N, M)`-query complexity of exact
learning is `Θ(min{M, N})`, for `N = 2^n` and every class size `2 ≤ M ≤ 2^N`. -/
theorem classical_NM_exact_theta :
    ∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧ ∀ (n M : ℕ), 2 ≤ M → M ≤ 2 ^ (2 ^ n) →
      c₁ * (min M (2 ^ n) : ℕ) ≤ (Learning.classicalExactNM n M : ℝ) ∧
        (Learning.classicalExactNM n M : ℝ) ≤ c₂ * (min M (2 ^ n) : ℕ) := by
  sorry



end QAlgorithms.LearningSurvey

Source

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

Read-back

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

Classical exact complexity. For a finite concept class $C$ on $\{0,1\}^n$ , the classical exact complexity $R(C)$ is the least $T\in\mathbb N$ for which there is a randomized decision tree $R$ (a probability distribution over deterministic decision trees querying values $c(i)$ and outputting a hypothesis) such that:

every tree in the support of $R$ makes at most $T$ queries on every input;
for every $c\in C$ , a tree drawn from $R$ and run on $c$ outputs exactly $c$ with probability at least $2/3$ .

It is $0$ if no such $T$ exists.

Worst case over classes of size $M$ . Let

R(n,M)=\max\{R(C): C \text{ a set of exactly } M \text{ concepts } \{0,1\}^n\to\{0,1\}\},

with the value $0$ if there are no such sets.

Statement. There are constants $c_1,c_2>0$ such that for all $n,M\in\mathbb N$ with $2\le M\le 2^{2^n}$ ,

c_1\cdot\min(M,2^n)\ \le\ R(n,M)\ \le\ c_2\cdot\min(M,2^n).

Edge case: $n=0$ is allowed. Then only $M=2$ qualifies, and $\min(M,2^n)=1$ .

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