§6: budget concavity and equal allocations
ProvedQAlgorithms.Papers.Independent.Gap48.P46.budget_concavityAll quantum systems are nonzero finite-dimensional complex Hilbert spaces. States are positive semidefinite trace-one matrices, and channels are CPTP maps on the full matrix algebra. All entropies and logarithms are in bits. An ensemble is a finite probability distribution of states, with zero weights permitted. For a channel , write for the maximum ensemble Holevo information at mean , for the minimum average output entropy at that mean, and for the maximum of over a nonempty closed mean constraint .
Let be a channel and . Define and on , with a density. The function is nondecreasing and concave on . For every integer and ,
and the equal allocation is feasible and attains this value. Concavity is a conclusion, and capacities on empty sections are excluded.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P46
noncomputable section
namespace QAlgorithms.Papers.Independent.Gap48.P46
open scoped Matrix ComplexConjugate ENNReal ComplexOrder
open Filter
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
open QAlgorithms.Papers.Independent.Information100.P62 (tensorChannel)
open QAlgorithms.Papers.Independent.Information100.P54 (relativeEntropyBits)
open QAlgorithms.Papers.Independent.Dependency50.P23 (IsEB)
open QAlgorithms.Papers.Independent.Information100.P08
(Ensemble ensembleAverage outputHolevo mixedRoof)
variable {I O J K : Type} [Fintype I] [Fintype O] [Fintype J] [Fintype K]
variable [DecidableEq I] [DecidableEq O] [DecidableEq J] [DecidableEq K]
/-- PDF p.16, §6 and Appendix II: budget monotonicity, concavity and the allocation
maximum attained at equal budgets, for every positive block length. -/
theorem budget_concavity [Nonempty I] [Nonempty O]
(Phi : Superop I O) (hPhi : IsChannel Phi) (A : Matrix I I ℂ) (hA : A.PosSemidef) :
let f := fun alpha => constrainedChiCapacity Phi (linearConstraint A alpha)
MonotoneOn f (budgetDomain A) ∧ ConcaveOn ℝ (budgetDomain A) f ∧
∀ n : ℕ, 1 ≤ n → ∀ alpha ∈ budgetDomain A,
(fun _ : Fin n => alpha) ∈ blockAllocations A n alpha ∧
(∑ i : Fin n, f alpha) = (n : ℝ) * f alpha ∧
MaximizesValue (blockAllocations A n alpha) (fun a => ∑ i, f (a i)) ((n : ℝ) * f alpha) := by sorry
end QAlgorithms.Papers.Independent.Gap48.P46
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be finite nonempty sets with decidable equality, let be a channel from matrices on to matrices on , and let be a positive semidefinite matrix on . Here a channel has a finite representation with . A density matrix is positive semidefinite with trace ; write , let be the supremum of over finite density-matrix ensembles with nonnegative weights summing to and average , and define
Then is nondecreasing and concave on . Moreover, for every natural and every , the constant allocation belongs to , one has , and is the greatest attained value of on .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.