Kothari: optimal quantum (N,M)-query complexity of exact learning

Open

QAlgorithms.LearningSurvey.kothari_quantum_NM_exact_theta

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

learning-surveylecture-notesquantum-information

This is Kothari's tight characterization of the quantum $(N,M)$ -query complexity of exact learning.

Let $N=2^n$ . For an integer $M$ , the quantum $(N,M)$ -query complexity $Q(N,M)$ is the maximum, over concept classes $C\subseteq\{0,1\}^N$ with $|C|=M$ , of the least number of queries to $O_c:|x,b\rangle\mapsto|x,b\oplus c(x)\rangle$ made by a quantum exact learner for $C$ (success probability at least $2/3$ on every target). There are absolute constants $c_1,c_2>0$ such that:

if $2\le M\le N$ , then $c_1\sqrt M\le Q(N,M)\le c_2\sqrt M$ ;
if $N<M\le 2^N$ , then, with $\log=\log_2$ ,

c_1\sqrt{\frac{N\log M}{\log(N/\log M)+1}}\ \le\ Q(N,M)\ \le\ c_2\sqrt{\frac{N\log M}{\log(N/\log M)+1}}.

Compared with the classical $\Theta(\min\{M,N\})$ of Theorem 4.5, it quantifies the quantum speed-up for oracle identification.

Formalization Note $M=1$ is excluded from the first case (a single concept needs no queries). In the second case $1<\log_2 M\le N$ , so the denominator is at least $1$ . Logarithms are base 2; another base changes the expression only by bounded factors.

Preamble

import Definitions.Def_QAlgorithms_Defs_LearningHardInstances
set_option autoImplicit false

Formal statement

namespace QAlgorithms.LearningSurvey

universe u




/-- **Theorem 4.6** (Kothari; survey p.10). The quantum `(N, M)`-query complexity of exact
learning (`N = 2^n`) is `Θ(√M)` for `M ≤ N` and
`Θ(√(N log M / (log(N / log M) + 1)))` for `N < M ≤ 2^N` (logarithms base 2). -/
theorem kothari_quantum_NM_exact_theta :
    ∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧ ∀ (n M : ℕ),
      (2 ≤ M → M ≤ 2 ^ n →
        c₁ * Real.sqrt (M : ℝ) ≤ (Learning.quantumExactNM n M : ℝ) ∧
          (Learning.quantumExactNM n M : ℝ) ≤ c₂ * Real.sqrt (M : ℝ)) ∧
      (2 ^ n < M → M ≤ 2 ^ (2 ^ n) →
        c₁ * Real.sqrt (((2 ^ n : ℕ) : ℝ) * Real.logb 2 (M : ℝ) /
            (Real.logb 2 (((2 ^ n : ℕ) : ℝ) / Real.logb 2 (M : ℝ)) + 1)) ≤
          (Learning.quantumExactNM n M : ℝ) ∧
        (Learning.quantumExactNM n M : ℝ) ≤
          c₂ * Real.sqrt (((2 ^ n : ℕ) : ℝ) * Real.logb 2 (M : ℝ) /
            (Real.logb 2 (((2 ^ n : ℕ) : ℝ) / Real.logb 2 (M : ℝ)) + 1))) := 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.6. https://arxiv.org/pdf/1701.06806v3

Read-back

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

Quantum exact complexity. Concepts, $T$ -query quantum algorithms with XOR oracle $O_c:|x,b\rangle\mapsto|x,b\oplus c(x)\rangle$ , and exact learning with success probability $\ge 2/3$ for each $c\in C$ are as in the first entry. $Q(C)$ is the least $T$ such that some $T$ -query algorithm with workspace $\{0,\dots,w-1\}$ (some $w$ ) and some output map exactly learn $C$ . It is $0$ if no such $T$ exists.

Worst case over classes of size $M$ . Let

Q(n,M)=\max\{Q(C): |C|=M\}

over sets $C$ of concepts $\{0,1\}^n\to\{0,1\}$ , with the value $0$ if there are none.

Statement. There are constants $c_1,c_2>0$ such that for all $n,M\in\mathbb N$ both of the following hold.

If $2\le M\le 2^n$ , then

c_1\sqrt M\ \le\ Q(n,M)\ \le\ c_2\sqrt M .

If $2^n<M\le 2^{2^n}$ , then

c_1\sqrt{\frac{2^n\log_2 M}{\log_2\!\bigl(2^n/\log_2 M\bigr)+1}}\ \le\ Q(n,M)\ \le\ c_2\sqrt{\frac{2^n\log_2 M}{\log_2\!\bigl(2^n/\log_2 M\bigr)+1}} .

Both are implications, so for $M$ outside both ranges nothing is asserted.

Edge case: for $n=0$ , case 1 is vacuous. Case 2 applies only to $M=2$ , where the expression under the root equals $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