Lemma 3.3 — the Fourier transform on the centered grid
ProvedQuantumLTF.Membership.lemma_3_3linear-threshold-functionsmembership-queriesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-informationquantum-learning
, defined by , is the same as the usual quantum Fourier transform up to composition before and after with a tensor product of single-qubit unitaries: there are single-qubit unitaries with
Centering the grid therefore costs only linearly many single-qubit gates. This is [GAW19, Claim 19].
Differences from the source:
- generalization: a tensor product of b single-qubit unitaries before and after → the same tensor product on both sides; reason: Eq. (48) and the next line give this U; it specializes to the printed sentence
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Fourier import Definitions.Def_QAlgorithms_Defs_GradientMethods import Definitions.Def_QuantumLTF_Membership_tensorSingle
Formal statement
namespace QuantumLTF.Membership
open QAlgorithms
/-- **Lemma 3.3 ([GAW19, Claim 19]).** Krivcenko, Nguyen, de Wolf, *Fast Quantum Algorithms for Learning Linear Threshold Functions*,
arXiv:2609.40331, Lemma 3.3, p. 27 (PDF p. 28), Eqs. (44)–(48):
`QFT_{G_b}` is the same as the usual quantum Fourier transform up to composition before and after with
a tensor product of `b` single-qubit unitaries.
**Formalization Note.** `gridQFT b` is Eq. (44) and `qftQubits b` is Eq. (47), both with `|j⟩` read most
significant bit first. The same `U` stands on both sides (Eq. (48) and the line after it). -/
theorem lemma_3_3 (b : ℕ) :
∃ u : Fin b → Matrix Bool Bool ℂ, (∀ i, u i ∈ Matrix.unitaryGroup Bool ℂ) ∧
gridQFT b = tensorSingle u * qftQubits b * tensorSingle u := by sorry
end QuantumLTF.Membership
Source
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Lemma 3.3, Eqs. (44)–(48), p. 27 (PDF p. 28)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.