Theorem 4.6 — logarithmic lower bound for learning Majority
OpenQuantumLTF.Majority.theorem_4_6lower-boundsquantum-algorithmssection-4
For , every bounded-error quantum learner for nonempty supports of size at most needs Majority queries.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Majority_oracle import Definitions.Def_QuantumLTF_Sections45_Model
Formal statement
namespace QuantumLTF.Majority open QAlgorithms QuantumLTF.Membership theorem theorem_4_6 : ∃ C : ℝ, 0 < C ∧ ∀ n k : ℕ, 2 ≤ k → k ≤ n → ∀ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m), LearnsUpTo (k:=k) c out (2/3) → C*Real.log k ≤ c.queryCount 0 := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Theorem 4.6, p.49 (PDF p.50).