Theorem 4.10 — gate-efficient learning with bounded support size
OpenQuantumLTF.Majority.theorem_4_10gate-complexityquantum-algorithmssection-4
For nonempty hidden supports of size at most , 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 : ∃ C : ℝ, 0 < C ∧ ∀ n k : ℕ, 2 ≤ k → k ≤ n → ∀ ε : ℝ, 0 < ε → ε < 1 → ∃ (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).