A fixed binary test yields an actual random-coding error bound
OpenQAlgorithms.Papers.Independent.Support50.P20.fixedTest_toCodeLet be any channel from a nonempty classical set to normalized trace-class states on , and let be a discrete probability distribution on . Form and its marginals. Fix an effect with , where . For every and integer , there is an actual -message code with a complete decoding POVM and average error satisfying
This provides the fixed-test coding interface underlying achievability. The right-hand side need not be below one, and no pre-existing good code or invertible measurement sum is assumed.
Formalization Note The test is represented by its diagonal blocks ; the two traces are respectively and . Every effect has these blocks, and every family of effects has a bounded direct-sum realization.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P20
noncomputable section
open Filter
open scoped ENNReal
namespace QAlgorithms.Papers.Independent.Support50.P20
attribute [local instance] Classical.propDecidable Classical.decEq
open QAlgorithms.Papers.Independent.Dependency50.P13
(IsTraceClass IsPositive operatorTrace State)
open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)
variable {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℂ H] [CompleteSpace H]
/-- PDF pp.3–4, (8): fixed-test random coding produces an actual complete
m-outcome decoding POVM. The left side is its resulting average error. The cq
test is represented exactly by its diagonal blocks, which are all the proof uses.
Completion on the square-root measurement's kernel is allowed. -/
theorem fixedTest_toCode {X I : Type*} [Nonempty X]
(b : HilbertBasis I ℂ H) (W : ClassicalInputChannel X b) (P : PMF X)
(Q : X → Effect H) (epsilonPrime c : ℝ)
(hZero : 0 ≤ epsilonPrime) (hOne : epsilonPrime < 1) (hc : 0 < c)
(hAccept : 1 - epsilonPrime ≤ cqJointAcceptance b W P Q)
(m : ℕ) (hm : 0 < m) :
∃ C : ClassicalMessageCode X H m, uniformDecodingError b W C ≤
(1 + c) * epsilonPrime + (2 + c + c⁻¹) * m * cqProductAcceptance b W P Q := by sorry
end QAlgorithms.Papers.Independent.Support50.P20
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a complete complex inner-product space with Hilbert basis , let be any nonempty type, and let assign a state to every . Here a state is a bounded complex-linear operator that is self-adjoint with nonnegative real quadratic form, has , and admits a representation with . An effect is a bounded operator for which and are self-adjoint with nonnegative real quadratic forms; write . Let be any probability mass function on , let be an effect for every , and let satisfy and . Using real probability masses, suppose
For every positive integer , there exist words and effects satisfying and
The left side is the uniformly averaged decoding error of the asserted code. The words are not required to be distinct, is included, and the bound is asserted for every positive , even when its right side exceeds .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.