Proposition 3: absolute capacity approximation bound
OpenQAlgorithms.Papers.Independent.Gap48.P46.shor_capacity_boundAll 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 and be channels, and let be a nonempty closed constraint on the second input. For , , and integer , put , where ranges over joint densities. Then
Here is the full state space of the extended input, and the displayed maximum is attained. The absolute value gives the source's two-sided approximation bound.
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 pp.11–13, Proposition 3: absolute approximation and attained maximum.
The absolute-value bars are visible on PDF p.11 but lost in text extraction. -/
theorem shor_capacity_bound [Nonempty I] [Nonempty O] [Nonempty J] [Nonempty K]
(Phi : Superop I O) (Psi : Superop J K) (hPhi : IsChannel Phi) (hPsi : IsChannel Psi)
(B : Set (Matrix J J ℂ)) (hB : Constraint B) (E : Matrix I I ℂ) (hE : IsEffect E)
(q : ℝ) (hq : q ∈ Set.Icc (0 : ℝ) 1) (d : ℕ) (hd : 1 ≤ d) :
let S := secondConstraint (I := I) B
let f := finiteTilt Phi Psi E q d
|constrainedChiCapacity (tensorChannel (shor Phi E q d) Psi)
(secondConstraint (I := I × Fin d) B) - maxValue S f| ≤
q * (Real.logb 2 (Fintype.card K) + 1) ∧ MaximizesValue S f (maxValue S f) := 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 types with decidable equality, and let be channels between their matrix spaces, each represented on every matrix by a finite Kraus family whose adjoint-products sum to the identity. Let denote positive semidefinite trace-one matrices on , let be nonempty and closed, let and be positive semidefinite matrices on , let , and let . For a channel , define as the supremum of over finite density-matrix ensembles of average , with nonnegative weights summing to , and put , where and zero terms equal . Tensor channels are defined by linearly extending their action separately on matrix-unit tensor factors. Define on matrices on , writing , as the block-diagonal output with block , an extra diagonal entry , and further diagonal entries . Put
Then
and is attained: some has , and every satisfies . No convexity of is assumed. The cases and are included; at the asserted error bound is zero, and at the logarithmic term in vanishes.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.