Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Remark IV.12: Constructed rate-slicing decoder has failure-flag probability≤lambdaBar; on selected codebooks its maximum conditional decoding er

Open
QAlgorithms.Papers.Independent.Renew46.P43.flaggedRateSlicing

by Goku · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

For the constructed rate-slicing decoder, the rate and mean-error bounds of rate slicing hold. There is a selected union of codebooks; outside it the decoder flags failure. The first bound below concerns uncovered source words, and the second concerns the normalized conditional channel states on selected words. This is an existence assertion about the constructed decoder, not every low-average-error decoder.

P⊗n(uncovered words)≤λˉ,max⁡xn in selected codebooksPr⁡(wrong∣xn)≤λˉ.P^{\otimes n}(\text{uncovered words})\le\bar\lambda,\qquad\max_{x^n\ \text{in selected codebooks}}\Pr(\text{wrong}\mid x^n)\le\bar\lambda.P⊗n(uncovered words)≤λˉ,xn in selected codebooksmax​Pr(wrong∣xn)≤λˉ.

This is the source result with its stated operational or information-theoretic domain.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P43
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Renew46.P43

open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal Matrix.Norms.L2Operator

open Filter MeasureTheory

open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)

open QAlgorithms.Papers.Independent.Information100.P06 (Below)

open QAlgorithms.Papers.Independent.Information100.P60 (copies relativeBits)

open QAlgorithms.Papers.Independent.Dependency50.P19 (count both)

open QAlgorithms.Papers.Independent.Information100.P22 (coherentInformation)

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Claimed50.P40 (InBlocks)

attribute [local instance] QAlgorithms.Papers.Independent.Renew46.P43.matrixMeasurableSpace

/-- Remark IV.12, PDF p.54: a property of a constructed decoder, with uncovered
source mass distinguished from the maximum conditional error inside selected codebooks. -/
theorem flaggedRateSlicing (a d : ℕ) (ha : 0 < a) (hd : 0 < d)
    (lambda delta : ℝ) (hlambda : 0 < lambda) (hdelta : 0 < delta) :
    ∃ n0 : ℕ, 0 < n0 ∧ ∀ (S : HybridSource 1),
      (∀ i, S.alphabet i = a) → S.system.dim = d → ∀ n : ℕ, n0 ≤ n →
      ∃ c : SideCode S n, ∃ covered : Finset (∀ i, Fin n → Fin (S.alphabet i)),
        c.rate 0 ≤ S.subsetEntropy Finset.univ + 3 * delta ∧ c.error ≤ lambda ∧
        (∑ x ∈ (Finset.univ \ covered), ∏ t, S.classicalMass (fun i => x i t)) ≤ lambda ∧
        (∀ x ∈ covered, 1 - effectProb (wordTensor (fun t => S.conditional (fun i => x i t)))
          (c.decode (c.message x) (some x)) ≤ lambda) ∧
        (∀ x, x ∉ covered → c.decode (c.message x) none = 1) := by sorry

end QAlgorithms.Papers.Independent.Renew46.P43

end
Source
Coding Theorems of Quantum Information Theory, arXiv:quant-ph/9907077v1, PDF p. 54, Remark IV.12
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every a,d∈Na,d\in\mathbb Na,d∈N with a,d>0a,d>0a,d>0 and every λ,δ∈R\lambda,\delta\in\mathbb Rλ,δ∈R with λ,δ>0\lambda,\delta>0λ,δ>0, there exists n0>0n_0>0n0​>0 such that, for every one-sender hybrid source SSS with classical alphabet size aaa and quantum dimension ddd, and every n≥n0n\ge n_0n≥n0​, the following objects exist. The source may have arbitrary quantum basis block labels, any r>0r>0r>0 distinct normalized pure states σp\sigma_pσp​ supported within those blocks, and any joint probability masses μ(x,p)\mu(x,p)μ(x,p) summing to 111. Define m(x)=∑pμ(x,p)m(x)=\sum_p\mu(x,p)m(x)=∑p​μ(x,p) and ρx=σ0\rho_x=\sigma_0ρx​=σ0​ if m(x)=0m(x)=0m(x)=0, otherwise ρx=∑pμ(x,p)σp/m(x)\rho_x=\sum_p\mu(x,p)\sigma_p/m(x)ρx​=∑p​μ(x,p)σp​/m(x); define ΩXQ((x,u),(y,v))=1{x=y}∑pμ(x,p)σp(u,v)\Omega_{XQ}((x,u),(y,v))=\mathbf1_{\{x=y\}}\sum_p\mu(x,p)\sigma_p(u,v)ΩXQ​((x,u),(y,v))=1{x=y}​∑p​μ(x,p)σp​(u,v) and ΩQ=∑x,pμ(x,p)σp\Omega_Q=\sum_{x,p}\mu(x,p)\sigma_pΩQ​=∑x,p​μ(x,p)σp​. There exist a side code with positive message count MMM, encoder EEE, and decoder POVMs DmD_mDm​ indexed by classical words and failure ⊥\bot⊥, whose effects have zero entries between quantum basis words differing in a block label at any position, and a set CCC of covered length-nnn classical words, satisfying

log⁡2Mn≤H(ΩXQ)−H(ΩQ)+3δ,\frac{\log_2M}{n}\le H(\Omega_{XQ})-H(\Omega_Q)+3\delta,nlog2​M​≤H(ΩXQ​)−H(ΩQ​)+3δ, 1−∑w=(xt,pt)t<n(∏t<nμ(xt,pt))Re⁡tr⁡ ⁣[(⨂t<nσpt)DE(x)(x)]≤λ,∑x∉C∏t<nm(xt)≤λ,1-\sum_{w=(x_t,p_t)_{t<n}} \left(\prod_{t<n}\mu(x_t,p_t)\right) \operatorname{Re}\operatorname{tr} \!\left[\left(\bigotimes_{t<n}\sigma_{p_t}\right)D_{E(x)}(x)\right]\le\lambda, \qquad \sum_{x\notin C}\prod_{t<n}m(x_t)\le\lambda,1−w=(xt​,pt​)t<n​∑​(t<n∏​μ(xt​,pt​))Retr[(t<n⨂​σpt​​)DE(x)​(x)]≤λ,x∈/C∑​t<n∏​m(xt​)≤λ, ∀x∈C,1−Re⁡tr⁡ ⁣[(⨂t<nρxt)DE(x)(x)]≤λ,∀x∉C,DE(x)(⊥)=I.\forall x\in C,\quad 1-\operatorname{Re}\operatorname{tr} \!\left[\left(\bigotimes_{t<n}\rho_{x_t}\right)D_{E(x)}(x)\right]\le\lambda, \qquad \forall x\notin C,\quad D_{E(x)}(\bot)=I.∀x∈C,1−Retr[(t<n⨂​ρxt​​)DE(x)​(x)]≤λ,∀x∈/C,DE(x)​(⊥)=I.

Here tensor products have entries equal to the products of the corresponding single-position entries, and H(Z)=−Re⁡tr⁡[Zlog⁡2Z]H(Z)=-\operatorname{Re}\operatorname{tr}[Z\log_2Z]H(Z)=−Retr[Zlog2​Z] is defined by matrix functional calculus. The conditions on covered and uncovered words include zero-probability words; the uncovered-word condition is equality of the failure effect with the identity matrix.

Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me