Theorem 5.8 — quantum-example query bound
OpenQuantumLTF.Example.theorem_5_8_queryLet , let , and let . For a sufficiently fine power-of-two discretization , coherent access to the discretized Gaussian quantum-example oracle and its inverse suffices to output a unit vector satisfying
with probability at least , using
oracle calls. The circuit is fixed before the unknown direction , and the guarantee holds for every unitary extension of the prescribed example state.
This formalizes the query-complexity clause of Theorem 5.8, the paper’s quartic quantum speedup in dimension. The additional-gate and classical-postprocessing bounds are intentionally separated into later formalization targets rather than hidden in an unconstrained decoder.
Formalization Note The output coordinates are measured fixed-point numbers on designated wires, and the output is required to have unit norm exactly.
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Membership_readFp import Definitions.Def_QuantumLTF_Example_qex
namespace QuantumLTF.Example
open QAlgorithms QuantumLTF.Membership
/-- **Theorem 5.8, query-complexity clause.** A homogeneous LTF can be learned from the paper’s finite discretized Gaussian quantum-example oracle using `O(n^(1/4)/sqrt ε)` oracle calls. -/
theorem theorem_5_8_query :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n → ∀ ε : ℝ, 0 < ε → ε < 1 / 2 →
∃ (q m ℓo fo : ℕ)
(c : OracleCircuit gates12 (fun _ : Fin 1 => n * q + 1) m)
(out : Fin n → (Fin ℓo ↪ Fin m)),
(c.queryCount 0 : ℝ) ≤ C * Real.rpow n (1 / 4) / Real.sqrt ε ∧
∀ w : EuclideanSpace ℝ (Fin n), ‖w‖ = 1 →
∀ U : Matrix (Fin (n * q + 1) → Bool) (Fin (n * q + 1) → Bool) ℂ, IsQEX w U →
probEvent (act (c.unitary fun _ => U) (zeroKet m))
(fun z => let wt := WithLp.toLp 2 fun i => readFp (out i) fo z
‖wt‖ = 1 ∧ ‖wt - w‖ ≤ ε) ≥ 2 / 3 := by sorry
end QuantumLTF.Example