Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit SDPs for completely bounded norms

Open
QAlgorithms.Papers.Independent.Intakenext100.P98.completelyBoundedNorms_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, where n,m≥1n,m\ge1n,m≥1, and let Φ:L(X)→L(Y)\Phi:L(X)\to L(Y)Φ:L(X)→L(Y) be complex-linear. Suppose A,B:X→Y⊗ZA,B:X\to Y\otimes ZA,B:X→Y⊗Z satisfy Φ(T)=Tr⁡Z(ATB∗)\Phi(T)=\operatorname{Tr}_Z(ATB^*)Φ(T)=TrZ​(ATB∗) for every operator TTT, with dim⁡Z=rank⁡J(Φ)\dim Z=\operatorname{rank}J(\Phi)dimZ=rankJ(Φ). For the output-first, unnormalized Choi matrix JJJ, construct

Ψ(TMNW)=(Tr⁡T00Tr⁡Y(W−ATA∗)),C=diag⁡(0,BB∗),D=diag⁡(1,0).\Psi\begin{pmatrix}T&M\\N&W\end{pmatrix}=\begin{pmatrix}\operatorname{Tr}T&0\\0&\operatorname{Tr}_Y(W-ATA^*)\end{pmatrix},\quad C=\operatorname{diag}(0,BB^*),\quad D=\operatorname{diag}(1,0).Ψ(TN​MW​)=(TrT0​0TrY​(W−ATA∗)​),C=diag(0,BB∗),D=diag(1,0).

Let α\alphaα be the supremum of Re⁡Tr⁡(C∗P)\operatorname{Re}\operatorname{Tr}(C^*P)ReTr(C∗P) over P⪰0P\succeq0P⪰0 with Ψ(P)⪯D\Psi(P)\preceq DΨ(P)⪯D, and let β\betaβ be the infimum of Re⁡Tr⁡(D∗S)\operatorname{Re}\operatorname{Tr}(D^*S)ReTr(D∗S) over S⪰0S\succeq0S⪰0 with Ψ∗(S)⪰C\Psi^*(S)\succeq CΨ∗(S)⪰C. Then

α=β=∥Φ∥⋄2.\alpha=\beta=\|\Phi\|_\diamond^2.α=β=∥Φ∥⋄2​.

A minimal Stinespring pair exists for the Hilbert–Schmidt adjoint Φ∗\Phi^*Φ∗, and this same construction applied to it has primal and dual values ∥Φ∥cb,∞2=∥Φ∗∥⋄2\|\Phi\|_{\mathrm{cb},\infty}^2=\|\Phi^*\|_\diamond^2∥Φ∥cb,∞2​=∥Φ∗∥⋄2​. Trace norm has no factor 1/21/21/2. At the zero map the minimal environment is allowed to have dimension zero.

These explicit programs express both completely bounded norms by finite-dimensional semidefinite optimization; the computational complexity claim is inventoried separately.

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.1,4,7--9: explicit SDP values are the SQUARED diamond norm.
Applying the construction to the adjoint gives the spectral variant.
Phi need not be positive, Hermiticity-preserving, or nonzero. -/
theorem completelyBoundedNorms_sdp {n m r : ℕ} (hn : 0 < n) (hm : 0 < m)
    (Phi : (Matrix (Fin n) (Fin n) ℂ →ₗ[ℂ] Matrix (Fin m) (Fin m) ℂ)) (A B : (Matrix (Fin m × Fin r) (Fin n) ℂ))
    (hpair : stinespringPairRepresents Phi A B) (hminimal : r = (watrousChoiMatrix Phi).rank) :
    blockPrimalValue A B = (((stabilizedTraceNorm Phi) ^ 2 : ℝ) : EReal) ∧
    blockDualValue A B = (((stabilizedTraceNorm Phi) ^ 2 : ℝ) : EReal) ∧
    ∃ (s : ℕ) (C D : (Matrix (Fin n × Fin s) (Fin m) ℂ)),
      stinespringPairRepresents (superAdjoint Phi) C D ∧ s = (watrousChoiMatrix (superAdjoint Phi)).rank ∧
      blockPrimalValue C D = (((cbSpectral Phi) ^ 2 : ℝ) : EReal) ∧
      blockDualValue C D = (((cbSpectral Phi) ^ 2 : ℝ) : EReal) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P98

end
Source
Semidefinite programs for completely bounded norms, arXiv:0901.4709v2, PDF p. 7, Abstract and §3: explicit SDPs for completely bounded trace and spectral norms
Read-back

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

Let n,m,rn,m,rn,m,r be natural numbers with n>0n>0n>0 and m>0m>0m>0, let Φ:Mn(C)→Mm(C)\Phi:M_n(\mathbb C)\to M_m(\mathbb C)Φ:Mn​(C)→Mm​(C) be any complex-linear map, and let A,B:Cn→Cm⊗CrA,B:\mathbb C^n\to\mathbb C^m\otimes\mathbb C^rA,B:Cn→Cm⊗Cr be matrices satisfying, for every X∈Mn(C)X\in M_n(\mathbb C)X∈Mn​(C),

Φ(X)=Tr⁡r(AXB†),r=rank⁡J(Φ),J(Φ)(a,i),(b,j)=Φ(Eij)ab,\Phi(X)=\operatorname{Tr}_{r}(AXB^\dagger), \qquad r=\operatorname{rank}J(\Phi), \qquad J(\Phi)_{(a,i),(b,j)}=\Phi(E_{ij})_{ab},Φ(X)=Trr​(AXB†),r=rankJ(Φ),J(Φ)(a,i),(b,j)​=Φ(Eij​)ab​,

where EijE_{ij}Eij​ is the matrix unit and (Tr⁡rT)ab=∑q=0r−1T(a,q),(b,q)(\operatorname{Tr}_{r}T)_{ab}=\sum_{q=0}^{r-1}T_{(a,q),(b,q)}(Trr​T)ab​=∑q=0r−1​T(a,q),(b,q)​. To specify the asserted values, for any matrices E,F:Ca→Cb⊗CcE,F:\mathbb C^a\to\mathbb C^b\otimes\mathbb C^cE,F:Ca→Cb⊗Cc, define p(E,F)p(E,F)p(E,F) as the extended-real supremum of Re⁡tr⁡(FF†Y)\operatorname{Re}\operatorname{tr}(FF^\dagger Y)Retr(FF†Y) over block matrices PPP with diagonal blocks X∈Ma(C)X\in M_a(\mathbb C)X∈Ma​(C), Y∈Mbc(C)Y\in M_{bc}(\mathbb C)Y∈Mbc​(C), satisfying P⪰0P\succeq0P⪰0 and diag⁡(1−tr⁡X,Tr⁡b(EXE†−Y))⪰0\operatorname{diag}(1-\operatorname{tr}X,\operatorname{Tr}_{b}(EXE^\dagger-Y))\succeq0diag(1−trX,Trb​(EXE†−Y))⪰0; define d(E,F)d(E,F)d(E,F) as the extended-real infimum of Re⁡z\operatorname{Re}zRez over block matrices SSS with upper-left scalar zzz and lower-right block Z∈Mc(C)Z\in M_c(\mathbb C)Z∈Mc​(C), satisfying S⪰0S\succeq0S⪰0 and diag⁡(zIa−E†(Ib⊗Z)E,Ib⊗Z−FF†)⪰0\operatorname{diag}(zI_a-E^\dagger(I_b\otimes Z)E,I_b\otimes Z-FF^\dagger)\succeq0diag(zIa​−E†(Ib​⊗Z)E,Ib​⊗Z−FF†)⪰0, where (Tr⁡bT)ij=∑u=0b−1T(u,i),(u,j)(\operatorname{Tr}_{b}T)_{ij}=\sum_{u=0}^{b-1}T_{(u,i),(u,j)}(Trb​T)ij​=∑u=0b−1​T(u,i),(u,j)​. For any complex-linear map Ψ:Ma(C)→Mb(C)\Psi:M_a(\mathbb C)\to M_b(\mathbb C)Ψ:Ma​(C)→Mb​(C), put

N(Ψ)=sup⁡X∈Ma2(C)∥X∥1≤1∥(ida⊗Ψ)(X)∥1,∥T∥1=Re⁡tr⁡T†T,N(\Psi)=\sup_{\substack{X\in M_{a^2}(\mathbb C)\\ \|X\|_1\le1}} \|(\mathrm{id}_a\otimes\Psi)(X)\|_1, \qquad \|T\|_1=\operatorname{Re}\operatorname{tr}\sqrt{T^\dagger T},N(Ψ)=X∈Ma2​(C)∥X∥1​≤1​sup​∥(ida​⊗Ψ)(X)∥1​,∥T∥1​=RetrT†T​,

where (ida⊗Ψ)(X)(u,i),(v,j)=Ψ((X(u,k),(v,l))k,l)ij(\mathrm{id}_a\otimes\Psi)(X)_{(u,i),(v,j)} =\Psi((X_{(u,k),(v,l)})_{k,l})_{ij}(ida​⊗Ψ)(X)(u,i),(v,j)​=Ψ((X(u,k),(v,l)​)k,l​)ij​, and this supremum is taken in R\mathbb RR. The theorem asserts

p(A,B)=N(Φ)2,d(A,B)=N(Φ)2p(A,B)=N(\Phi)^2,\qquad d(A,B)=N(\Phi)^2p(A,B)=N(Φ)2,d(A,B)=N(Φ)2

as extended-real equalities, and also asserts that there exist a natural number sss and matrices C,D:Cm→Cn⊗CsC,D:\mathbb C^m\to\mathbb C^n\otimes\mathbb C^sC,D:Cm→Cn⊗Cs such that

Φ∗(Y)=Tr⁡s(CYD†) for every Y,s=rank⁡J(Φ∗),p(C,D)=N(Φ∗)2,d(C,D)=N(Φ∗)2.\Phi^*(Y)=\operatorname{Tr}_{s}(CYD^\dagger)\ \text{for every }Y,\qquad s=\operatorname{rank}J(\Phi^*),\qquad p(C,D)=N(\Phi^*)^2,\qquad d(C,D)=N(\Phi^*)^2.Φ∗(Y)=Trs​(CYD†) for every Y,s=rankJ(Φ∗),p(C,D)=N(Φ∗)2,d(C,D)=N(Φ∗)2.

Here the map denoted Φ∗\Phi^*Φ∗ is defined entrywise by Φ∗(Y)ij=∑a,b=0m−1Φ(Eij)ab‾Yab\Phi^*(Y)_{ij}=\sum_{a,b=0}^{m-1}\overline{\Phi(E_{ij})_{ab}}Y_{ab}Φ∗(Y)ij​=∑a,b=0m−1​Φ(Eij​)ab​​Yab​; N(Φ∗)N(\Phi^*)N(Φ∗) is the quantity called the completely bounded spectral norm in the statement. No positivity or channel assumption is imposed on Φ\PhiΦ. Neither rrr nor sss is required positive; zero-dimensional environments are included, with empty partial traces equal to zero.

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