Explicit single-qubit phases for the centered-grid QFT
DefinitionQuantumLTF_Membership_centerPhaseGatelinear-threshold-functionsmembership-queriesquantum-fourier-transformquantum-learning
Write the centered grid point represented by an integer as . Expanding separates it into the ordinary Fourier term plus one affine function of and one of . Since the binary value of is a weighted sum of its bits, each affine phase factors as a tensor product of diagonal one-qubit gates.
centerPhaseGate(b,i) is the explicit diagonal gate on bit ; the index-independent phase is divided equally among the wires. These gates make Lemma 3.3 a concrete matrix identity rather than an existential factorization.
Formalization Note The definition is used only for , so the apparent division by is never evaluated when .
Definition code
import Mathlib
namespace QuantumLTF.Membership
/-- The explicit one-qubit diagonal phase on wire `i` which converts the ordinary QFT into
the QFT on the centered grid. The constant phase is shared evenly among the `b` wires. -/
noncomputable def centerPhaseGate (b : ℕ) (i : Fin b) : Matrix Bool Bool ℂ :=
let N : ℝ := (2 : ℝ) ^ b
let c : ℝ := -(1 / 2) + 1 / (2 * N)
let weight : ℝ := (2 : ℝ) ^ (b - 1 - i.1)
let shared : ℝ := N * c ^ 2 / (2 * b)
Matrix.of fun y z =>
if y = z then
Complex.exp (2 * Real.pi * Complex.I *
((if z then c * weight else 0) + shared))
else 0
end QuantumLTF.Membership
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331v3, Lemma 3.3 and Eqs. (44)–(48), p. 27 (PDF p. 28); explicit expansion of the phases in the proof