Theorem 5.8 — learning homogeneous LTFs with a quantum-example oracle
OpenQuantumLTF.Example.theorem_5_8example-oraclequantum-algorithmssection-5
For and , homogeneous LTFs can be learned to vector error with probability using quantum examples and gates.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Example_qex import Definitions.Def_QuantumLTF_Sections45_Model
Formal statement
namespace QuantumLTF.Example open QAlgorithms QuantumLTF.Membership theorem theorem_5_8 : ∃ C : ℝ, ∃ J : ℕ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n → ∀ ε : ℝ, 0 < ε → ε < 1/2 → ∃ (q m : ℕ) (L : LearnerContract n q m), LearnsHomogeneous L ε (2/3) ∧ (L.circuit.queryCount 0 : ℝ) ≤ C*(n : ℝ)^(1/4 : ℝ)/Real.sqrt ε ∧ (L.circuit.gateCount : ℝ) ≤ C*((n : ℝ)^(5/4 : ℝ)/Real.sqrt ε+(n : ℝ)^2/ε)*(Real.log (n/ε))^J := by sorry end QuantumLTF.Example
Source
Krivcenko, Nguyen, de Wolf, STOC 2027 submission #347, Theorem 5.8, p.72 (PDF p.73).