over in characteristic 2 (trace character)
DefinitionCertRandQROM_Supplement_qftcertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
Let be a power of , , and let , , be the absolute trace. For a vector ,
where is the dot product of the unfolded words in . The inverse transform is its adjoint.
This is the transform of Yamakawa–Zhandry (Section 2.2 of their paper), which the construction uses: it sends , , to , and maps the uniform superposition over a linear code to the uniform superposition over its dual.
Formalization Note absTrace is (with computed as Nat.log 2 (card K)), trSign a is as a complex number, qft and qftInv are the transform and its adjoint. In characteristic 2 the character is real and the transform is its own inverse.
Definition code
import Mathlib
import Definitions.Def_CertRandQROM_Supplement_dualCode
set_option autoImplicit false
namespace CertRandQROM.Supplement
/-- The **absolute trace** `Tr : F_q → F_2` of a field of order `q = 2^e`,
`Tr(a) = a + a^2 + a^4 + ⋯ + a^{2^{e−1}}`, with `e = log₂ q` (used by `QFT_Σ` of [YZ24, §2.2],
footnote 6 on p.29 of Coladangelo et al., arXiv:2608.31112, sha256 b75095a2…).
**Formalization Note** The value lies in the prime field `{0, 1} ⊆ F_q` when `F_q` has
characteristic 2, which is the case for `q(λ) = 2^{2⌊log λ⌋}` (§5.2). `e` is `Nat.log 2 q`. -/
def absTrace {K : Type} [Field K] [Fintype K] (a : K) : K :=
∑ i ∈ Finset.range (Nat.log 2 (Fintype.card K)), a ^ (2 ^ i)
/-- The additive character `a ↦ (−1)^{Tr(a)}` of `F_q` (characteristic 2), as a complex number:
`1` if `Tr(a) = 0`, `−1` otherwise. -/
noncomputable def trSign {K : Type} [Field K] [Fintype K] [DecidableEq K] (a : K) : ℂ :=
if absTrace a = 0 then 1 else -1
/-- **`QFT_Σ^{⊗n}`** on `ℂ^{Σ^n}`, `Σ = F_q^m` (Construction 6.2, step 4, p.29, with footnote 6:
"We use the definition of `QFT_Σ` given in [YZ24, Section 2.2]"):
`QFT_Σ |x⟩ = q^{−m/2} Σ_{y ∈ Σ} (−1)^{Tr(x·y)} |y⟩`, and its `n`-fold tensor power is
`(QFT^{⊗n} v)(y) = q^{−nm/2} Σ_{x ∈ Σ^n} (−1)^{Tr(x·y)} v(x)` with `x·y` the unfolded dot
product (`Tr` is additive, so the tensor product of the blockwise transforms is this). -/
noncomputable def qft {K : Type} [Field K] [Fintype K] [DecidableEq K] {n m : ℕ}
(v : (Fin n → Fin m → K) → ℂ) (y : Fin n → Fin m → K) : ℂ :=
((Real.sqrt ((Fintype.card K : ℝ) ^ (n * m)))⁻¹ : ℂ) *
∑ x, trSign (unfoldDot x y) * v x
/-- **`(QFT_Σ^{−1})^{⊗n}`**: the adjoint of `qft`,
`(QFT^{−1 ⊗n} v)(x) = q^{−nm/2} Σ_{y} conj((−1)^{Tr(x·y)}) v(y)` (Construction 6.2, step 5).
**Formalization Note** It is written as the conjugate transpose of the `qft` matrix; since the
character is real and `x·y = y·x`, it coincides with `qft` (in characteristic 2 the transform
is its own inverse). -/
noncomputable def qftInv {K : Type} [Field K] [Fintype K] [DecidableEq K] {n m : ℕ}
(v : (Fin n → Fin m → K) → ℂ) (x : Fin n → Fin m → K) : ℂ :=
((Real.sqrt ((Fintype.card K : ℝ) ^ (n * m)))⁻¹ : ℂ) *
∑ y, star (trSign (unfoldDot x y)) * v y
end CertRandQROM.Supplement
Source
Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal, Unconditional Certified Randomness without Structure, arXiv:2608.31112 (sha256 b75095a2…), Construction 6.2, step 4 with footnote 6, p.29 (PDF p.31); q(λ) = 2^{2⌊log λ⌋}, §5.2, p.23 (PDF p.25)