Theorem 4.9 — gate-efficient learning with known odd support size (fixed error)
OpenQuantumLTF.Majority.theorem_4_9_fixed_errorgate-complexityquantum-algorithmssection-4
Fix any constant error . For odd known support size , the learner uses queries, gates and depth .
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_9_fixed_error : ∀ ε : ℝ, 0<ε → ε<1 → ∃ C : ℝ, 0<C ∧ ∀ n k : ℕ, 2≤k → k≤n → Odd k → ∃ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m) (d : ℕ), LearnsExact (k:=k) c out (1-ε) ∧ (c.queryCount 0 : ℝ)≤C*Real.log k ∧ (c.gateCount : ℝ)≤C*n*Real.log (n+1)*Real.log k ∧ (d:ℝ)≤C*Real.log (n+1)*Real.log k := by sorry end QuantumLTF.Majority
Source
Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Theorem 4.9, p.54 (PDF p.55). The constant is quantified after the fixed error parameter, matching the source.