Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Channel-distance SDP equals half the diamond norm

Open
QAlgorithms.Papers.Independent.Intakenext100.P98.channelDistance_sdp

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

prove2quantum

Let X=CnX=\mathbb C^nX=Cn and Y=CmY=\mathbb C^mY=Cm, n,m≥1n,m\ge1n,m≥1, and let Φ0,Φ1:L(X)→L(Y)\Phi_0,\Phi_1:L(X)\to L(Y)Φ0​,Φ1​:L(X)→L(Y) be quantum channels, meaning completely positive trace-preserving maps. Put Δ=Φ0−Φ1\Delta=\Phi_0-\Phi_1Δ=Φ0​−Φ1​ and use the output-first unnormalized Choi matrix J(Δ)J(\Delta)J(Δ). With D(X)D(X)D(X) denoting positive semidefinite trace-one operators, the two optimization values satisfy

sup⁡ρ∈D(X)0⪯W⪯IY⊗ρRe⁡Tr⁡(J(Δ)∗W)=inf⁡Z⪰0Z⪰J(Δ)∥Tr⁡YZ∥∞=12∥Δ∥⋄.\sup_{\substack{\rho\in D(X)\\0\preceq W\preceq I_Y\otimes\rho}}\operatorname{Re}\operatorname{Tr}(J(\Delta)^*W) =\inf_{\substack{Z\succeq0\\Z\succeq J(\Delta)}}\|\operatorname{Tr}_Y Z\|_\infty =\frac12\|\Delta\|_\diamond.ρ∈D(X)0⪯W⪯IY​⊗ρ​sup​ReTr(J(Δ)∗W)=Z⪰0Z⪰J(Δ)​inf​∥TrY​Z∥∞​=21​∥Δ∥⋄​.

Here the diamond norm uses the full trace norm without a distance factor. This simpler formulation applies to a difference of two channels with the same input and output spaces.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P98
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder

namespace QAlgorithms.Papers.Independent.Intakenext100.P98

/-- PDF pp.11--12, Section 4: for a difference of TWO CHANNELS both SDP
values equal HALF the diamond norm, with no square. -/
theorem channelDistance_sdp {n m : ℕ} (hn : 0 < n) (hm : 0 < m)
    (Phi0 Phi1 : (Matrix (Fin n) (Fin n) ℂ →ₗ[ℂ] Matrix (Fin m) (Fin m) ℂ)) (h0 : IsChannel Phi0) (h1 : IsChannel Phi1) :
    sSup ((fun v : ℝ => (v : EReal)) '' channelPrimalValues (Phi0 - Phi1)) =
      ((stabilizedTraceNorm (Phi0 - Phi1) / 2 : ℝ) : EReal) ∧
    sInf ((fun v : ℝ => (v : EReal)) '' channelDualValues (Phi0 - Phi1)) =
      ((stabilizedTraceNorm (Phi0 - Phi1) / 2 : ℝ) : EReal) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P98

end
Source
Semidefinite programs for completely bounded norms, arXiv:0901.4709v2, PDF p. 11, §4, unnumbered: channel-distance SDP has half-diamond value
Read-back

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

For positive natural numbers n,mn,mn,m, let Φ0,Φ1:Mn(C)→Mm(C)\Phi_0,\Phi_1:M_n(\mathbb C)\to M_m(\mathbb C)Φ0​,Φ1​:Mn​(C)→Mm​(C) be complex-linear maps, each admitting a finite Kraus representation: for each j∈{0,1}j\in\{0,1\}j∈{0,1}, there are a natural number sjs_jsj​ and matrices Ej,ℓ∈Cm×nE_{j,\ell}\in\mathbb C^{m\times n}Ej,ℓ​∈Cm×n such that ∑ℓ=0sj−1Ej,ℓ†Ej,ℓ=In\sum_{\ell=0}^{s_j-1}E_{j,\ell}^{\dagger}E_{j,\ell}=I_n∑ℓ=0sj​−1​Ej,ℓ†​Ej,ℓ​=In​ and Φj(X)=∑ℓ=0sj−1Ej,ℓXEj,ℓ†\Phi_j(X)=\sum_{\ell=0}^{s_j-1}E_{j,\ell}XE_{j,\ell}^{\dagger}Φj​(X)=∑ℓ=0sj​−1​Ej,ℓ​XEj,ℓ†​ for every XXX. Here †\dagger† denotes conjugate transpose. Put Δ=Φ0−Φ1\Delta=\Phi_0-\Phi_1Δ=Φ0​−Φ1​, and define J∈Mmn(C)J\in M_{mn}(\mathbb C)J∈Mmn​(C), indexed by pairs (a,i)(a,i)(a,i) with 0≤a<m0\le a<m0≤a<m, 0≤i<n0\le i<n0≤i<n, by J(a,i),(b,j)=Δ(Eij)abJ_{(a,i),(b,j)}=\Delta(E_{ij})_{ab}J(a,i),(b,j)​=Δ(Eij​)ab​, where EijE_{ij}Eij​ is the matrix unit. Write (Tr⁡mZ)ij=∑a=0m−1Z(a,i),(a,j)(\operatorname{Tr}_m Z)_{ij}=\sum_{a=0}^{m-1}Z_{(a,i),(a,j)}(Trm​Z)ij​=∑a=0m−1​Z(a,i),(a,j)​, and let ∥⋅∥op\|\cdot\|_{\mathrm{op}}∥⋅∥op​ be the Euclidean operator norm. Define

P={Re⁡tr⁡(J†W):ρ⪰0, tr⁡ρ=1, W⪰0, Im⊗ρ−W⪰0},D={∥Tr⁡mZ∥op:Z⪰0, Z−J⪰0},\mathcal P=\left\{\operatorname{Re}\operatorname{tr}(J^\dagger W): \rho\succeq0,\ \operatorname{tr}\rho=1,\ W\succeq0,\ I_m\otimes\rho-W\succeq0\right\}, \qquad \mathcal D=\left\{\|\operatorname{Tr}_m Z\|_{\mathrm{op}}: Z\succeq0,\ Z-J\succeq0\right\},P={Retr(J†W):ρ⪰0, trρ=1, W⪰0, Im​⊗ρ−W⪰0},D={∥Trm​Z∥op​:Z⪰0, Z−J⪰0},

where ρ∈Mn(C)\rho\in M_n(\mathbb C)ρ∈Mn​(C) and W,Z∈Mmn(C)W,Z\in M_{mn}(\mathbb C)W,Z∈Mmn​(C), and ⪰0\succeq0⪰0 means positive semidefinite. For any square matrix YYY, set ∥Y∥1=Re⁡tr⁡Y†Y\|Y\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Y^\dagger Y}∥Y∥1​=RetrY†Y​, and put D=sup⁡{∥(idn⊗Δ)(X)∥1:X∈Mn2(C), ∥X∥1≤1}D=\sup\{\|(\mathrm{id}_n\otimes\Delta)(X)\|_1:X\in M_{n^2}(\mathbb C),\ \|X\|_1\le1\}D=sup{∥(idn​⊗Δ)(X)∥1​:X∈Mn2​(C), ∥X∥1​≤1}, where the amplified map applies Δ\DeltaΔ to each n×nn\times nn×n block indexed by the first tensor factor; XXX is otherwise unrestricted. Then, taking the supremum and infimum after embedding these real value sets into the extended real numbers,

sup⁡v∈Pv=D2andinf⁡v∈Dv=D2.\sup_{v\in\mathcal P}v=\frac D2 \quad\text{and}\quad \inf_{v\in\mathcal D}v=\frac D2.v∈Psup​v=2D​andv∈Dinf​v=2D​.
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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