Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for The Fidelity of Recovery is Multiplicative

Definition
QAlgorithms_Papers_Independent_Intakenext100_P75

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

prove2quantum

The objects the formalized statements of The Fidelity of Recovery is Multiplicative (arXiv:1502.07973) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • generalizedRecoveryFidelity: PDF p.1, (6): optimization over every CPTP C → B map. On density inputs the objective set is nonempty (replacement channels) and bounded in [0,1].
  • marginalAD: The AD marginal of a state on (AC)D, PDF p.2, Lemma 1.
  • choiOutput: PDF p.3, (14): lift sqrt(sigma_AD) by I_B, sandwich, then trace D.
  • recovered: PDF p.1, (4): recover A from C, with B passive; output is ordered B,A,C.
  • ordinaryRecovery: PDF p.1, (4): ordinary fidelity of recovery.
  • ordinaryTensor: PDF p.2, (7): the product state grouped as BB', (AA',CC').
  • channelTensor: Tensor product of linear channels, using all matrix units (PDF p.4, (27)).
  • productRecovery: PDF p.2 after (7): a product recovery channel, canonically regrouped.
  • conditionedLastCMIBits: PDF p.1, (1): use the accepted CMI in bits after reordering B,A,C to A,C,B. The accepted CMI conditions on its middle register, so this is I(A:B|C).
  • halfRenyi: PDF p.7, (49): order-one-half divergence in bits; zero fidelity gives +infinity. There is no support-containment requirement at order one-half.
  • halfRecovery: PDF p.7, (49): optimization over all local CPTP recoveries, including channels whose individual fidelity is zero.
  • ordinaryCopies: PDF pp.6–7, tensor powers regrouped into B^n,A^n,C^n.
  • Redistribution: PDF p.5, Definition 3: a finite protocol with sender AR, receiver C and independent arbitrary shared assistance. Scratch and discarding are included in CPTP maps. Positive dimensions are encoded as successor cardinalities.
  • Redistribution.cost: PDF p.5, Definition 3: communication cost log_2 dim Q, a real number.
  • Redistribution.output: PDF p.5, (31): the full reconstructed state, with B passive and R returned. First order the input for the encoder, then reorder for the decoder.
  • fullTarget: PDF p.5: target including the sender's reference, under A ≅ A'.
  • discardReference: Trace R, leaving the tripartite density matrix for the rate formula.
  • fullCopies: PDF p.6, (34): n copies, regrouping each register across the copies.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P63
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P53
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P08
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P18
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P12

/-!
Statements from Berta and Tomamichel, arXiv:1502.07973v2.
All registers have finite nonempty complex orthonormal bases. Ordinary tripartite
states are ordered B × (A × C), to keep the passive register first.
Pinned accepted definitions supply matrices, squared fidelity, purity, partial traces,
tensor regrouping and CMI. Local definitions implement the remaining paper-specific
optimization and protocol interfaces.
-/

namespace QAlgorithms.Papers.Independent.Intakenext100.P75

open scoped Matrix ComplexOrder

open QAlgorithms.Papers.Independent.Information100.P63 (Mat)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)
open QAlgorithms.Papers.Independent.Dependency50.P18 (bipartiteTensor)

variable {A B C D Ap Bp Cp R I J K L : Type}
variable [Fintype A] [DecidableEq A] [Nonempty A]
variable [Fintype B] [DecidableEq B] [Nonempty B]
variable [Fintype C] [DecidableEq C] [Nonempty C]
variable [Fintype D] [DecidableEq D] [Nonempty D]
variable [Fintype Ap] [DecidableEq Ap] [Nonempty Ap]
variable [Fintype Bp] [DecidableEq Bp] [Nonempty Bp]
variable [Fintype Cp] [DecidableEq Cp] [Nonempty Cp]
variable [Fintype R] [DecidableEq R] [Nonempty R]

/-- PDF p.1, (6): optimization over every CPTP C → B map. On density
inputs the objective set is nonempty (replacement channels) and bounded in [0,1]. -/
noncomputable def generalizedRecoveryFidelity (rho : Mat (A × B)) (sigma : Mat (A × C)) : ℝ :=
  sSup {v | ∃ f : Superop C B, IsChannel f ∧
    v = fidelity rho (idTensorSuperop (R := A) f sigma)}

/-- The AD marginal of a state on (AC)D, PDF p.2, Lemma 1. -/
def marginalAD (sigma : Mat ((A × C) × D)) : Mat (A × D) :=
  fun x y => ∑ c, sigma ((x.1, c), x.2) ((y.1, c), y.2)

/-- PDF p.3, (14): lift sqrt(sigma_AD) by I_B, sandwich, then trace D. -/
noncomputable def choiOutput (sigma : Mat (A × D)) (t : Mat ((A × B) × D)) :
    Mat (A × B) :=
  let s := cfc Real.sqrt sigma
  let lift : Mat ((A × B) × D) := fun x y =>
    s (x.1.1, x.2) (y.1.1, y.2) * (1 : Mat B) x.1.2 y.1.2
  traceRight (lift * t * lift)

/-- PDF p.1, (4): recover A from C, with B passive; output is ordered B,A,C. -/
def recovered (rho : Mat (B × (A × C))) (f : Superop C (A × C)) : Mat (B × (A × C)) :=
  idTensorSuperop (R := B) f
    (fun b b2 => ∑ a, rho (b.1, (a, b.2)) (b2.1, (a, b2.2)))

/-- PDF p.1, (4): ordinary fidelity of recovery. -/
noncomputable def ordinaryRecovery (rho : Mat (B × (A × C))) : ℝ :=
  generalizedRecoveryFidelity rho (fun x y : B × C => ∑ a, rho (x.1, (a, x.2)) (y.1, (a, y.2)))

/-- PDF p.2, (7): the product state grouped as BB', (AA',CC'). -/
def ordinaryTensor (rho : Mat (B × (A × C))) (tau : Mat (Bp × (Ap × Cp))) :
    Mat ((B × Bp) × ((A × Ap) × (C × Cp))) :=
  fun x y => rho (x.1.1, (x.2.1.1, x.2.2.1)) (y.1.1, (y.2.1.1, y.2.2.1)) *
    tau (x.1.2, (x.2.1.2, x.2.2.2)) (y.1.2, (y.2.1.2, y.2.2.2))

/-- Tensor product of linear channels, using all matrix units (PDF p.4, (27)). -/
noncomputable def channelTensor [Fintype I] [DecidableEq I]
    [Fintype K] [DecidableEq K] (f : Superop I J) (g : Superop K L) :
    Superop (I × K) (J × L) :=
  fun x => fun o p => ∑ i, ∑ j, ∑ k, ∑ l,
    x (i, k) (j, l) * f (Matrix.single i j 1) o.1 p.1 *
      g (Matrix.single k l 1) o.2 p.2

/-- PDF p.2 after (7): a product recovery channel, canonically regrouped. -/
noncomputable def productRecovery (f : Superop C (A × C)) (g : Superop Cp (Ap × Cp)) :
    Superop (C × Cp) ((A × Ap) × (C × Cp)) :=
  fun x => (channelTensor f g x).submatrix
    (fun o => ((o.1.1, o.2.1), (o.1.2, o.2.2)))
    (fun o => ((o.1.1, o.2.1), (o.1.2, o.2.2)))

/-- PDF p.1, (1): use the accepted CMI in bits after reordering B,A,C to A,C,B.
The accepted CMI conditions on its middle register, so this is I(A:B|C). -/
noncomputable def conditionedLastCMIBits (rho : Mat (B × (A × C))) : ℝ :=
  QAlgorithms.Papers.Independent.Claimed50.P12.cmi
    (rho.submatrix (fun x : A × (C × B) => (x.2.2, (x.1, x.2.1)))
      (fun x : A × (C × B) => (x.2.2, (x.1, x.2.1))))

/-- PDF p.7, (49): order-one-half divergence in bits; zero fidelity gives +infinity.
There is no support-containment requirement at order one-half. -/
noncomputable def halfRenyi [Fintype I] [DecidableEq I] (rho sigma : Mat I) : EReal :=
  if fidelity rho sigma = 0 then ⊤ else ((-Real.logb 2 (fidelity rho sigma) : ℝ) : EReal)

/-- PDF p.7, (49): optimization over all local CPTP recoveries, including
channels whose individual fidelity is zero. -/
noncomputable def halfRecovery (rho : Mat (B × (A × C))) : EReal :=
  sInf {v | ∃ f : Superop C (A × C), IsChannel f ∧ v = halfRenyi rho (recovered rho f)}

/-- PDF pp.6–7, tensor powers regrouped into B^n,A^n,C^n. -/
def ordinaryCopies (rho : Mat (B × (A × C))) (n : ℕ) :
    Mat ((Fin n → B) × ((Fin n → A) × (Fin n → C))) :=
  fun x y => ∏ i, rho (x.1 i, (x.2.1 i, x.2.2 i)) (y.1 i, (y.2.1 i, y.2.2 i))

/-- PDF p.5, Definition 3: a finite protocol with sender AR, receiver C and
independent arbitrary shared assistance. Scratch and discarding are included in CPTP maps.
Positive dimensions are encoded as successor cardinalities. -/
structure Redistribution (A C R : Type*) [Fintype A] [DecidableEq A]
    [Fintype C] [DecidableEq C] [Fintype R] [DecidableEq R] where
  messagePred : ℕ
  alicePred : ℕ
  bobPred : ℕ
  assistance : Mat (Fin (alicePred + 1) × Fin (bobPred + 1))
  assistance_density : IsDensityMatrix assistance
  encoder : Superop ((A × R) × Fin (alicePred + 1)) (Fin (messagePred + 1) × R)
  encoder_channel : IsChannel encoder
  decoder : Superop ((C × Fin (messagePred + 1)) × Fin (bobPred + 1)) (A × C)
  decoder_channel : IsChannel decoder

/-- PDF p.5, Definition 3: communication cost log_2 dim Q, a real number. -/
noncomputable def Redistribution.cost (p : Redistribution A C R) : ℝ :=
  Real.logb 2 (p.messagePred + 1)

/-- PDF p.5, (31): the full reconstructed state, with B passive and R returned.
First order the input for the encoder, then reorder for the decoder. -/
noncomputable def Redistribution.output (p : Redistribution A C R)
    (psi : Mat (B × (R × (A × C)))) : Mat ((B × R) × (A × C)) :=
  let initial : Mat ((B × (C × Fin (p.bobPred + 1))) ×
      ((A × R) × Fin (p.alicePred + 1))) := fun x y =>
    psi (x.1.1, (x.2.1.2, (x.2.1.1, x.1.2.1)))
      (y.1.1, (y.2.1.2, (y.2.1.1, y.1.2.1))) *
    p.assistance (x.2.2, x.1.2.2) (y.2.2, y.1.2.2)
  let encoded := idTensorSuperop p.encoder initial
  let ordered : Mat ((B × R) × ((C × Fin (p.messagePred + 1)) × Fin (p.bobPred + 1))) :=
    encoded.submatrix
      (fun x => ((x.1.1, (x.2.1.1, x.2.2)), (x.2.1.2, x.1.2)))
      (fun x => ((x.1.1, (x.2.1.1, x.2.2)), (x.2.1.2, x.1.2)))
  idTensorSuperop p.decoder ordered

/-- PDF p.5: target including the sender's reference, under A ≅ A'. -/
def fullTarget (psi : Mat (B × (R × (A × C)))) : Mat ((B × R) × (A × C)) :=
  psi.submatrix (fun x => (x.1.1, (x.1.2, x.2))) (fun x => (x.1.1, (x.1.2, x.2)))

/-- Trace R, leaving the tripartite density matrix for the rate formula. -/
def discardReference (psi : Mat (B × (R × (A × C)))) : Mat (B × (A × C)) :=
  fun x y => ∑ r, psi (x.1, (r, x.2)) (y.1, (r, y.2))

/-- PDF p.6, (34): n copies, regrouping each register across the copies. -/
def fullCopies (psi : Mat (B × (R × (A × C)))) (n : ℕ) :
    Mat ((Fin n → B) × ((Fin n → R) × ((Fin n → A) × (Fin n → C)))) :=
  fun x y => ∏ i, psi (x.1 i, (x.2.1 i, (x.2.2.1 i, x.2.2.2 i)))
    (y.1 i, (y.2.1 i, (y.2.2.1 i, y.2.2.2 i)))

/-! Sanity checks pin coordinate order, full spectator blocks, zero copies and log zero. -/

example (rho : Mat (A × B)) (sigma : Mat (A × C)) :
    generalizedRecoveryFidelity rho sigma =
      sSup {v | ∃ f : Superop C B, IsChannel f ∧
        v = fidelity rho (idTensorSuperop (R := A) f sigma)} := rfl

example (rho : Mat (B × (A × C))) :
    conditionedLastCMIBits rho = QAlgorithms.Papers.Independent.Claimed50.P12.cmi
      (rho.submatrix (fun x : A × (C × B) => (x.2.2, (x.1, x.2.1)))
        (fun x : A × (C × B) => (x.2.2, (x.1, x.2.1)))) := rfl

example [Fintype I] [DecidableEq I] (x y : Mat I) :
    fidelity x y = rootFidelity x y ^ 2 := rfl

example (f : Superop C B) (x : Mat (A × C)) (a a2 : A) (b b2 : B) :
    idTensorSuperop f x (a, b) (a2, b2) =
      f (fun c c2 => x (a, c) (a2, c2)) b b2 := rfl

example (rho : Mat (A × B)) (tau : Mat (Ap × Bp)) (a : A) (b : B)
    (ap : Ap) (bp : Bp) :
    bipartiteTensor rho tau ((a, ap), (b, bp)) ((a, ap), (b, bp)) =
      rho (a, b) (a, b) * tau (ap, bp) (ap, bp) := rfl

example (rho : Mat (B × (A × C))) (x y) : ordinaryCopies rho 0 x y = 1 := by
  simp [ordinaryCopies]

example [Fintype I] [DecidableEq I] (rho sigma : Mat I)
    (h : fidelity rho sigma = 0) : halfRenyi rho sigma = ⊤ := by
  simp [halfRenyi, h]

example (psi : Mat (B × (R × (A × C)))) (b : B) (r : R) (a : A) (c : C) :
    fullTarget psi ((b, r), (a, c)) ((b, r), (a, c)) =
      psi (b, (r, (a, c))) (b, (r, (a, c))) := rfl

end QAlgorithms.Papers.Independent.Intakenext100.P75
Source
The Fidelity of Recovery is Multiplicative, arXiv:1502.07973v2, https://arxiv.org/abs/1502.07973v2
Read-back

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

QAlgorithms.Papers.Independent.Intakenext100.P75.Redistribution.cost

For finite types A,C,RA,C,RA,C,R with decidable equality and any redistribution object ppp, its cost is the real number

cost⁡(p)=log⁡2(m+1),\operatorname{cost}(p)=\log_2(m+1),cost(p)=log2​(m+1),

where mmm is its message predecessor parameter. Thus the cost depends only on the message register dimension, and it equals zero when m=0m=0m=0.

QAlgorithms.Papers.Independent.Intakenext100.P75.Redistribution

For finite types A,C,RA,C,RA,C,R, each with decidable equality, a redistribution object consists of three natural numbers m,a,bm,a,bm,a,b, a matrix η\etaη on {0,…,a}×{0,…,b}\{0,\ldots,a\}\times\{0,\ldots,b\}{0,…,a}×{0,…,b} that is positive semidefinite and has trace 111, an encoder from matrices on (A×R)×{0,…,a}(A\times R)\times\{0,\ldots,a\}(A×R)×{0,…,a} to matrices on {0,…,m}×R\{0,\ldots,m\}\times R{0,…,m}×R, and a decoder from matrices on (C×{0,…,m})×{0,…,b}(C\times\{0,\ldots,m\})\times\{0,\ldots,b\}(C×{0,…,m})×{0,…,b} to matrices on A×CA\times CA×C. Each encoder and decoder must admit a finite Kraus representation X↦∑jKjXKj†X\mapsto\sum_j K_jXK_j^\daggerX↦∑j​Kj​XKj†​ with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. The three natural numbers may be zero, so their associated register dimensions are always at least one; no nonemptiness assumption is imposed on A,C,RA,C,RA,C,R.

QAlgorithms.Papers.Independent.Intakenext100.P75.Redistribution.output

For finite types A,C,RA,C,RA,C,R with decidable equality, any type BBB, a redistribution object ppp with assistance matrix η\etaη, encoder E\mathcal EE, decoder D\mathcal DD, and register dimensions m+1,a+1,b+1m+1,a+1,b+1m+1,a+1,b+1, and any complex matrix ψ\psiψ on B×(R×(A×C))B\times(R\times(A\times C))B×(R×(A×C)), the output is the following matrix on (B×R)×(A×C)(B\times R)\times(A\times C)(B×R)×(A×C). First form the matrix XXX on (B×(C×{0,…,b}))×((A×R)×{0,…,a})(B\times(C\times\{0,\ldots,b\}))\times((A\times R)\times\{0,\ldots,a\})(B×(C×{0,…,b}))×((A×R)×{0,…,a}) with entries

X((β,(c,j)),((u,r),i)), ((β′,(c′,j′)),((u′,r′),i′))=ψ(β,(r,(u,c))), (β′,(r′,(u′,c′))) η(i,j),(i′,j′).X_{((\beta,(c,j)),((u,r),i)),\,((\beta',(c',j')),((u',r'),i'))} =\psi_{(\beta,(r,(u,c))),\,(\beta',(r',(u',c')))}\, \eta_{(i,j),(i',j')}.X((β,(c,j)),((u,r),i)),((β′,(c′,j′)),((u′,r′),i′))​=ψ(β,(r,(u,c))),(β′,(r′,(u′,c′)))​η(i,j),(i′,j′)​.

Apply E\mathcal EE to the second factor while retaining the first factor, reorder the resulting coordinates from (B×(C×{0,…,b}))×({0,…,m}×R)(B\times(C\times\{0,\ldots,b\}))\times(\{0,\ldots,m\}\times R)(B×(C×{0,…,b}))×({0,…,m}×R) to (B×R)×((C×{0,…,m})×{0,…,b})(B\times R)\times((C\times\{0,\ldots,m\})\times\{0,\ldots,b\})(B×R)×((C×{0,…,m})×{0,…,b}), and apply D\mathcal DD to the second factor while retaining B×RB\times RB×R. Here applying a map Φ\PhiΦ to the second factor means that its output entry at (s,u),(t,v)(s,u),(t,v)(s,u),(t,v) is Φ([Y(s,i),(t,j)]i,j)u,v\Phi([Y_{(s,i),(t,j)}]_{i,j})_{u,v}Φ([Y(s,i),(t,j)​]i,j​)u,v​. No positivity, normalization, or purity assumption is imposed on ψ\psiψ.

QAlgorithms.Papers.Independent.Intakenext100.P75.channelTensor

For finite index types I,KI,KI,K with decidable equality, arbitrary output index types J,LJ,LJ,L, and arbitrary functions fff from matrices on III to matrices on JJJ and ggg from matrices on KKK to matrices on LLL, this defines a function on matrices XXX on I×KI\times KI×K by

[channelTensor⁡(f,g)(X)](u,v),(u′,v′)=∑i,j∈I∑k,l∈KX(i,k),(j,l) f(Eij)u,u′ g(Ekl)v,v′.[\operatorname{channelTensor}(f,g)(X)]_{(u,v),(u',v')} = \sum_{i,j\in I}\sum_{k,l\in K} X_{(i,k),(j,l)}\,f(E_{ij})_{u,u'}\,g(E_{kl})_{v,v'}.[channelTensor(f,g)(X)](u,v),(u′,v′)​=i,j∈I∑​k,l∈K∑​X(i,k),(j,l)​f(Eij​)u,u′​g(Ekl​)v,v′​.

Here EijE_{ij}Eij​ and EklE_{kl}Ekl​ are the respective matrix units, with one entry equal to 111 and all others zero. The functions f,gf,gf,g are not assumed linear or channels; the formula uses only their values on matrix units. If either input index type is empty, the output is zero.

QAlgorithms.Papers.Independent.Intakenext100.P75.choiOutput

For finite index types A,B,DA,B,DA,B,D with decidable equality, an arbitrary matrix σ\sigmaσ on A×DA\times DA×D, and an arbitrary matrix ttt on (A×B)×D(A\times B)\times D(A×B)×D, let SSS be functional calculus applied to σ\sigmaσ using the real square-root function, and define

L((a,b),d),((a′,b′),d′)=S(a,d),(a′,d′) δb,b′.L_{((a,b),d),((a',b'),d')}=S_{(a,d),(a',d')}\,\delta_{b,b'}.L((a,b),d),((a′,b′),d′)​=S(a,d),(a′,d′)​δb,b′​.

This declaration returns the matrix on A×BA\times BA×B whose entries are

[choiOutput⁡(σ,t)](a,b),(a′,b′)=∑d∈D(LtL)((a,b),d),((a′,b′),d).[\operatorname{choiOutput}(\sigma,t)]_{(a,b),(a',b')} =\sum_{d\in D}(LtL)_{((a,b),d),((a',b'),d)}.[choiOutput(σ,t)](a,b),(a′,b′)​=d∈D∑​(LtL)((a,b),d),((a′,b′),d)​.

The two factors surrounding ttt are both LLL. Neither σ\sigmaσ nor ttt is assumed positive or normalized, and the definition imposes no condition identifying ttt as a channel’s Choi matrix. If DDD is empty, the output is zero.

QAlgorithms.Papers.Independent.Intakenext100.P75.conditionedLastCMIBits

For finite index types A,B,CA,B,CA,B,C with decidable equality and an arbitrary matrix ρ\rhoρ on B×(A×C)B\times(A\times C)B×(A×C), this defines

H(ρAC)+H(ρBC)−H(ρC)−H(ρ~),H(\rho_{AC})+H(\rho_{BC})-H(\rho_C)-H(\widetilde\rho),H(ρAC​)+H(ρBC​)−H(ρC​)−H(ρ​),

where ρ~\widetilde\rhoρ​, indexed by A×(C×B)A\times(C\times B)A×(C×B), is given by

ρ~(a,(c,b)),(a′,(c′,b′))=ρ(b,(a,c)),(b′,(a′,c′)).\widetilde\rho_{(a,(c,b)),(a',(c',b'))} =\rho_{(b,(a,c)),(b',(a',c'))}.ρ​(a,(c,b)),(a′,(c′,b′))​=ρ(b,(a,c)),(b′,(a′,c′))​.

The marginals are

(ρAC)(a,c),(a′,c′)=∑bρ(b,(a,c)),(b,(a′,c′)),(ρBC)(b,c),(b′,c′)=∑aρ(b,(a,c)),(b′,(a,c′)),(\rho_{AC})_{(a,c),(a',c')}=\sum_b\rho_{(b,(a,c)),(b,(a',c'))},\qquad (\rho_{BC})_{(b,c),(b',c')}=\sum_a\rho_{(b,(a,c)),(b',(a,c'))},(ρAC​)(a,c),(a′,c′)​=b∑​ρ(b,(a,c)),(b,(a′,c′))​,(ρBC​)(b,c),(b′,c′)​=a∑​ρ(b,(a,c)),(b′,(a,c′))​,

and (ρC)c,c′=∑b,aρ(b,(a,c)),(b,(a,c′))(\rho_C)_{c,c'}=\sum_{b,a}\rho_{(b,(a,c)),(b,(a,c'))}(ρC​)c,c′​=∑b,a​ρ(b,(a,c)),(b,(a,c′))​. For every matrix XXX, H(X)=−Re⁡tr⁡h(X)H(X)=-\operatorname{Re}\operatorname{tr}h(X)H(X)=−Retrh(X), with h(x)=xlog⁡2xh(x)=x\log_2xh(x)=xlog2​x applied by functional calculus. No positivity or normalization hypothesis is imposed on ρ\rhoρ.

QAlgorithms.Papers.Independent.Intakenext100.P75.discardReference

For types A,B,CA,B,CA,B,C, a finite type RRR, and any complex matrix ψ\psiψ on B×(R×(A×C))B\times(R\times(A\times C))B×(R×(A×C)), discarding the reference produces the matrix on B×(A×C)B\times(A\times C)B×(A×C) whose entries are

discardReference⁡(ψ)(b,(a,c)), (b′,(a′,c′))=∑r∈Rψ(b,(r,(a,c))), (b′,(r,(a′,c′))).\operatorname{discardReference}(\psi)_{(b,(a,c)),\,(b',(a',c'))} =\sum_{r\in R}\psi_{(b,(r,(a,c))),\,(b',(r,(a',c')))}.discardReference(ψ)(b,(a,c)),(b′,(a′,c′))​=r∈R∑​ψ(b,(r,(a,c))),(b′,(r,(a′,c′)))​.

This is defined without a positivity or normalization assumption; if RRR is empty, the result is the zero matrix.

QAlgorithms.Papers.Independent.Intakenext100.P75.fullCopies

For any types A,B,C,RA,B,C,RA,B,C,R, any complex matrix ψ\psiψ on B×(R×(A×C))B\times(R\times(A\times C))B×(R×(A×C)), and every natural number nnn, the full copies matrix is indexed by Bn×(Rn×(An×Cn))B^n\times(R^n\times(A^n\times C^n))Bn×(Rn×(An×Cn)), where XnX^nXn denotes functions from {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} to XXX, and has entries

fullCopies⁡(ψ,n)(b,(r,(a,c))), (b′,(r′,(a′,c′)))=∏i=0n−1ψ(bi,(ri,(ai,ci))), (bi′,(ri′,(ai′,ci′))).\operatorname{fullCopies}(\psi,n)_{(b,(r,(a,c))),\,(b',(r',(a',c')))} =\prod_{i=0}^{n-1} \psi_{(b_i,(r_i,(a_i,c_i))),\,(b'_i,(r'_i,(a'_i,c'_i)))}.fullCopies(ψ,n)(b,(r,(a,c))),(b′,(r′,(a′,c′)))​=i=0∏n−1​ψ(bi​,(ri​,(ai​,ci​))),(bi′​,(ri′​,(ai′​,ci′​)))​.

All four registers are copied and grouped separately. No state assumption is required. For n=0n=0n=0, every indexing function is the unique empty function and the single matrix entry is the empty product 111.

QAlgorithms.Papers.Independent.Intakenext100.P75.fullTarget

For any types A,B,C,RA,B,C,RA,B,C,R and any complex matrix ψ\psiψ on B×(R×(A×C))B\times(R\times(A\times C))B×(R×(A×C)), the full target is the matrix on (B×R)×(A×C)(B\times R)\times(A\times C)(B×R)×(A×C) obtained solely by reassociating coordinates:

fullTarget⁡(ψ)((b,r),(a,c)), ((b′,r′),(a′,c′))=ψ(b,(r,(a,c))), (b′,(r′,(a′,c′))).\operatorname{fullTarget}(\psi)_{((b,r),(a,c)),\,((b',r'),(a',c'))} =\psi_{(b,(r,(a,c))),\,(b',(r',(a',c')))}.fullTarget(ψ)((b,r),(a,c)),((b′,r′),(a′,c′))​=ψ(b,(r,(a,c))),(b′,(r′,(a′,c′)))​.

No positivity, trace, or purity condition is required.

QAlgorithms.Papers.Independent.Intakenext100.P75.generalizedRecoveryFidelity

For finite index types A,B,CA,B,CA,B,C with decidable equality and arbitrary complex square matrices ρ\rhoρ on A×BA\times BA×B and σ\sigmaσ on A×CA\times CA×C, this defines

sup⁡fF(ρ,(idA⊗f)(σ)).\sup_f F\bigl(\rho,(\mathrm{id}_A\otimes f)(\sigma)\bigr).fsup​F(ρ,(idA​⊗f)(σ)).

Here fff ranges over maps from matrices on CCC to matrices on BBB admitting a finite Kraus representation f(X)=∑jKjXKj†f(X)=\sum_j K_jXK_j^\daggerf(X)=∑j​Kj​XKj†​ with ∑jKj†Kj=IC\sum_jK_j^\dagger K_j=I_C∑j​Kj†​Kj​=IC​. The extension acts entrywise by

[(idA⊗f)(σ)](a,b),(a′,b′)=f((σ(a,c),(a′,c′))c,c′)b,b′.[(\mathrm{id}_A\otimes f)(\sigma)]_{(a,b),(a',b')} =f\bigl((\sigma_{(a,c),(a',c')})_{c,c'}\bigr)_{b,b'}.[(idA​⊗f)(σ)](a,b),(a′,b′)​=f((σ(a,c),(a′,c′)​)c,c′​)b,b′​.

The fidelity used is

F(X,Y)=(Re⁡tr⁡X Y X)2,F(X,Y)=\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt X\,Y\,\sqrt X}\right)^2,F(X,Y)=(RetrX​YX​​)2,

where each square root means functional calculus for the real square-root function. Neither input matrix is assumed positive or normalized. The supremum is a real supremum, with value 000 if its defining set is empty or unbounded above; attainment is not part of the definition.

QAlgorithms.Papers.Independent.Intakenext100.P75.halfRecovery

For finite index types A,B,CA,B,CA,B,C with decidable equality and any matrix ρ\rhoρ on B×(A×C)B\times(A\times C)B×(A×C), this defines an extended-real infimum over all maps fff from matrices on CCC to matrices on A×CA\times CA×C with finite Kraus representations f(X)=∑jKjXKj†f(X)=\sum_jK_jXK_j^\daggerf(X)=∑j​Kj​XKj†​ satisfying ∑jKj†Kj=IC\sum_jK_j^\dagger K_j=I_C∑j​Kj†​Kj​=IC​. For each such map, define

(Rf)(b,(a,c)),(b′,(a′,c′))=f((∑α∈Aρ(b,(α,u)),(b′,(α,v)))u,v∈C)(a,c),(a′,c′),Ff=(Re⁡tr⁡ρ Rf ρ)2,(R_f)_{(b,(a,c)),(b',(a',c'))} =f\left( \left(\sum_{\alpha\in A} \rho_{(b,(\alpha,u)),(b',(\alpha,v))} \right)_{u,v\in C} \right)_{(a,c),(a',c')}, \qquad F_f=\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt\rho\,R_f\,\sqrt\rho}\right)^2,(Rf​)(b,(a,c)),(b′,(a′,c′))​=f​(α∈A∑​ρ(b,(α,u)),(b′,(α,v))​)u,v∈C​​(a,c),(a′,c′)​,Ff​=(Retrρ​Rf​ρ​​)2,

where square roots use functional calculus for the real square-root function. The quantity being minimized is +∞+\infty+∞ if Ff=0F_f=0Ff​=0, and −log⁡2Ff-\log_2F_f−log2​Ff​ otherwise. No positivity or normalization is required of ρ\rhoρ, and attainment is not asserted. The infimum of an empty set is +∞+\infty+∞.

QAlgorithms.Papers.Independent.Intakenext100.P75.halfRenyi

For a finite index type III with decidable equality and arbitrary complex square matrices ρ,σ\rho,\sigmaρ,σ on III, set

F=(Re⁡tr⁡ρ σ ρ)2,F=\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt\rho\,\sigma\,\sqrt\rho}\right)^2,F=(Retrρ​σρ​​)2,

using functional calculus for the real square-root function. This defines an extended-real value equal to +∞+\infty+∞ when F=0F=0F=0, and equal to the finite real number −log⁡2F-\log_2F−log2​F, embedded in the extended reals, otherwise. No density-matrix assumptions are made, so the definition does not require F≤1F\le1F≤1 or the resulting value to be nonnegative. An empty index type gives F=0F=0F=0 and therefore +∞+\infty+∞.

QAlgorithms.Papers.Independent.Intakenext100.P75.marginalAD

For index types A,C,DA,C,DA,C,D, with CCC finite, and any complex square matrix σ\sigmaσ indexed by (A×C)×D(A\times C)\times D(A×C)×D, this defines a matrix on A×DA\times DA×D by

[marginal⁡AD(σ)](a,d),(a′,d′)=∑c∈Cσ((a,c),d),((a′,c),d′).[\operatorname{marginal}_{AD}(\sigma)]_{(a,d),(a',d')} =\sum_{c\in C}\sigma_{((a,c),d),((a',c),d')}.[marginalAD​(σ)](a,d),(a′,d′)​=c∈C∑​σ((a,c),d),((a′,c),d′)​.

Thus the CCC coordinate is summed with the same value in the row and column. No positivity or trace condition is imposed on σ\sigmaσ; if CCC is empty, the resulting matrix is zero.

QAlgorithms.Papers.Independent.Intakenext100.P75.ordinaryCopies

For arbitrary index types A,B,CA,B,CA,B,C, any complex square matrix ρ\rhoρ on B×(A×C)B\times(A\times C)B×(A×C), and any natural number nnn, this defines a matrix indexed by (Bn)×(An×Cn)(B^n)\times(A^n\times C^n)(Bn)×(An×Cn) through

[ordinaryCopies⁡(ρ,n)](b,(a,c)),(b′,(a′,c′))=∏i=0n−1ρ(bi,(ai,ci)),(bi′,(ai′,ci′)).[\operatorname{ordinaryCopies}(\rho,n)]_{(b,(a,c)),(b',(a',c'))} = \prod_{i=0}^{n-1} \rho_{(b_i,(a_i,c_i)),(b'_i,(a'_i,c'_i))}.[ordinaryCopies(ρ,n)](b,(a,c)),(b′,(a′,c′))​=i=0∏n−1​ρ(bi​,(ai​,ci​)),(bi′​,(ai′​,ci′​))​.

Each superscript nnn denotes functions from {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} to the indicated type. No positivity, normalization, or finiteness assumption on the index types is required. For n=0n=0n=0, the empty product equals 111, so the resulting matrix has its single entry equal to 111.

QAlgorithms.Papers.Independent.Intakenext100.P75.ordinaryRecovery

For finite index types A,B,CA,B,CA,B,C with decidable equality and any complex square matrix ρ\rhoρ on B×(A×C)B\times(A\times C)B×(A×C), this defines the real supremum of F(ρ,Rf)F(\rho,R_f)F(ρ,Rf​) over all maps fff from matrices on CCC to matrices on A×CA\times CA×C having a finite Kraus representation f(X)=∑jKjXKj†f(X)=\sum_jK_jXK_j^\daggerf(X)=∑j​Kj​XKj†​ with ∑jKj†Kj=IC\sum_jK_j^\dagger K_j=I_C∑j​Kj†​Kj​=IC​, where

(Rf)(b,(a,c)),(b′,(a′,c′))=f((∑α∈Aρ(b,(α,u)),(b′,(α,v)))u,v∈C)(a,c),(a′,c′).(R_f)_{(b,(a,c)),(b',(a',c'))} =f\left( \left(\sum_{\alpha\in A} \rho_{(b,(\alpha,u)),(b',(\alpha,v))} \right)_{u,v\in C} \right)_{(a,c),(a',c')}.(Rf​)(b,(a,c)),(b′,(a′,c′))​=f​(α∈A∑​ρ(b,(α,u)),(b′,(α,v))​)u,v∈C​​(a,c),(a′,c′)​.

Here

F(X,Y)=(Re⁡tr⁡X Y X)2F(X,Y)=\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt X\,Y\,\sqrt X}\right)^2F(X,Y)=(RetrX​YX​​)2

uses functional calculus for the real square-root function. No density-matrix hypothesis is imposed on ρ\rhoρ. The real supremum is 000 if its defining set is empty or unbounded above, and the definition does not assert that it is attained.

QAlgorithms.Papers.Independent.Intakenext100.P75.ordinaryTensor

For arbitrary index types A,B,C,A′,B′,C′A,B,C,A',B',C'A,B,C,A′,B′,C′, and arbitrary matrices ρ\rhoρ on B×(A×C)B\times(A\times C)B×(A×C) and τ\tauτ on B′×(A′×C′)B'\times(A'\times C')B′×(A′×C′), this defines a matrix on (B×B′)×((A×A′)×(C×C′))(B\times B')\times((A\times A')\times(C\times C'))(B×B′)×((A×A′)×(C×C′)) by

[ordinaryTensor⁡(ρ,τ)]((b,b′),((a,a′),(c,c′))),((b~,b~′),((a~,a~′),(c~,c~′)))=ρ(b,(a,c)),(b~,(a~,c~)) τ(b′,(a′,c′)),(b~′,(a~′,c~′)).[\operatorname{ordinaryTensor}(\rho,\tau)]_{((b,b'),((a,a'),(c,c'))),((\tilde b,\tilde b'),((\tilde a,\tilde a'),(\tilde c,\tilde c')))} = \rho_{(b,(a,c)),(\tilde b,(\tilde a,\tilde c))} \,\tau_{(b',(a',c')),(\tilde b',(\tilde a',\tilde c'))}.[ordinaryTensor(ρ,τ)]((b,b′),((a,a′),(c,c′))),((b~,b~′),((a~,a~′),(c~,c~′)))​=ρ(b,(a,c)),(b~,(a~,c~))​τ(b′,(a′,c′)),(b~′,(a~′,c~′))​.

No finiteness, positivity, normalization, or other condition on the matrices is required.

QAlgorithms.Papers.Independent.Intakenext100.P75.productRecovery

For finite input index types C,C′C,C'C,C′ with decidable equality, arbitrary types A,A′A,A'A,A′, and arbitrary functions fff from matrices on CCC to matrices on A×CA\times CA×C and ggg from matrices on C′C'C′ to matrices on A′×C′A'\times C'A′×C′, this defines a function taking a matrix XXX on C×C′C\times C'C×C′ to a matrix on (A×A′)×(C×C′)(A\times A')\times(C\times C')(A×A′)×(C×C′), with entries

[productRecovery⁡(f,g)(X)]((a,a′),(c,c′)),((b,b′),(d,d′))=∑u,v∈C∑s,t∈C′X(u,s),(v,t) f(Euv)(a,c),(b,d) g(Est)(a′,c′),(b′,d′).[\operatorname{productRecovery}(f,g)(X)]_{((a,a'),(c,c')),((b,b'),(d,d'))} = \sum_{u,v\in C}\sum_{s,t\in C'} X_{(u,s),(v,t)} \,f(E_{uv})_{(a,c),(b,d)} \,g(E_{st})_{(a',c'),(b',d')}.[productRecovery(f,g)(X)]((a,a′),(c,c′)),((b,b′),(d,d′))​=u,v∈C∑​s,t∈C′∑​X(u,s),(v,t)​f(Euv​)(a,c),(b,d)​g(Est​)(a′,c′),(b′,d′)​.

The symbols EEE denote matrix units. This formula includes the regrouping of output coordinates into the displayed order. Neither fff nor ggg is assumed linear or a channel; if CCC or C′C'C′ is empty, the output is zero.

QAlgorithms.Papers.Independent.Intakenext100.P75.recovered

For index types A,B,CA,B,CA,B,C, with AAA finite, an arbitrary matrix ρ\rhoρ on B×(A×C)B\times(A\times C)B×(A×C), and any function fff from matrices on CCC to matrices on A×CA\times CA×C, this defines a matrix on B×(A×C)B\times(A\times C)B×(A×C) by

[recovered⁡(ρ,f)](b,(a,c)),(b′,(a′,c′))=f((∑α∈Aρ(b,(α,u)),(b′,(α,v)))u,v∈C)(a,c),(a′,c′).[\operatorname{recovered}(\rho,f)]_{(b,(a,c)),(b',(a',c'))} =f\left( \left(\sum_{\alpha\in A} \rho_{(b,(\alpha,u)),(b',(\alpha,v))} \right)_{u,v\in C} \right)_{(a,c),(a',c')}.[recovered(ρ,f)](b,(a,c)),(b′,(a′,c′))​=f​(α∈A∑​ρ(b,(α,u)),(b′,(α,v))​)u,v∈C​​(a,c),(a′,c′)​.

Thus it sums out the original AAA coordinate and applies fff separately to each matrix block specified by b,b′b,b'b,b′. There is no assumption that fff is linear or a channel, or that ρ\rhoρ is positive or normalized. When AAA is empty, the matrix supplied to fff is zero, without any requirement that f(0)=0f(0)=0f(0)=0.

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