Theorem 4.1 — query complexity of learning Majority
OpenQuantumLTF.Majority.theorem_4_1majorityquantum-algorithmssection-4
For every , learning a hidden Majority support has bounded-error quantum query complexity under both promises and .
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_1 : ∃ Cu Cl : ℝ, 0 < Cu ∧ 0 < Cl ∧ ∀ k : ℕ, 2 ≤ k → ((∀ n : ℕ, 2*k ≤ n → (∃ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m), (c.queryCount 0 : ℝ) ≤ Cu*Real.log k ∧ LearnsExact (k:=k) c out (2/3)) ∧ ∀ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m), LearnsExact (k:=k) c out (2/3) → Cl*Real.log k ≤ c.queryCount 0) ∧ (∀ n : ℕ, k ≤ n → (∃ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m), (c.queryCount 0 : ℝ) ≤ Cu*Real.log k ∧ LearnsUpTo (k:=k) c out (2/3)) ∧ ∀ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m), LearnsUpTo (k:=k) c out (2/3) → Cl*Real.log k ≤ c.queryCount 0)) := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Theorem 4.1, p.39 (PDF p.40).