Theorem 5.12 — quantum example-oracle lower bound
OpenQuantumLTF.Example.theorem_5_12example-oraclelinear-threshold-functionslower-boundsquantum-algorithmssection-5
For every and , any quantum learner which outputs, with probability at least , a measurable classifier of Gaussian disagreement at most from every homogeneous LTF requires calls to the quantum-example oracle or its inverse. The learner may be adaptive and improper.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_disagree import Definitions.Def_QuantumLTF_Example_qex
Formal statement
namespace QuantumLTF.Example
open QAlgorithms QuantumLTF.Membership
theorem theorem_5_12 :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n → ∀ ε : ℝ, 0 < ε → ε ≤ 1 / (8 * Real.pi) →
∀ q m (c : OracleCircuit gates12 (fun _ : Fin 1 => n * q + 1) m)
(decode : Qubits m → (EuclideanSpace ℝ (Fin n) → ℤ)),
(∀ w : EuclideanSpace ℝ (Fin n), ‖w‖ = 1 → ∀ U, IsQEX w U →
probEvent (act (c.unitary fun _ => U) (zeroKet m))
(fun z => disagree (decode z) (ltf w 0) ≤ ε) ≥ 2 / 3) →
C * n ^ (1 / 4 : ℝ) / Real.sqrt ε ≤ c.queryCount 0 := by sorry
end QuantumLTF.ExampleSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, STOC 2027 submission #347, Theorem 5.12, p. 77 (PDF p. 78); also Theorem 1.4.