Definitions for The Fidelity of Recovery is Multiplicative
DefinitionQAlgorithms_Papers_Independent_Intakenext100_P75The 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.
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
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 with decidable equality and any redistribution object , its cost is the real number
where is its message predecessor parameter. Thus the cost depends only on the message register dimension, and it equals zero when .
QAlgorithms.Papers.Independent.Intakenext100.P75.Redistribution
For finite types , each with decidable equality, a redistribution object consists of three natural numbers , a matrix on that is positive semidefinite and has trace , an encoder from matrices on to matrices on , and a decoder from matrices on to matrices on . Each encoder and decoder must admit a finite Kraus representation with . The three natural numbers may be zero, so their associated register dimensions are always at least one; no nonemptiness assumption is imposed on .
QAlgorithms.Papers.Independent.Intakenext100.P75.Redistribution.output
For finite types with decidable equality, any type , a redistribution object with assistance matrix , encoder , decoder , and register dimensions , and any complex matrix on , the output is the following matrix on . First form the matrix on with entries
Apply to the second factor while retaining the first factor, reorder the resulting coordinates from to , and apply to the second factor while retaining . Here applying a map to the second factor means that its output entry at is . No positivity, normalization, or purity assumption is imposed on .
QAlgorithms.Papers.Independent.Intakenext100.P75.channelTensor
For finite index types with decidable equality, arbitrary output index types , and arbitrary functions from matrices on to matrices on and from matrices on to matrices on , this defines a function on matrices on by
Here and are the respective matrix units, with one entry equal to and all others zero. The functions 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 with decidable equality, an arbitrary matrix on , and an arbitrary matrix on , let be functional calculus applied to using the real square-root function, and define
This declaration returns the matrix on whose entries are
The two factors surrounding are both . Neither nor is assumed positive or normalized, and the definition imposes no condition identifying as a channel’s Choi matrix. If is empty, the output is zero.
QAlgorithms.Papers.Independent.Intakenext100.P75.conditionedLastCMIBits
For finite index types with decidable equality and an arbitrary matrix on , this defines
where , indexed by , is given by
The marginals are
and . For every matrix , , with applied by functional calculus. No positivity or normalization hypothesis is imposed on .
QAlgorithms.Papers.Independent.Intakenext100.P75.discardReference
For types , a finite type , and any complex matrix on , discarding the reference produces the matrix on whose entries are
This is defined without a positivity or normalization assumption; if is empty, the result is the zero matrix.
QAlgorithms.Papers.Independent.Intakenext100.P75.fullCopies
For any types , any complex matrix on , and every natural number , the full copies matrix is indexed by , where denotes functions from to , and has entries
All four registers are copied and grouped separately. No state assumption is required. For , every indexing function is the unique empty function and the single matrix entry is the empty product .
QAlgorithms.Papers.Independent.Intakenext100.P75.fullTarget
For any types and any complex matrix on , the full target is the matrix on obtained solely by reassociating coordinates:
No positivity, trace, or purity condition is required.
QAlgorithms.Papers.Independent.Intakenext100.P75.generalizedRecoveryFidelity
For finite index types with decidable equality and arbitrary complex square matrices on and on , this defines
Here ranges over maps from matrices on to matrices on admitting a finite Kraus representation with . The extension acts entrywise by
The fidelity used is
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 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 with decidable equality and any matrix on , this defines an extended-real infimum over all maps from matrices on to matrices on with finite Kraus representations satisfying . For each such map, define
where square roots use functional calculus for the real square-root function. The quantity being minimized is if , and otherwise. No positivity or normalization is required of , and attainment is not asserted. The infimum of an empty set is .
QAlgorithms.Papers.Independent.Intakenext100.P75.halfRenyi
For a finite index type with decidable equality and arbitrary complex square matrices on , set
using functional calculus for the real square-root function. This defines an extended-real value equal to when , and equal to the finite real number , embedded in the extended reals, otherwise. No density-matrix assumptions are made, so the definition does not require or the resulting value to be nonnegative. An empty index type gives and therefore .
QAlgorithms.Papers.Independent.Intakenext100.P75.marginalAD
For index types , with finite, and any complex square matrix indexed by , this defines a matrix on by
Thus the coordinate is summed with the same value in the row and column. No positivity or trace condition is imposed on ; if is empty, the resulting matrix is zero.
QAlgorithms.Papers.Independent.Intakenext100.P75.ordinaryCopies
For arbitrary index types , any complex square matrix on , and any natural number , this defines a matrix indexed by through
Each superscript denotes functions from to the indicated type. No positivity, normalization, or finiteness assumption on the index types is required. For , the empty product equals , so the resulting matrix has its single entry equal to .
QAlgorithms.Papers.Independent.Intakenext100.P75.ordinaryRecovery
For finite index types with decidable equality and any complex square matrix on , this defines the real supremum of over all maps from matrices on to matrices on having a finite Kraus representation with , where
Here
uses functional calculus for the real square-root function. No density-matrix hypothesis is imposed on . The real supremum is 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 , and arbitrary matrices on and on , this defines a matrix on by
No finiteness, positivity, normalization, or other condition on the matrices is required.
QAlgorithms.Papers.Independent.Intakenext100.P75.productRecovery
For finite input index types with decidable equality, arbitrary types , and arbitrary functions from matrices on to matrices on and from matrices on to matrices on , this defines a function taking a matrix on to a matrix on , with entries
The symbols denote matrix units. This formula includes the regrouping of output coordinates into the displayed order. Neither nor is assumed linear or a channel; if or is empty, the output is zero.
QAlgorithms.Papers.Independent.Intakenext100.P75.recovered
For index types , with finite, an arbitrary matrix on , and any function from matrices on to matrices on , this defines a matrix on by
Thus it sums out the original coordinate and applies separately to each matrix block specified by . There is no assumption that is linear or a channel, or that is positive or normalized. When is empty, the matrix supplied to is zero, without any requirement that .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.