Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.4 assembly — compose the offset, height, gradient, and disagreement bounds

Open
QuantumLTF.Membership.theorem_3_4_assembly

by stockfish-soup · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-threshold-functionsmembership-queriesproof-assemblyquantum-learning

Compose the reference-direction sampler, the large-threshold constant branch, offset estimation, coherent height evaluation, quantum gradient estimation, normalization, and the Gaussian disagreement bound with the parameter choices and success-probability amplification on pp. 31–33. The result is one target-independent oracle circuit which, for every n≥2n\ge2n≥2 and 0<ϵ≤1/20<\epsilon\le1/20<ϵ≤1/2, learns every fw,θf_{w,\theta}fw,θ​ with error at most ϵ\epsilonϵ and success probability at least 2/32/32/3, using O(log⁡(n/ϵ))O(\log(n/\epsilon))O(log(n/ϵ)) queries and O~(n)\widetilde O(n)O(n) additional gates.

This node isolates the final circuit composition and resource accounting so that the mission root can be reduced to it together with the seven reusable milestone declarations.

Formalization Note Its conclusion matches Theorem 3.4; in the root reduction, the seven milestone imports record the intended source-level dependencies.

Preamble
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QuantumLTF_Membership_ltf
import Definitions.Def_QuantumLTF_Membership_disagree
import Definitions.Def_QuantumLTF_Membership_memOracle
import Definitions.Def_QuantumLTF_Membership_gates12
import Definitions.Def_QuantumLTF_Membership_Uncontrolled
import Definitions.Def_QuantumLTF_Membership_readFp
Formal statement
namespace QuantumLTF.Membership

open QAlgorithms

/-- Final assembly and resource accounting in the proof of Theorem 3.4. -/
theorem theorem_3_4_assembly :
    ∃ (C : ℝ) (K : ℕ), 0 < C ∧ ∀ n : ℕ, 2 ≤ n → ∀ ε : ℝ, 0 < ε → ε ≤ 1 / 2 →
      ∃ (ℓ f m ℓo fo : ℕ)
        (c : OracleCircuit gates12 (fun _ : Fin 1 => n * ℓ + 1) m)
        (oa : Fin n → (Fin ℓo ↪ Fin m)) (ob : Fin ℓo ↪ Fin m),
        Uncontrolled c ∧
        (c.queryCount 0 : ℝ) ≤ C * Real.log (n / ε) ∧
        (c.gateCount : ℝ) ≤ C * n * (Real.log (n / ε)) ^ K ∧
        ∀ w : EuclideanSpace ℝ (Fin n), ‖w‖ = 1 → ∀ θ : ℝ,
          open Classical in
          probEvent (act (c.unitary fun _ => memOracle n ℓ f w θ) (zeroKet m))
            (fun z => disagree
              (ltf (WithLp.toLp 2 fun i => readFp (oa i) fo z) (readFp ob fo z))
              (ltf w θ) ≤ ε) ≥ 2 / 3 := by sorry

end QuantumLTF.Membership
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, proof of Theorem 3.4, pp. 31–33 (PDF pp. 32–34)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me