Optimum recovery is an attained semidefinite program
ProvedQAlgorithms.Papers.Independent.Dependency50.P40.optimumRecoverySDPLet and , with , and fix a density operator on and a CPTP noise channel with finite Kraus operators . For any normalized purification of , define . With output-first, unnormalized operator kets, put . Then
Both maxima are attained. Every recovery gives a feasible with this objective, and every feasible is the Choi matrix of a CPTP recovery. This identifies the exact recovery problem with an SDP; it supplies no bit-complexity claim.
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P40
noncomputable section
namespace QAlgorithms.Papers.Independent.Dependency50.P40
open scoped ComplexConjugate ComplexOrder Matrix
open QAlgorithms.Papers.Independent.Information100.P34 (dyad)
/-- PDF pp.1–4, abstract and (7), (22): the exact recovery SDP has an attained maximum.
Every feasible Choi matrix is included, and every CPTP recovery is compared. -/
theorem optimumRecoverySDP {h k a m : ℕ} (hh : 0 < h) (hk : 0 < k)
(rho : Matrix (Fin h) (Fin h) ℂ) (hrho : IsDensityMatrix rho)
(psi : EuclideanSpace ℂ (Fin a × Fin h)) (hpsi : IsPurification rho psi)
(E : Fin m → Matrix (Fin k) (Fin h) ℂ) (hE : IsKrausFamily E) :
(∀ R : Superop (Fin k) (Fin h), IsChannel R →
ChoiFeasible (outputFirstChoi R) ∧ purificationFidelity psi (R ∘ krausApply E) =
(outputFirstChoi R * recoveryCoefficient rho E).trace.re) ∧
(∀ X : Matrix (Fin h × Fin k) (Fin h × Fin k) ℂ, ChoiFeasible X →
∃ R : Superop (Fin k) (Fin h), IsChannel R ∧ outputFirstChoi R = X) ∧
∃ (R : Superop (Fin k) (Fin h))
(X : Matrix (Fin h × Fin k) (Fin h × Fin k) ℂ),
IsChannel R ∧ outputFirstChoi R = X ∧ ChoiFeasible X ∧
purificationFidelity psi (R ∘ krausApply E) =
(X * recoveryCoefficient rho E).trace.re ∧
(∀ Y, ChoiFeasible Y → (Y * recoveryCoefficient rho E).trace.re ≤
(X * recoveryCoefficient rho E).trace.re) ∧
(∀ S : Superop (Fin k) (Fin h), IsChannel S →
purificationFidelity psi (S ∘ krausApply E) ≤
purificationFidelity psi (R ∘ krausApply E)) := by sorry
end QAlgorithms.Papers.Independent.Dependency50.P40
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For all natural numbers with and , let be a complex positive semidefinite matrix with , let have Euclidean norm and satisfy , and let be complex matrices satisfying . Write . A channel from dimension to dimension means a function on matrices having a finite representation for every , with . Define its output-first Choi matrix by , where has its only nonzero entry, , at ; call a matrix indexed by feasible when is positive semidefinite and . For a matrix , write for the vector with coordinates , and set
Here an outer product has entries . For an endomorphism on matrices, let
where the extension applies separately to each block indexed by a pair of reference indices. Then every channel from dimension to dimension has feasible and satisfies ; every feasible is for some such channel ; and there exist such a channel and feasible for which
The parameters have no explicit positivity hypotheses, but is incompatible with , and is incompatible with the Kraus identity when .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.