Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps

Definition
QAlgorithms_Papers_Independent_Intakenext100_P36

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

prove2quantum

The objects the formalized statements of Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps (arXiv:0711.3636) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • extendedInducedNorm: PDF p.2: the accepted induced Schatten norm at p=infinity, embedded in ENNReal. The real supremum is meaningful: the matrix domain is finite dimensional and phi is complex-linear. No new norm convention is introduced.
  • extendedCBNorm: PDF p.3, Definition 2: the accepted CB Schatten norm at p=infinity, embedded in ENNReal. The source's finite-matrix stabilization guarantees boundedness of the real supremum for every such phi. The accepted m=0 term adds only zero. The arbitrary-operator-space norm below instead uses a complete supremum.
  • rectangularDiamondNorm: PDF p.2, Definition 1: the induced trace norm with input-dimension ancilla; trace is unnormalized, and no factor 1/2 is used.
  • operatorSpaceBlockNorm: PDF p.4: inherited C*-matrix norm, with the canonical C*-positive order. No concrete Hilbert realization, closedness, or unit is required of a subspace.
  • operatorSpaceAmplification: PDF p.4: entrywise amplification into the ambient C*-algebra, whose inherited matrix norms restrict to the possibly nonclosed operator subspace M.
  • operatorSpaceInducedNorm: PDF pp.2,4: ordinary induced norm into the operator subspace.
  • operatorSpaceCBNorm: PDF p.4, Definition 5: all finite entrywise amplifications with the inherited C*-matrix norm. Extended values do not presuppose complete boundedness.
  • IsGeneralizedChoiKraus: PDF p.8: arbitrary finite generalized Choi–Kraus representation, including empty families for the zero map; no Kraus normalization is imposed.
  • factorizationCost: PDF p.8: row/column factorization cost, with the source's asymmetric stars.
  • representationCosts: PDF p.8, Corollary 20: costs of all actual finite representations of phi.
  • firstReducedLeft: PDF p.10, Step 2: D_j is computed from the supplied coefficients.
  • BasisReduction: PDF p.10, Steps 1–3: only basis choices and their coordinates are fields. Independence of the final right family and the norm formula are theorem content.
  • reducedRight: PDF p.10, Step 3: the final right family is computed from the second coordinates.
  • changedLeft: PDF p.10, Step 4: G_j=sum_i (S^-1)_(i,j) E_i.
  • changedRight: PDF p.10, Step 4: H_i=sum_j S_(i,j) F_j; no transpose or conjugation.
  • changeCost: PDF pp.10,17: the objective; all uses below restrict S to actual invertibles.
  • unitaryDifference: PDF p.13: the constructed map X -> U X U-adjoint - X on all matrices.
  • IsSmallestSpectralDisk: PDF p.13: a smallest enclosing disk, not the diameter of the spectral set.
  • exampleUnitary: Example 27, PDF p.19: the actual diagonal matrix, in the printed order.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_ChannelDiamondNorm
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P50
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P49

/-! Johnston–Kribs–Paulsen, arXiv:0711.3636v1. All page citations are PDF pages.
Norm comparisons and infima take values in ENNReal. Finite matrix norms reuse
the accepted real-valued norms; arbitrary-operator-space suprema retain infinity
until finite bounds are asserted. Matrix norms are the frozen Euclidean operator norm
and unnormalized trace norm. Pinned accepted-library imports supply matrix/map types and the bilinear trace dual.
The extended and rectangular norm adapters below have different interfaces from
the accepted real-valued and endomorphism-only norms. Only the eight selected paper results are targets;
cited background and ambiguous runtime claims are recorded in HARD.md. -/

noncomputable section

open scoped Matrix ComplexConjugate ENNReal ComplexOrder

namespace QAlgorithms.Papers.Independent.Intakenext100.P36

-- Reuse the pinned full-matrix and complex-linear map types without redeclaring them.
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.2: the accepted induced Schatten norm at p=infinity, embedded in ENNReal.
The real supremum is meaningful: the matrix domain is finite dimensional and phi
is complex-linear. No new norm convention is introduced. -/
def extendedInducedNorm {n k : ℕ} (phi : Map n k) : ℝ≥0∞ :=
  ENNReal.ofReal (QAlgorithms.Papers.Independent.Information100.P50.inducedNorm ⊤ phi)

/-- PDF p.3, Definition 2: the accepted CB Schatten norm at p=infinity,
embedded in ENNReal. The source's finite-matrix stabilization guarantees boundedness
of the real supremum for every such phi. The accepted m=0 term adds only zero.
The arbitrary-operator-space norm below instead uses a complete supremum. -/
def extendedCBNorm {n k : ℕ} (phi : Map n k) : ℝ≥0∞ :=
  ENNReal.ofReal (QAlgorithms.Papers.Independent.Information100.P50.cbNorm ⊤ phi)

/-- PDF p.2, Definition 1: the induced trace norm with input-dimension ancilla;
trace is unnormalized, and no factor 1/2 is used. -/
def rectangularDiamondNorm {n k : ℕ} (phi : Map n k) : ℝ≥0∞ :=
  ⨆ X : Matrix (Fin n × Fin n) (Fin n × Fin n) ℂ,
    ⨆ (_ : traceNorm X ≤ 1),
      ENNReal.ofReal (traceNorm (idTensorSuperop (R := Fin n) phi X))

/-- PDF p.4: inherited C*-matrix norm, with the canonical C*-positive order.
No concrete Hilbert realization, closedness, or unit is required of a subspace. -/
def operatorSpaceBlockNorm {A : Type*} [NonUnitalCStarAlgebra A] {m : ℕ}
    (Y : Matrix (Fin m) (Fin m) A) : ℝ := by
  letI : PartialOrder A := CStarAlgebra.spectralOrder A
  letI : StarOrderedRing A := CStarAlgebra.spectralOrderedRing A
  exact ‖CStarMatrix.ofMatrix Y‖

/-- PDF p.4: entrywise amplification into the ambient C*-algebra, whose inherited
matrix norms restrict to the possibly nonclosed operator subspace M. -/
def operatorSpaceAmplification {A : Type*} [NonUnitalCStarAlgebra A]
    {n m : ℕ} {M : Submodule ℂ A} (phi : Mat n →ₗ[ℂ] M)
    (X : Matrix (Fin m × Fin n) (Fin m × Fin n) ℂ) : Matrix (Fin m) (Fin m) A :=
  fun i j => (phi (fun a b => X (i, a) (j, b)) : A)

/-- PDF pp.2,4: ordinary induced norm into the operator subspace. -/
def operatorSpaceInducedNorm {A : Type*} [NonUnitalCStarAlgebra A]
    {n : ℕ} {M : Submodule ℂ A} (phi : Mat n →ₗ[ℂ] M) : ℝ≥0∞ :=
  ⨆ X : Mat n, ⨆ (_ : specNorm X ≤ 1), ENNReal.ofReal ‖(phi X : A)‖

/-- PDF p.4, Definition 5: all finite entrywise amplifications with the inherited
C*-matrix norm. Extended values do not presuppose complete boundedness. -/
def operatorSpaceCBNorm {A : Type*} [NonUnitalCStarAlgebra A]
    {n : ℕ} {M : Submodule ℂ A} (phi : Mat n →ₗ[ℂ] M) : ℝ≥0∞ :=
  ⨆ m : ℕ, ⨆ (_ : 0 < m),
    ⨆ X : Matrix (Fin m × Fin n) (Fin m × Fin n) ℂ,
      ⨆ (_ : specNorm X ≤ 1),
        ENNReal.ofReal (operatorSpaceBlockNorm (operatorSpaceAmplification phi X))

/-- PDF p.8: arbitrary finite generalized Choi–Kraus representation, including
empty families for the zero map; no Kraus normalization is imposed. -/
def IsGeneralizedChoiKraus {n k m : ℕ} (phi : Map n k)
    (A : Fin m → Matrix (Fin k) (Fin n) ℂ)
    (B : Fin m → Matrix (Fin n) (Fin k) ℂ) : Prop :=
  ∀ X, phi X = ∑ i, A i * X * B i

/-- PDF p.8: row/column factorization cost, with the source's asymmetric stars. -/
def factorizationCost {n k m : ℕ}
    (A : Fin m → Matrix (Fin k) (Fin n) ℂ)
    (B : Fin m → Matrix (Fin n) (Fin k) ℂ) : ℝ :=
  Real.sqrt (specNorm (∑ i, A i * (A i)ᴴ)) *
    Real.sqrt (specNorm (∑ i, (B i)ᴴ * B i))

/-- PDF p.8, Corollary 20: costs of all actual finite representations of phi. -/
def representationCosts {n k : ℕ} (phi : Map n k) : Set ℝ≥0∞ :=
  {r | ∃ m : ℕ, ∃ A : Fin m → Matrix (Fin k) (Fin n) ℂ,
    ∃ B : Fin m → Matrix (Fin n) (Fin k) ℂ,
      IsGeneralizedChoiKraus phi A B ∧ r = ENNReal.ofReal (factorizationCost A B)}

/-- PDF p.10, Step 2: D_j is computed from the supplied coefficients. -/
def firstReducedLeft {n k m l : ℕ}
    (A : Fin m → Matrix (Fin k) (Fin n) ℂ) (d : Fin m → Fin l → ℂ)
    (j : Fin l) : Matrix (Fin k) (Fin n) ℂ := ∑ i, d i j • A i

/-- PDF p.10, Steps 1–3: only basis choices and their coordinates are fields.
Independence of the final right family and the norm formula are theorem content. -/
structure BasisReduction {n k m : ℕ}
    (A : Fin m → Matrix (Fin k) (Fin n) ℂ)
    (B : Fin m → Matrix (Fin n) (Fin k) ℂ) where
  l : ℕ
  C : Fin l → Matrix (Fin n) (Fin k) ℂ
  C_independent : LinearIndependent ℂ C
  C_span : Submodule.span ℂ (Set.range C) = Submodule.span ℂ (Set.range B)
  d : Fin m → Fin l → ℂ
  B_coordinates : ∀ i, B i = ∑ j, d i j • C j
  p : ℕ
  E : Fin p → Matrix (Fin k) (Fin n) ℂ
  E_independent : LinearIndependent ℂ E
  E_span : Submodule.span ℂ (Set.range E) =
    Submodule.span ℂ (Set.range (firstReducedLeft A d))
  c : Fin l → Fin p → ℂ
  D_coordinates : ∀ j, firstReducedLeft A d j = ∑ i, c j i • E i

/-- PDF p.10, Step 3: the final right family is computed from the second coordinates. -/
def reducedRight {n k m : ℕ}
    {A : Fin m → Matrix (Fin k) (Fin n) ℂ}
    {B : Fin m → Matrix (Fin n) (Fin k) ℂ} (r : BasisReduction A B)
    (i : Fin r.p) : Matrix (Fin n) (Fin k) ℂ := ∑ j, r.c j i • r.C j

/-- PDF p.10, Step 4: G_j=sum_i (S^-1)_(i,j) E_i. -/
def changedLeft {n k p : ℕ} (E : Fin p → Matrix (Fin k) (Fin n) ℂ)
    (S : Mat p) (j : Fin p) : Matrix (Fin k) (Fin n) ℂ :=
  ∑ i, (S⁻¹) i j • E i

/-- PDF p.10, Step 4: H_i=sum_j S_(i,j) F_j; no transpose or conjugation. -/
def changedRight {n k p : ℕ} (F : Fin p → Matrix (Fin n) (Fin k) ℂ)
    (S : Mat p) (i : Fin p) : Matrix (Fin n) (Fin k) ℂ := ∑ j, S i j • F j

/-- PDF pp.10,17: the objective; all uses below restrict S to actual invertibles. -/
def changeCost {n k p : ℕ} (E : Fin p → Matrix (Fin k) (Fin n) ℂ)
    (F : Fin p → Matrix (Fin n) (Fin k) ℂ) (S : Mat p) : ℝ :=
  factorizationCost (changedLeft E S) (changedRight F S)

/-- PDF p.13: the constructed map X -> U X U-adjoint - X on all matrices. -/
def unitaryDifference {n : ℕ} (U : Mat n) : Map n n where
  toFun X := conjSuperop U X - X
  map_add' X Y := by
    simp only [conjSuperop, Matrix.mul_add, Matrix.add_mul]
    abel
  map_smul' c X := by
    simp [conjSuperop, Matrix.mul_smul, Matrix.smul_mul, smul_sub]

/-- PDF p.13: a smallest enclosing disk, not the diameter of the spectral set. -/
def IsSmallestSpectralDisk {n : ℕ} (U : Mat n) (center : ℂ) (radius : ℝ) : Prop :=
  0 ≤ radius ∧ (∀ z ∈ spectrum ℂ U, dist z center ≤ radius) ∧
    ∀ (c : ℂ) (r : ℝ), 0 ≤ r → (∀ z ∈ spectrum ℂ U, dist z c ≤ r) → radius ≤ r

/-- Example 27, PDF p.19: the actual diagonal matrix, in the printed order. -/
def exampleUnitary : Mat 3 :=
  Matrix.diagonal ![Complex.exp (((5 * Real.pi / 4 : ℝ) : ℂ) * Complex.I),
    Complex.exp (((Real.pi : ℝ) : ℂ) * Complex.I),
    Complex.exp (((3 * Real.pi / 4 : ℝ) : ℂ) * Complex.I)]

/-- Sanity: empty sums supply the zero representation, including zero dimensions. -/
example {n k : ℕ} (A : Fin 0 → Matrix (Fin k) (Fin n) ℂ)
    (B : Fin 0 → Matrix (Fin n) (Fin k) ℂ) : IsGeneralizedChoiKraus (0 : Map n k) A B := by
  intro X
  simp

/-- Sanity: the empty objective is exactly zero. -/
example {n k : ℕ} (A : Fin 0 → Matrix (Fin k) (Fin n) ℂ)
    (B : Fin 0 → Matrix (Fin n) (Fin k) ℂ) : factorizationCost A B = 0 := by
  letI : NormedAddCommGroup (Matrix (Fin k) (Fin k) ℂ) :=
    Matrix.instL2OpNormedAddCommGroup
  simp [factorizationCost, specNorm]

/-- Sanity: entrywise amplification of zero is zero in the actual ambient algebra. -/
example {A : Type*} [NonUnitalCStarAlgebra A] {n m : ℕ} (M : Submodule ℂ A)
    (X : Matrix (Fin m × Fin n) (Fin m × Fin n) ℂ) :
    operatorSpaceAmplification (0 : Mat n →ₗ[ℂ] M) X = 0 := by
  ext i j
  change (((0 : Mat n →ₗ[ℂ] M) (fun a b => X (i, a) (j, b))) : A) = 0
  exact congrArg (fun z : M => (z : A)) (LinearMap.zero_apply _)

/-- Sanity: the constructed unitary difference vanishes on the identity unitary. -/
example {n : ℕ} (X : Mat n) : unitaryDifference (1 : Mat n) X = 0 := by
  simp [unitaryDifference, conjSuperop]

/-- Sanity: the bilinear trace dual of zero is zero, without any hidden conjugation. -/
example {n k : ℕ} : traceDual (0 : Map n k) = 0 := by
  ext X i j
  change (∑ a : Fin k, ∑ b : Fin k, (0 : ℂ) * X a b) = 0
  simp

end QAlgorithms.Papers.Independent.Intakenext100.P36
Source
Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps, arXiv:0711.3636v1, https://arxiv.org/abs/0711.3636v1
Read-back

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

QAlgorithms.Papers.Independent.Intakenext100.P36.BasisReduction

For natural numbers n,k,mn,k,mn,k,m and fixed families Ai∈Mk×n(C)A_i\in M_{k\times n}(\mathbb C)Ai​∈Mk×n​(C), Bi∈Mn×k(C)B_i\in M_{n\times k}(\mathbb C)Bi​∈Mn×k​(C), indexed by 0≤i<m0\le i<m0≤i<m, this structure consists of natural numbers l,pl,pl,p, a complex-linearly independent family Cj∈Mn×k(C)C_j\in M_{n\times k}(\mathbb C)Cj​∈Mn×k​(C) indexed by j<lj<lj<l, coefficients dij∈Cd_{ij}\in\mathbb Cdij​∈C, a complex-linearly independent family Eh∈Mk×n(C)E_h\in M_{k\times n}(\mathbb C)Eh​∈Mk×n​(C) indexed by h<ph<ph<p, and coefficients cjh∈Cc_{jh}\in\mathbb Ccjh​∈C, satisfying

span⁡C{Cj:j<l}=span⁡C{Bi:i<m},Bi=∑j<ldijCj(i<m),\operatorname{span}_{\mathbb C}\{C_j:j<l\} =\operatorname{span}_{\mathbb C}\{B_i:i<m\}, \qquad B_i=\sum_{j<l}d_{ij}C_j\quad(i<m),spanC​{Cj​:j<l}=spanC​{Bi​:i<m},Bi​=j<l∑​dij​Cj​(i<m), span⁡C{Eh:h<p}=span⁡C{∑i<mdijAi:j<l},∑i<mdijAi=∑h<pcjhEh(j<l).\operatorname{span}_{\mathbb C}\{E_h:h<p\} =\operatorname{span}_{\mathbb C}\left\{\sum_{i<m}d_{ij}A_i:j<l\right\}, \qquad \sum_{i<m}d_{ij}A_i=\sum_{h<p}c_{jh}E_h\quad(j<l).spanC​{Eh​:h<p}=spanC​{i<m∑​dij​Ai​:j<l},i<m∑​dij​Ai​=h<p∑​cjh​Eh​(j<l).

No independence is required of the original AiA_iAi​ or BiB_iBi​, and no map representation is part of the structure. Every size may be zero; empty sums are zero, empty spans are the zero subspace, and independence and coordinate conditions on empty indexed families are vacuous.

QAlgorithms.Papers.Independent.Intakenext100.P36.IsGeneralizedChoiKraus

For natural numbers n,k,mn,k,mn,k,m, a complex-linear map ϕ:Mn(C)→Mk(C)\phi:M_n(\mathbb C)\to M_k(\mathbb C)ϕ:Mn​(C)→Mk​(C), matrices Ai∈Mk×n(C)A_i\in M_{k\times n}(\mathbb C)Ai​∈Mk×n​(C), and matrices Bi∈Mn×k(C)B_i\in M_{n\times k}(\mathbb C)Bi​∈Mn×k​(C), indexed by 0≤i<m0\le i<m0≤i<m, this predicate means

∀X∈Mn(C),ϕ(X)=∑i=0m−1AiXBi.\forall X\in M_n(\mathbb C),\qquad \phi(X)=\sum_{i=0}^{m-1}A_iXB_i.∀X∈Mn​(C),ϕ(X)=i=0∑m−1​Ai​XBi​.

The equality is required for every complex matrix XXX, without positivity or Hermitian restrictions. There is no condition relating AiA_iAi​ and BiB_iBi​. All dimensions and the number mmm of terms may be zero; when m=0m=0m=0, the sum is zero and the predicate says that ϕ\phiϕ is the zero map.

QAlgorithms.Papers.Independent.Intakenext100.P36.IsSmallestSpectralDisk

For any natural number nnn, complex n×nn\times nn×n matrix UUU, center z0∈Cz_0\in\mathbb Cz0​∈C, and radius r∈Rr\in\mathbb Rr∈R, this predicate means that r≥0r\ge0r≥0, every point zzz of the complex spectrum of UUU satisfies ∣z−z0∣≤r|z-z_0|\le r∣z−z0​∣≤r, and for every center c∈Cc\in\mathbb Cc∈C and every nonnegative radius sss, if ∣z−c∣≤s|z-c|\le s∣z−c∣≤s for every spectral point zzz, then r≤sr\le sr≤s. Thus the closed disk has a radius no larger than that of any closed disk containing the spectrum; uniqueness of its center is not asserted. There is no unitarity assumption, and n=0n=0n=0 is permitted; if the spectrum is empty, the conditions force r=0r=0r=0 and impose no restriction on z0z_0z0​.

QAlgorithms.Papers.Independent.Intakenext100.P36.changeCost

For natural numbers n,k,pn,k,pn,k,p, complex k×nk\times nk×n matrices EiE_iEi​, complex n×kn\times kn×k matrices FiF_iFi​, indexed by i<pi<pi<p, and an arbitrary complex p×pp\times pp×p matrix SSS, set 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​. The definition returns the real number

∥∑i<pEi′(Ei′)†∥op ∥∑i<p(Fi′)†Fi′∥op,\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}}},​i<p∑​Ei′​(Ei′​)†​op​​​i<p∑​(Fi′​)†Fi′​​op​​,

where †\dagger† denotes conjugate transpose and ∥⋅∥op\|\cdot\|_{\mathrm{op}}∥⋅∥op​ is the Euclidean operator norm. No invertibility assumption is made: the total inverse of a singular SSS is zero, making this cost zero. All dimensions may be zero, and for p=0p=0p=0 both sums, and hence the cost, are zero.

QAlgorithms.Papers.Independent.Intakenext100.P36.changedLeft

For natural numbers n,k,pn,k,pn,k,p, a family E0,…,Ep−1E_0,\ldots,E_{p-1}E0​,…,Ep−1​ of complex k×nk\times nk×n matrices, an arbitrary complex p×pp\times pp×p matrix SSS, and an index j<pj<pj<p, the definition returns

Ej′=∑i<p(S−1)ijEi.E'_j=\sum_{i<p}(S^{-1})_{ij}E_i.Ej′​=i<p∑​(S−1)ij​Ei​.

No invertibility or positivity assumption is imposed on SSS. The matrix inverse is total: for singular SSS it is the zero matrix, so every Ej′E'_jEj′​ is zero. Zero dimensions are permitted; when p=0p=0p=0, there is no index jjj.

QAlgorithms.Papers.Independent.Intakenext100.P36.changedRight

For natural numbers n,k,pn,k,pn,k,p, a family F0,…,Fp−1F_0,\ldots,F_{p-1}F0​,…,Fp−1​ of complex n×kn\times kn×k matrices, an arbitrary complex p×pp\times pp×p matrix SSS, and an index i<pi<pi<p, the definition returns

Fi′=∑j<pSijFj.F'_i=\sum_{j<p}S_{ij}F_j.Fi′​=j<p∑​Sij​Fj​.

There are no invertibility, positivity, or independence assumptions. Zero dimensions are allowed; when p=0p=0p=0, there is no index iii.

QAlgorithms.Papers.Independent.Intakenext100.P36.exampleUnitary

Defines the complex 3×33\times33×3 matrix

U=diag⁡ ⁣(e5πi/4, eπi, e3πi/4),U=\operatorname{diag}\!\left(e^{5\pi i/4},\,e^{\pi i},\,e^{3\pi i/4}\right),U=diag(e5πi/4,eπi,e3πi/4),

with these diagonal entries in index order 0,1,20,1,20,1,2 and all off-diagonal entries zero.

QAlgorithms.Papers.Independent.Intakenext100.P36.extendedCBNorm

For natural numbers n,kn,kn,k, including zero, and a complex-linear map ϕ:Mn(C)→Mk(C)\phi:M_n(\mathbb C)\to M_k(\mathbb C)ϕ:Mn​(C)→Mk​(C), this defines

ofReal⁡ ⁣(sup⁡{∥(idm⊗ϕ)(X)∥op:m∈N, X∈Mmn(C), ∥X∥op≤1}).\operatorname{ofReal}\!\left( \sup\left\{\left\|(\mathrm{id}_m\otimes\phi)(X)\right\|_{\mathrm{op}}: m\in\mathbb N,\ X\in M_{mn}(\mathbb C),\ \|X\|_{\mathrm{op}}\le1\right\}\right).ofReal(sup{∥(idm​⊗ϕ)(X)∥op​:m∈N, X∈Mmn​(C), ∥X∥op​≤1}).

Here the amplification applies ϕ\phiϕ separately to each n×nn\times nn×n block of XXX, producing an m×mm\times mm×m array of k×kk\times kk×k blocks, and every operator norm uses Euclidean coordinate norms. The amplification size m=0m=0m=0 is included. The supremum is the real-valued supremum used by the code, followed by ofReal⁡(r)=max⁡(r,0)\operatorname{ofReal}(r)=\max(r,0)ofReal(r)=max(r,0) in [0,∞][0,\infty][0,∞]; thus the resulting value is finite, and an unbounded set in this real supremum convention has supremum 000.

QAlgorithms.Papers.Independent.Intakenext100.P36.extendedInducedNorm

For natural numbers n,kn,kn,k, including zero, and a complex-linear map ϕ:Mn(C)→Mk(C)\phi:M_n(\mathbb C)\to M_k(\mathbb C)ϕ:Mn​(C)→Mk​(C), this defines the value in [0,∞][0,\infty][0,∞]

ofReal⁡ ⁣(sup⁡X∈Mn(C)∥X∥op≤1∥ϕ(X)∥op),\operatorname{ofReal}\!\left(\sup_{\substack{X\in M_n(\mathbb C)\\ \|X\|_{\mathrm{op}}\le1}}\|\phi(X)\|_{\mathrm{op}}\right),ofReal​X∈Mn​(C)∥X∥op​≤1​sup​∥ϕ(X)∥op​​,

where ∥⋅∥op\|\cdot\|_{\mathrm{op}}∥⋅∥op​ is the operator norm for the Euclidean norm on complex coordinate vectors. The supremum is taken in R\mathbb RR before applying ofReal⁡\operatorname{ofReal}ofReal, which sends a real number rrr to max⁡(r,0)\max(r,0)max(r,0), viewed as a finite extended nonnegative real. In particular, this definition does not take the supremum directly in [0,∞][0,\infty][0,∞].

QAlgorithms.Papers.Independent.Intakenext100.P36.factorizationCost

For natural numbers n,k,mn,k,mn,k,m and arbitrary families Ai∈Mk×n(C)A_i\in M_{k\times n}(\mathbb C)Ai​∈Mk×n​(C), Bi∈Mn×k(C)B_i\in M_{n\times k}(\mathbb C)Bi​∈Mn×k​(C), indexed by 0≤i<m0\le i<m0≤i<m, this defines the real number

∥∑i=0m−1AiAi∗∥op ∥∑i=0m−1Bi∗Bi∥op,\sqrt{\left\|\sum_{i=0}^{m-1}A_iA_i^*\right\|_{\mathrm{op}}}\, \sqrt{\left\|\sum_{i=0}^{m-1}B_i^*B_i\right\|_{\mathrm{op}}},​i=0∑m−1​Ai​Ai∗​​op​​​i=0∑m−1​Bi∗​Bi​​op​​,

where ∗^{*}∗ denotes conjugate transpose, the norms are Euclidean operator norms, and the square roots are real square roots. No representation identity or other hypothesis on the families is required. Zero dimensions and m=0m=0m=0 are allowed; for an empty family both sums, and hence the cost, are zero.

QAlgorithms.Papers.Independent.Intakenext100.P36.firstReducedLeft

For natural numbers n,k,m,ln,k,m,ln,k,m,l, matrices Ai∈Mk×n(C)A_i\in M_{k\times n}(\mathbb C)Ai​∈Mk×n​(C) indexed by 0≤i<m0\le i<m0≤i<m, arbitrary complex coefficients dijd_{ij}dij​ for 0≤i<m0\le i<m0≤i<m, 0≤j<l0\le j<l0≤j<l, and a specified index j<lj<lj<l, this defines

Dj=∑i=0m−1dijAi∈Mk×n(C).D_j=\sum_{i=0}^{m-1}d_{ij}A_i\in M_{k\times n}(\mathbb C).Dj​=i=0∑m−1​dij​Ai​∈Mk×n​(C).

There are no independence or coordinate hypotheses on AAA or ddd. All sizes may be zero: when m=0m=0m=0, the result is the zero matrix, and when l=0l=0l=0, there is no index jjj to which the function can be applied.

QAlgorithms.Papers.Independent.Intakenext100.P36.operatorSpaceAmplification

For any possibly nonunital complex C∗C^*C∗-algebra AAA, natural numbers n,mn,mn,m, complex-linear subspace M⊆AM\subseteq AM⊆A, complex-linear map ϕ:Mn(C)→M\phi:M_n(\mathbb C)\to Mϕ:Mn​(C)→M, and matrix XXX indexed by {0,…,m−1}×{0,…,n−1}\{0,\ldots,m-1\}\times\{0,\ldots,n-1\}{0,…,m−1}×{0,…,n−1} in both rows and columns, this defines the AAA-valued m×mm\times mm×m matrix

Yij=ϕ(Xij)∈A,(Xij)ab=X(i,a),(j,b).Y_{ij}=\phi(X_{ij})\in A,\qquad (X_{ij})_{ab}=X_{(i,a),(j,b)}.Yij​=ϕ(Xij​)∈A,(Xij​)ab​=X(i,a),(j,b)​.

Thus each n×nn\times nn×n block is mapped into MMM and then included in AAA. No positivity, norm bound, or multiplicative closure of MMM is assumed. Both dimensions may be zero; if m=0m=0m=0, the output is empty, and if n=0n=0n=0, every block is the zero element of M0(C)M_0(\mathbb C)M0​(C), so every output entry is zero.

QAlgorithms.Papers.Independent.Intakenext100.P36.operatorSpaceBlockNorm

For any possibly nonunital complex C∗C^*C∗-algebra AAA, any natural number mmm, and any matrix Y∈Mm(A)Y\in M_m(A)Y∈Mm​(A), this defines a real number as the norm of YYY in the C∗C^*C∗-algebra of matrices over AAA. The construction equips AAA with its spectral partial order and corresponding star-ordered-ring structure before viewing YYY as a C∗C^*C∗-matrix. The size m=0m=0m=0 is permitted, in which case the empty matrix has norm 000.

QAlgorithms.Papers.Independent.Intakenext100.P36.operatorSpaceCBNorm

For any possibly nonunital complex C∗C^*C∗-algebra AAA, natural number nnn, complex-linear subspace M⊆AM\subseteq AM⊆A, and complex-linear map ϕ:Mn(C)→M\phi:M_n(\mathbb C)\to Mϕ:Mn​(C)→M, this defines

sup⁡m∈N, m>0X∈Mmn(C), ∥X∥op≤1ofReal⁡ ⁣(∥[ϕ(Xij)]i,j=0m−1∥Mm(A))in [0,∞].\sup_{\substack{m\in\mathbb N,\ m>0\\ X\in M_{mn}(\mathbb C),\ \|X\|_{\mathrm{op}}\le1}} \operatorname{ofReal}\!\left(\left\|[\phi(X_{ij})]_{i,j=0}^{m-1}\right\|_{M_m(A)}\right) \quad\text{in }[0,\infty].m∈N, m>0X∈Mmn​(C), ∥X∥op​≤1​sup​ofReal(​[ϕ(Xij​)]i,j=0m−1​​Mm​(A)​)in [0,∞].

Each XijX_{ij}Xij​ is the n×nn\times nn×n block with entries X(i,a),(j,b)X_{(i,a),(j,b)}X(i,a),(j,b)​, and each ϕ(Xij)\phi(X_{ij})ϕ(Xij​) is included in AAA. The output norm is the C∗C^*C∗-matrix norm formed using the spectral order on AAA; the input norm is the Euclidean operator norm. The conversion ofReal⁡\operatorname{ofReal}ofReal truncates negative real values to zero. Only positive amplification sizes mmm are included, but n=0n=0n=0 is allowed and gives value 000.

QAlgorithms.Papers.Independent.Intakenext100.P36.operatorSpaceInducedNorm

For any possibly nonunital complex C∗C^*C∗-algebra AAA, natural number nnn, complex-linear subspace M⊆AM\subseteq AM⊆A, and complex-linear map ϕ:Mn(C)→M\phi:M_n(\mathbb C)\to Mϕ:Mn​(C)→M, this defines

sup⁡X∈Mn(C)∥X∥op≤1ofReal⁡(∥ϕ(X)∥A)in [0,∞].\sup_{\substack{X\in M_n(\mathbb C)\\ \|X\|_{\mathrm{op}}\le1}} \operatorname{ofReal}\bigl(\|\phi(X)\|_A\bigr) \quad\text{in }[0,\infty].X∈Mn​(C)∥X∥op​≤1​sup​ofReal(∥ϕ(X)∥A​)in [0,∞].

Here ∥X∥op\|X\|_{\mathrm{op}}∥X∥op​ is its Euclidean operator norm, while ϕ(X)\phi(X)ϕ(X) is included in AAA and measured using the given C∗C^*C∗-algebra norm. The conversion ofReal⁡(r)\operatorname{ofReal}(r)ofReal(r) is max⁡(r,0)\max(r,0)max(r,0). No additional assumptions on MMM or ϕ\phiϕ are imposed. The dimension n=0n=0n=0 is included and gives value 000.

QAlgorithms.Papers.Independent.Intakenext100.P36.rectangularDiamondNorm

For natural numbers n,kn,kn,k, including zero, and a complex-linear map ϕ:Mn(C)→Mk(C)\phi:M_n(\mathbb C)\to M_k(\mathbb C)ϕ:Mn​(C)→Mk​(C), this defines the extended nonnegative supremum

sup⁡X∈Mn2(C)tr⁡X∗X≤1ofReal⁡ ⁣(Re⁡tr⁡((idn⊗ϕ)(X))∗(idn⊗ϕ)(X)).\sup_{\substack{X\in M_{n^2}(\mathbb C)\\ \operatorname{tr}\sqrt{X^*X}\le1}} \operatorname{ofReal}\!\left( \operatorname{Re}\operatorname{tr} \sqrt{\bigl((\mathrm{id}_n\otimes\phi)(X)\bigr)^* (\mathrm{id}_n\otimes\phi)(X)} \right).X∈Mn2​(C)trX∗X​≤1​sup​ofReal(Retr((idn​⊗ϕ)(X))∗(idn​⊗ϕ)(X)​).

The square roots are defined by continuous functional calculus, and the input trace norm likewise means Re⁡tr⁡X∗X\operatorname{Re}\operatorname{tr}\sqrt{X^*X}RetrX∗X​. The reference factor has exactly dimension nnn: writing XijX_{ij}Xij​ for its n×nn\times nn×n input blocks, the output block at reference indices i,ji,ji,j is ϕ(Xij)\phi(X_{ij})ϕ(Xij​). There is no positivity or Hermitian assumption on XXX. The conversion ofReal⁡\operatorname{ofReal}ofReal replaces negative real values by zero. When n=0n=0n=0, both amplified matrices have empty index sets and the defined value is 000.

QAlgorithms.Papers.Independent.Intakenext100.P36.reducedRight

Let n,k,mn,k,mn,k,m be natural numbers, let A0,…,Am−1A_0,\ldots,A_{m-1}A0​,…,Am−1​ be complex k×nk\times nk×n matrices, and let B0,…,Bm−1B_0,\ldots,B_{m-1}B0​,…,Bm−1​ be complex n×kn\times kn×k matrices. A datum rrr consists of a natural number ℓ\ellℓ, linearly independent n×kn\times kn×k matrices CjC_jCj​ whose complex span equals the span of the BiB_iBi​, coefficients dijd_{ij}dij​ satisfying Bi=∑j<ℓdijCjB_i=\sum_{j<\ell}d_{ij}C_jBi​=∑j<ℓ​dij​Cj​, a natural number ppp, linearly independent k×nk\times nk×n matrices EhE_hEh​ whose span equals the span of the matrices Dj=∑i<mdijAiD_j=\sum_{i<m}d_{ij}A_iDj​=∑i<m​dij​Ai​, and coefficients cjhc_{jh}cjh​ satisfying Dj=∑h<pcjhEhD_j=\sum_{h<p}c_{jh}E_hDj​=∑h<p​cjh​Eh​. For every index i<pi<pi<p, the definition returns the n×kn\times kn×k matrix

Fi=∑j<ℓcjiCj.F_i=\sum_{j<\ell}c_{ji}C_j.Fi​=j<ℓ∑​cji​Cj​.

All dimensions may be zero; an empty sum is the zero matrix, and when p=0p=0p=0 there is no index iii at which to evaluate this family.

QAlgorithms.Papers.Independent.Intakenext100.P36.representationCosts

For natural numbers n,kn,kn,k, including zero, and a complex-linear map ϕ:Mn(C)→Mk(C)\phi:M_n(\mathbb C)\to M_k(\mathbb C)ϕ:Mn​(C)→Mk​(C), this defines the set of all r∈[0,∞]r\in[0,\infty]r∈[0,∞] for which there exist a natural number mmm and families Ai∈Mk×n(C)A_i\in M_{k\times n}(\mathbb C)Ai​∈Mk×n​(C), Bi∈Mn×k(C)B_i\in M_{n\times k}(\mathbb C)Bi​∈Mn×k​(C), indexed by 0≤i<m0\le i<m0≤i<m, such that

ϕ(X)=∑i=0m−1AiXBifor every X∈Mn(C),r=ofReal⁡ ⁣(∥∑iAiAi∗∥op ∥∑iBi∗Bi∥op).\phi(X)=\sum_{i=0}^{m-1}A_iXB_i \quad\text{for every }X\in M_n(\mathbb C), \qquad r=\operatorname{ofReal}\!\left( \sqrt{\left\|\sum_iA_iA_i^*\right\|_{\mathrm{op}}}\, \sqrt{\left\|\sum_iB_i^*B_i\right\|_{\mathrm{op}}} \right).ϕ(X)=i=0∑m−1​Ai​XBi​for every X∈Mn​(C),r=ofReal​​i∑​Ai​Ai∗​​op​​​i∑​Bi∗​Bi​​op​​​.

Here the norms are Euclidean operator norms and ofReal⁡(s)=max⁡(s,0)\operatorname{ofReal}(s)=\max(s,0)ofReal(s)=max(s,0), viewed as a finite extended nonnegative real. Membership requires an actual finite representation with exactly that cost; no infimum or closure is taken. The choice m=0m=0m=0 is allowed and supplies cost 000 when ϕ=0\phi=0ϕ=0.

QAlgorithms.Papers.Independent.Intakenext100.P36.unitaryDifference

For every natural number nnn and every complex n×nn\times nn×n matrix UUU, the definition constructs the complex linear map

ΔU:Mn(C)→Mn(C),ΔU(X)=UXU†−X,\Delta_U:M_n(\mathbb C)\to M_n(\mathbb C), \qquad \Delta_U(X)=UXU^\dagger-X,ΔU​:Mn​(C)→Mn​(C),ΔU​(X)=UXU†−X,

where U†U^\daggerU† is the conjugate transpose. No assumption that UUU is unitary is required. The case n=0n=0n=0 is included and gives the unique, zero linear map between the zero-dimensional matrix spaces.

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