Lemma 5.2 — discrete quantum Hermite transform
OpenQuantumLTF.Example.lemma_5_2gaussian-analysishermite-transformquantum-algorithmssection-5
For , , and a power of two , there is a discrete quantum Hermite transform which uniformly maps every normalized superposition of degrees to the corresponding superposition of discrete Hermite states with Euclidean error at most . Its gate complexity is .
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Circuit import Definitions.Def_QuantumLTF_Membership_gates12 import Definitions.Def_QuantumLTF_Example_HermiteModel
Formal statement
namespace QuantumLTF.Example
open QAlgorithms QuantumLTF.Membership
theorem lemma_5_2 :
∃ Cg Csize : ℝ, 0 < Cg ∧ 0 < Csize ∧ ∀ D q : ℕ, 2 ≤ D →
∀ η : ℝ, 0 < η → η < 1 / 2 → Real.log (1 / η) < D →
let M := 2 ^ q
Cg * (D : ℝ) ^ (9 / 4 : ℝ) * η ^ (-13 / 4 : ℝ) ≤ M →
∃ c : Circuit gates12 q,
(c.size : ℝ) ≤ Csize * (Real.log M) ^ 3 * Real.log (1 / η) ∧
∀ a : Fin D → ℂ, (∑ k, ‖a k‖ ^ 2) = 1 →
‖act c.unitary (∑ k, a k • degreeKet q k) -
∑ k, a k • discreteHermiteKet q k‖ ≤ η := by sorry
end QuantumLTF.ExampleSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, STOC 2027 submission #347, Lemma 5.2, pp. 58–59 (PDF pp. 59–60), citing JIS+26 Theorem 19.