Theorem 4.10 — gate-efficient learning with bounded support size (fixed error)
OpenQuantumLTF.Majority.theorem_4_10_fixed_errorgate-complexityquantum-algorithmssection-4
Fix any constant error . Under , 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_10_fixed_error : ∀ ε : ℝ, 0<ε → ε<1 → ∃ C : ℝ, 0<C ∧ ∀ n k : ℕ, 2≤k → k≤n → ∃ (m : ℕ) (c : OracleCircuit gates12 (fun _ : Fin 1 => n+1) m) (out : Fin n ↪ Fin m) (d : ℕ), LearnsUpTo (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.10, p.56 (PDF p.57). The constant is quantified after the fixed error parameter, matching the source.