Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact finite matrix reduction of the CB norm

Open
QAlgorithms.Papers.Independent.Intakenext100.P36.finite_matrix_reduction

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

prove2quantum

Let n,k≥1n,k\ge1n,k≥1, let ϕ:Mn→Mk\phi:M_n\to M_kϕ:Mn​→Mk​ be complex-linear, and supply any finite representation ϕ(X)=∑i=1mAiXBi\phi(X)=\sum_{i=1}^m A_iXB_iϕ(X)=∑i=1m​Ai​XBi​, where Ai∈Mk,nA_i\in M_{k,n}Ai​∈Mk,n​ and Bi∈Mn,kB_i\in M_{n,k}Bi​∈Mn,k​. Choose a basis CjC_jCj​ of the span of the BiB_iBi​ and coefficients Bi=∑jdijCjB_i=\sum_jd_{ij}C_jBi​=∑j​dij​Cj​. Put Dj=∑idijAiD_j=\sum_id_{ij}A_iDj​=∑i​dij​Ai​, choose a basis EaE_aEa​ of their span, write Dj=∑acjaEaD_j=\sum_ac_{ja}E_aDj​=∑a​cja​Ea​, and put Fa=∑jcjaCjF_a=\sum_jc_{ja}C_jFa​=∑j​cja​Cj​. Such choices exist. For every such choice, both final indexed families are linearly independent and ϕ(X)=∑aEaXFa\phi(X)=\sum_aE_aXF_aϕ(X)=∑a​Ea​XFa​.

For each invertible S∈MpS\in M_pS∈Mp​, define Hi=∑jSijFjH_i=\sum_jS_{ij}F_jHi​=∑j​Sij​Fj​ and Gj=∑i(S−1)ijEiG_j=\sum_i(S^{-1})_{ij}E_iGj​=∑i​(S−1)ij​Ei​. These also represent ϕ\phiϕ, and

∥ϕ∥cb=∥ϕ†∥⋄=inf⁡S∈GLp(C)∥∑iGiGi†∥∥∑iHi†Hi∥.\|\phi\|_{\rm cb}=\|\phi^\dagger\|_\diamond=\inf_{S\in GL_p(\mathbb C)}\sqrt{\left\|\sum_iG_iG_i^\dagger\right\|}\sqrt{\left\|\sum_iH_i^\dagger H_i\right\|}.∥ϕ∥cb​=∥ϕ†∥⋄​=S∈GLp​(C)inf​​i∑​Gi​Gi†​​​​i∑​Hi†​Hi​​​.

The same infimum results on restricting SSS to positive definite matrices. Here ϕ†\phi^\daggerϕ† is the bilinear trace dual, characterized by Tr⁡(ϕ(X)Y)=Tr⁡(Xϕ†(Y))\operatorname{Tr}(\phi(X)Y)=\operatorname{Tr}(X\phi^\dagger(Y))Tr(ϕ(X)Y)=Tr(Xϕ†(Y)). All matrix norms are Euclidean operator norms, and the diamond norm uses the unnormalized trace norm. Empty reduced families give zero cost for the zero map.

This is the paper's finite preprocessing and exact minimization reduction; it states no finite-time minimization or sampling accuracy guarantee.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P36
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ENNReal ComplexOrder

namespace QAlgorithms.Papers.Independent.Intakenext100.P36

local notation "Mat" => QAlgorithms.Papers.Independent.Information100.P50.M

local notation "Map" => QAlgorithms.Papers.Independent.Information100.P50.Lin

open QAlgorithms.Papers.Independent.Dependency50.P49 (traceDual)

/-- PDF p.10: exact finite preprocessing followed by the invertible/positive
infimum formula. This asserts no finite-time exact minimization or sampling accuracy.
The p.12 reference to only Steps 1–2 is read as both eliminations, Steps 1–3. -/
theorem finite_matrix_reduction {n k m : ℕ} (hn : 0 < n) (hk : 0 < k)
    (phi : Map n k) (A : Fin m → Matrix (Fin k) (Fin n) ℂ)
    (B : Fin m → Matrix (Fin n) (Fin k) ℂ) (hrep : IsGeneralizedChoiKraus phi A B) :
    Nonempty (BasisReduction A B) ∧
    ∀ r : BasisReduction A B,
      LinearIndependent ℂ (reducedRight r) ∧
      IsGeneralizedChoiKraus phi r.E (reducedRight r) ∧
      (∀ S : Mat r.p, IsUnit S →
        IsGeneralizedChoiKraus phi (changedLeft r.E S) (changedRight (reducedRight r) S)) ∧
      extendedCBNorm phi = rectangularDiamondNorm (traceDual phi) ∧
      extendedCBNorm phi = sInf {v : ℝ≥0∞ | ∃ S : Mat r.p, IsUnit S ∧
        v = ENNReal.ofReal (changeCost r.E (reducedRight r) S)} ∧
      extendedCBNorm phi = sInf {v : ℝ≥0∞ | ∃ S : Mat r.p, S.PosDef ∧
        v = ENNReal.ofReal (changeCost r.E (reducedRight r) S)} := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P36

end
Source
Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps, arXiv:0711.3636v1, PDF p. 10, §4.1, unnumbered main result: exact finite matrix reduction for the CB/diamond norm
Read-back

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

Let n,kn,kn,k be positive natural numbers, let mmm be any natural number, let ϕ:Mn(C)→Mk(C)\phi:M_n(\mathbb C)\to M_k(\mathbb C)ϕ:Mn​(C)→Mk​(C) be complex linear, and suppose complex matrices Ai∈Ck×nA_i\in\mathbb C^{k\times n}Ai​∈Ck×n and Bi∈Cn×kB_i\in\mathbb C^{n\times k}Bi​∈Cn×k, indexed by i<mi<mi<m, satisfy ϕ(X)=∑i<mAiXBi\phi(X)=\sum_{i<m}A_iXB_iϕ(X)=∑i<m​Ai​XBi​ for every XXX. A reduction datum consists of a natural number ℓ\ellℓ, linearly independent matrices Cj∈Cn×kC_j\in\mathbb C^{n\times k}Cj​∈Cn×k spanning the same space as the BiB_iBi​, coefficients dijd_{ij}dij​ with Bi=∑j<ℓdijCjB_i=\sum_{j<\ell}d_{ij}C_jBi​=∑j<ℓ​dij​Cj​, a natural number ppp, linearly independent matrices Eh∈Ck×nE_h\in\mathbb C^{k\times n}Eh​∈Ck×n spanning the matrices Dj=∑i<mdijAiD_j=\sum_{i<m}d_{ij}A_iDj​=∑i<m​dij​Ai​, and coefficients cjhc_{jh}cjh​ with Dj=∑h<pcjhEhD_j=\sum_{h<p}c_{jh}E_hDj​=∑h<p​cjh​Eh​. Such a datum exists. Moreover, for every such datum, put Fi=∑j<ℓcjiCjF_i=\sum_{j<\ell}c_{ji}C_jFi​=∑j<ℓ​cji​Cj​. Then the FiF_iFi​ are linearly independent, ϕ(X)=∑i<pEiXFi\phi(X)=\sum_{i<p}E_iXF_iϕ(X)=∑i<p​Ei​XFi​ for every XXX, and every invertible S∈Mp(C)S\in M_p(\mathbb C)S∈Mp​(C) gives another representation ϕ(X)=∑i<pEi′XFi′\phi(X)=\sum_{i<p}E'_iXF'_iϕ(X)=∑i<p​Ei′​XFi′​, where Ej′=∑i<p(S−1)ijEiE'_j=\sum_{i<p}(S^{-1})_{ij}E_iEj′​=∑i<p​(S−1)ij​Ei​ and Fi′=∑j<pSijFjF'_i=\sum_{j<p}S_{ij}F_jFi′​=∑j<p​Sij​Fj​. To state the remaining conclusions, let [t]+[t]_+[t]+​ denote the image of max⁡(t,0)\max(t,0)max(t,0) in [0,∞][0,\infty][0,∞], let

C(ψ)=[sup⁡q∈N, X∈Mqu(C)∥X∥op≤1∥(idq⊗ψ)(X)∥op]+for ψ:Mu(C)→Mv(C),C(\psi)=\left[\sup_{\substack{q\in\mathbb N,\ X\in M_{q\,u}(\mathbb C)\\ \|X\|_{\mathrm{op}}\le1}} \|(\mathrm{id}_q\otimes\psi)(X)\|_{\mathrm{op}}\right]_+ \quad\text{for }\psi:M_u(\mathbb C)\to M_v(\mathbb C),C(ψ)=​q∈N, X∈Mqu​(C)∥X∥op​≤1​sup​∥(idq​⊗ψ)(X)∥op​​+​for ψ:Mu​(C)→Mv​(C),

where the supremum inside brackets is taken in R\mathbb RR, and let

D(ψ)=sup⁡X∈Mu2(C)∥X∥1≤1[∥(idu⊗ψ)(X)∥1]+,∥X∥1=Re⁡tr⁡X†X.D(\psi)=\sup_{\substack{X\in M_{u^2}(\mathbb C)\\\|X\|_1\le1}} [\|(\mathrm{id}_u\otimes\psi)(X)\|_1]_+, \qquad \|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}.D(ψ)=X∈Mu2​(C)∥X∥1​≤1​sup​[∥(idu​⊗ψ)(X)∥1​]+​,∥X∥1​=RetrX†X​.

Here amplification applies ψ\psiψ to each matrix block, and the trace dual ϕ∨:Mk(C)→Mn(C)\phi^\vee:M_k(\mathbb C)\to M_n(\mathbb C)ϕ∨:Mk​(C)→Mn​(C) is characterized by tr⁡(ϕ(X)Y)=tr⁡(Xϕ∨(Y))\operatorname{tr}(\phi(X)Y)=\operatorname{tr}(X\phi^\vee(Y))tr(ϕ(X)Y)=tr(Xϕ∨(Y)). Define

c(S)=∥∑i<pEi′(Ei′)†∥op ∥∑i<p(Fi′)†Fi′∥op.c(S)= \sqrt{\left\|\sum_{i<p}E'_i(E'_i)^\dagger\right\|_{\mathrm{op}}}\, \sqrt{\left\|\sum_{i<p}(F'_i)^\dagger F'_i\right\|_{\mathrm{op}}}.c(S)=​i<p∑​Ei′​(Ei′​)†​op​​​i<p∑​(Fi′​)†Fi′​​op​​.

The conclusions are

C(ϕ)=D(ϕ∨)=inf⁡S∈Mp(C)S invertible[c(S)]+=inf⁡S∈Mp(C)S positive definite[c(S)]+.C(\phi)=D(\phi^\vee) =\inf_{\substack{S\in M_p(\mathbb C)\\S\text{ invertible}}}[c(S)]_+ =\inf_{\substack{S\in M_p(\mathbb C)\\S\text{ positive definite}}}[c(S)]_+.C(ϕ)=D(ϕ∨)=S∈Mp​(C)S invertible​inf​[c(S)]+​=S∈Mp​(C)S positive definite​inf​[c(S)]+​.

The infima are in [0,∞][0,\infty][0,∞]. No channel or positivity assumption is made on ϕ\phiϕ. Empty families, including m=0m=0m=0 and p=0p=0p=0, are included, with empty sums 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