Exact finite matrix reduction of the CB norm
OpenQAlgorithms.Papers.Independent.Intakenext100.P36.finite_matrix_reductionLet , let be complex-linear, and supply any finite representation , where and . Choose a basis of the span of the and coefficients . Put , choose a basis of their span, write , and put . Such choices exist. For every such choice, both final indexed families are linearly independent and .
For each invertible , define and . These also represent , and
The same infimum results on restricting to positive definite matrices. Here is the bilinear trace dual, characterized by . 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.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P36
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be positive natural numbers, let be any natural number, let be complex linear, and suppose complex matrices and , indexed by , satisfy for every . A reduction datum consists of a natural number , linearly independent matrices spanning the same space as the , coefficients with , a natural number , linearly independent matrices spanning the matrices , and coefficients with . Such a datum exists. Moreover, for every such datum, put . Then the are linearly independent, for every , and every invertible gives another representation , where and . To state the remaining conclusions, let denote the image of in , let
where the supremum inside brackets is taken in , and let
Here amplification applies to each matrix block, and the trace dual is characterized by . Define
The conclusions are
The infima are in . No channel or positivity assumption is made on . Empty families, including and , are included, with empty sums equal to zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.