Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, diagonalization, Fourier mixture and convolution

Proved
QAlgorithms.Papers.Independent.Bridge50.P05.weylRepresentation

by Gohan · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let d≥1d\ge1d≥1, H=CZdH=\mathbb C^{\mathbb Z_d}H=CZd​, and Z=Zd×ZdZ=\mathbb Z_d\times\mathbb Z_dZ=Zd​×Zd​. In the specified orthonormal basis let W(x,y)=UxVyW_{(x,y)}=U^xV^yW(x,y)​=UxVy, where Uek=ek+1Ue_k=e_{k+1}Uek​=ek+1​ and Vek=e2πik/dekVe_k=e^{2\pi i k/d}e_kVek​=e2πik/dek​. Write fX(z)=Tr⁡(XWz∗)/df_X(z)=\operatorname{Tr}(XW_z^*)/dfX​(z)=Tr(XWz∗​)/d. All spaces are finite dimensional. The norm ∥X∥2=Tr⁡(X∗X)\|X\|_2=\sqrt{\operatorname{Tr}(X^*X)}∥X∥2​=Tr(X∗X)​ is the Hilbert–Schmidt norm, and ν2(Φ)=sup⁡ρ≥0,Tr⁡ρ=1∥Φ(ρ)∥2\nu_2(\Phi)=\sup_{\rho\ge0,\operatorname{Tr}\rho=1}\|\Phi(\rho)\|_2ν2​(Φ)=supρ≥0,Trρ=1​∥Φ(ρ)∥2​ is the maximal output norm. A map in W1(H)W_1(H)W1​(H) is complex linear, Weyl covariant and satisfies Φ(I)=I\Phi(I)=IΦ(I)=I; it need not be positive or completely positive. Its computed symbol is ϕ(z)=fΦ(Wz)(z)\phi(z)=f_{\Phi(W_z)}(z)ϕ(z)=fΦ(Wz​)​(z). Put m(ϕ)=max⁡z≠0∣ϕ(z)∣2m(\phi)=\max_{z\ne0}|\phi(z)|^2m(ϕ)=maxz=0​∣ϕ(z)∣2 and Emax⁡(ϕ)={z≠0:∣ϕ(z)∣2=m(ϕ)}E_{\max}(\phi)=\{z\ne0:|\phi(z)|^2=m(\phi)\}Emax​(ϕ)={z=0:∣ϕ(z)∣2=m(ϕ)}. At d=1d=1d=1, explicitly set m=0m=0m=0 and Emax⁡=∅E_{\max}=\varnothingEmax​=∅. Write S(ϕ)=d−1/21+(d−1)m(ϕ)S(\phi)=d^{-1/2}\sqrt{1+(d-1)m(\phi)}S(ϕ)=d−1/21+(d−1)m(ϕ)​.

For an additive subgroup G≤ZG\le ZG≤Z, let J(x,y)=(y,−x)J(x,y)=(y,-x)J(x,y)=(y,−x), χ(γ,z)=exp⁡(2πi(γxzx+γyzy)/d)\chi(\gamma,z)=\exp(2\pi i(\gamma_xz_x+\gamma_yz_y)/d)χ(γ,z)=exp(2πi(γx​zx​+γy​zy​)/d), and G⊥={γ:χ(γ,z)=1 for every z∈G}G^\perp=\{\gamma:\chi(\gamma,z)=1\text{ for every }z\in G\}G⊥={γ:χ(γ,z)=1 for every z∈G}. The symbol ϕG,a,b\phi_{G,a,b}ϕG,a,b​ is 111 at zero, a+ba+ba+b on G∖{0}G\setminus\{0\}G∖{0}, and bbb off GGG. Define ΨG(X)=d−1∑z∈G⊥WJzXWJz∗\Psi_G(X)=d^{-1}\sum_{z\in G^\perp}W_{Jz}XW_{Jz}^*ΨG​(X)=d−1∑z∈G⊥​WJz​XWJz∗​ and ΦG,a,b(X)=aΨG(X)+bX+(1−a−b)Tr⁡(X)I/d\Phi_{G,a,b}(X)=a\Psi_G(X)+bX+(1-a-b)\operatorname{Tr}(X)I/dΦG,a,b​(X)=aΨG​(X)+bX+(1−a−b)Tr(X)I/d.

For any Weyl-covariant complex-linear maps Φ,Θ\Phi,\ThetaΦ,Θ, without assuming normalization, define pγΦ=d−2∑zϕ(z)χ(γ,z)p^\Phi_\gamma=d^{-2}\sum_z\phi(z)\chi(\gamma,z)pγΦ​=d−2∑z​ϕ(z)χ(γ,z). Then

Φ(Wz)=ϕ(z)Wz,Φ(X)=∑zfX(z)ϕ(z)Wz=∑γpγΦWJγXWJγ∗,ϕ(z)=∑γpγΦχ(γ,−z).\Phi(W_z)=\phi(z)W_z,\quad \Phi(X)=\sum_z f_X(z)\phi(z)W_z=\sum_\gamma p^\Phi_\gamma W_{J\gamma}XW_{J\gamma}^*,\quad\phi(z)=\sum_\gamma p^\Phi_\gamma\chi(\gamma,-z).Φ(Wz​)=ϕ(z)Wz​,Φ(X)=z∑​fX​(z)ϕ(z)Wz​=γ∑​pγΦ​WJγ​XWJγ∗​,ϕ(z)=γ∑​pγΦ​χ(γ,−z).

The maps commute. The symbol of their composition is the pointwise product, and its Fourier coefficients are the convolution pγ=∑ηpηΦpγ−ηΘp_\gamma=\sum_\eta p^\Phi_\eta p^\Theta_{\gamma-\eta}pγ​=∑η​pηΦ​pγ−ηΘ​; the same mixture formula holds for the composition. Conversely, the finite formula Φϕ(X)=∑zfX(z)ϕ(z)Wz\Phi_\phi(X)=\sum_z f_X(z)\phi(z)W_zΦϕ​(X)=∑z​fX​(z)ϕ(z)Wz​ has Weyl eigenvalues ϕ(z)\phi(z)ϕ(z) and is Weyl covariant for every complex symbol ϕ\phiϕ.

This identifies the diagonal, Fourier-mixture and convolution descriptions of arbitrary Weyl-covariant linear maps. No claim that every map can be rescaled to ϕ(0)=1\phi(0)=1ϕ(0)=1 is made.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Bridge50_P05
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Bridge50.P05

open scoped BigOperators Matrix Kronecker ComplexConjugate ComplexOrder ENNReal

open QAlgorithms.Papers.Independent.Information100.P34 (cyclicPhase weyl dephasing)

open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)

open QAlgorithms.Papers.Independent.Gap48.P36 (WeylLabel)

open QAlgorithms.Papers.Independent.Information100.P21 (Op)

open QAlgorithms.Papers.Independent.Information100.P50 (schattenNorm)

open QAlgorithms.Papers.Independent.Claimed50.P48
  (nu superopTensor UniversalMultiplicative rowKraus indexedKrausDilation)

open QAlgorithms.Papers.Independent.Information100.P67 (complementaryChannel)

attribute [local instance] Classical.propDecidable Classical.decEq

variable {d : ℕ} [NeZero d]

/-- Section 2, PDF pp.3--4, (2.1)--(2.2): unnormalized covariant linear maps
are diagonal, have the Fourier mixture, and compose by symbol product/weylConvolution.
No claim that a zero symbol at zero can be rescaled to one. -/
theorem weylRepresentation (Phi Psi : Op (ZMod d) →ₗ[ℂ] Op (ZMod d))
    (hPhi : WeylCovariantMap Phi) (hPsi : WeylCovariantMap Psi) :
    (∀ z, Phi (W z) = symbol Phi z • W z) ∧
    (∀ X, Phi X = multiplier (symbol Phi) X) ∧
    (∀ z, symbol Phi z = ∑ g, fourier (symbol Phi) g * duality g (-z)) ∧
    (∀ X, Phi X = ∑ g, fourier (symbol Phi) g • (W (rotateWeylLabel g) * X * (W (rotateWeylLabel g))ᴴ)) ∧
    (∀ X, Phi (Psi X) = Psi (Phi X)) ∧
    (∀ z, symbol (fun X => Phi (Psi X)) z = symbol Phi z * symbol Psi z) ∧
    (∀ g, fourier (symbol (fun X => Phi (Psi X))) g =
      weylConvolution (fourier (symbol Phi)) (fourier (symbol Psi)) g) ∧
    (∀ X, Phi (Psi X) = ∑ g,
      weylConvolution (fourier (symbol Phi)) (fourier (symbol Psi)) g •
        (W (rotateWeylLabel g) * X * (W (rotateWeylLabel g))ᴴ)) ∧
    (∀ phi : WeylLabel d → ℂ,
      (∀ z, multiplier phi (W z) = phi z • W z) ∧
      (∀ z X, multiplier phi (W z * X * (W z)ᴴ) =
        W z * multiplier phi X * (W z)ᴴ)) := by sorry

end QAlgorithms.Papers.Independent.Bridge50.P05

end
Source
On Weyl-covariant channels, arXiv:quant-ph/0510148v3, PDF p. 3, §2, diagonalization, Fourier mixture and convolution
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let ddd be a nonzero natural number, H=Z/dZH=\mathbb Z/d\mathbb ZH=Z/dZ, and Φ,Ψ\Phi,\PsiΦ,Ψ complex linear maps on matrices indexed by HHH. Define ϵ(t)=exp⁡(2πi val⁡(t)/d)\epsilon(t)=\exp(2\pi i\,\operatorname{val}(t)/d)ϵ(t)=exp(2πival(t)/d), Sa,b=1{a=b+1}S_{a,b}=\mathbf1_{\{a=b+1\}}Sa,b​=1{a=b+1}​, C=diag⁡aϵ(a)C=\operatorname{diag}_a\epsilon(a)C=diaga​ϵ(a), Wn,m=Sval⁡(n)Cval⁡(m)W_{n,m}=S^{\operatorname{val}(n)}C^{\operatorname{val}(m)}Wn,m​=Sval(n)Cval(m), and J(g1,g2)=(g2,−g1)J(g_1,g_2)=(g_2,-g_1)J(g1​,g2​)=(g2​,−g1​). For a matrix XXX, a matrix map Λ\LambdaΛ, and functions f,p,q:H2→Cf,p,q:H^2\to\mathbb Cf,p,q:H2→C, use the definitions

X^(z)=tr⁡(XWz†)d,ϕΛ(z)=Λ(Wz)^(z),Mf(X)=∑zX^(z)f(z)Wz,Ff(g)=1d2∑zf(z)ϵ(g1z1+g2z2),(p∗q)(g)=∑hp(h)q(g−h).\begin{gathered} \widehat X(z)=\frac{\operatorname{tr}(XW_z^\dagger)}d,\qquad \phi_\Lambda(z)=\widehat{\Lambda(W_z)}(z),\\ \mathcal M_f(X)=\sum_z\widehat X(z)f(z)W_z,\qquad \mathcal Ff(g)=\frac1{d^2}\sum_z f(z)\epsilon(g_1z_1+g_2z_2),\\ (p*q)(g)=\sum_h p(h)q(g-h). \end{gathered}X(z)=dtr(XWz†​)​,ϕΛ​(z)=Λ(Wz​)​(z),Mf​(X)=z∑​X(z)f(z)Wz​,Ff(g)=d21​z∑​f(z)ϵ(g1​z1​+g2​z2​),(p∗q)(g)=h∑​p(h)q(g−h).​

Assume that each Λ∈{Φ,Ψ}\Lambda\in\{\Phi,\Psi\}Λ∈{Φ,Ψ} satisfies Λ(WzXWz†)=WzΛ(X)Wz†\Lambda(W_zXW_z^\dagger)=W_z\Lambda(X)W_z^\daggerΛ(Wz​XWz†​)=Wz​Λ(X)Wz†​ for all z,Xz,Xz,X. Then all of the following hold:

Φ(Wz)=ϕΦ(z)Wz,Φ(X)=MϕΦ(X),ϕΦ(z)=∑gFϕΦ(g) ϵ(−g1z1−g2z2),Φ(X)=∑gFϕΦ(g) WJgXWJg†,Φ(Ψ(X))=Ψ(Φ(X)),ϕΦ∘Ψ(z)=ϕΦ(z)ϕΨ(z),FϕΦ∘Ψ(g)=(FϕΦ∗FϕΨ)(g),Φ(Ψ(X))=∑g(FϕΦ∗FϕΨ)(g) WJgXWJg†.\begin{gathered} \Phi(W_z)=\phi_\Phi(z)W_z,\qquad \Phi(X)=\mathcal M_{\phi_\Phi}(X),\\ \phi_\Phi(z)=\sum_g\mathcal F\phi_\Phi(g)\, \epsilon(-g_1z_1-g_2z_2),\\ \Phi(X)=\sum_g\mathcal F\phi_\Phi(g)\, W_{Jg}XW_{Jg}^\dagger,\\ \Phi(\Psi(X))=\Psi(\Phi(X)),\qquad \phi_{\Phi\circ\Psi}(z)=\phi_\Phi(z)\phi_\Psi(z),\\ \mathcal F\phi_{\Phi\circ\Psi}(g) =(\mathcal F\phi_\Phi*\mathcal F\phi_\Psi)(g),\\ \Phi(\Psi(X))=\sum_g(\mathcal F\phi_\Phi*\mathcal F\phi_\Psi)(g)\, W_{Jg}XW_{Jg}^\dagger. \end{gathered}Φ(Wz​)=ϕΦ​(z)Wz​,Φ(X)=MϕΦ​​(X),ϕΦ​(z)=g∑​FϕΦ​(g)ϵ(−g1​z1​−g2​z2​),Φ(X)=g∑​FϕΦ​(g)WJg​XWJg†​,Φ(Ψ(X))=Ψ(Φ(X)),ϕΦ∘Ψ​(z)=ϕΦ​(z)ϕΨ​(z),FϕΦ∘Ψ​(g)=(FϕΦ​∗FϕΨ​)(g),Φ(Ψ(X))=g∑​(FϕΦ​∗FϕΨ​)(g)WJg​XWJg†​.​

These equalities hold for every indicated label and every matrix XXX. In addition, for every function f:H2→Cf:H^2\to\mathbb Cf:H2→C, every label zzz, and every matrix XXX,

Mf(Wz)=f(z)Wz,Mf(WzXWz†)=WzMf(X)Wz†.\mathcal M_f(W_z)=f(z)W_z,\qquad \mathcal M_f(W_zXW_z^\dagger)=W_z\mathcal M_f(X)W_z^\dagger.Mf​(Wz​)=f(z)Wz​,Mf​(Wz​XWz†​)=Wz​Mf​(X)Wz†​.

Neither unitality nor positivity is assumed of Φ\PhiΦ or Ψ\PsiΨ; d=1d=1d=1 is included.

Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

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