Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sequential decoder effects and independently sampled finite codebooks

Definition
GaoQuantumUnion_Decoding

by Mrnaiq · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

gao-2015quantum-informationquantum-union-boundsequential-measurementstrace-distance

The rejection prefix at position mmm is (I−Qm−1)⋯(I−Q0)(I-Q_{m-1})\cdots(I-Q_0)(I−Qm−1​)⋯(I−Q0​), with empty prefix III. The accepting Kraus operator is Qm(I−Qm−1)⋯(I−Q0)PQ_m(I-Q_{m-1})\cdots(I-Q_0)PQm​(I−Qm−1​)⋯(I−Q0​)P, and its effect is Km†KmK_m^\dagger K_mKm†​Km​. A codebook is a function C:Fin(M)→JC:\mathrm{Fin}(M)\to JC:Fin(M)→J, including repeated codewords; its independent sampling weight is ∏mp(Cm)\prod_m p(C_m)∏m​p(Cm​). Its average decoding error uses the uniform average over the MMM message positions and the trace of each accepting branch. The coding theorem explicitly requires M>0M>0M>0, avoiding the total-definition value at zero.

Definition code
import Definitions.Def_GaoQuantumUnion_Model
import Definitions.Def_WildeQIT_Gentle_averageState
noncomputable section
open Matrix WildeQIT
open scoped MatrixOrder ComplexOrder ComplexConjugate
set_option autoImplicit false
namespace GaoQuantumUnion
variable {ι J : Type} [Fintype ι] [DecidableEq ι]
def rejectPrefix {M : ℕ} (Q : Fin M → Matrix ι ι ℂ) (m : Fin M) : Matrix ι ι ℂ :=
  ((List.ofFn (fun i => 1-Q i)).take m.val).foldl (fun K P => P*K) 1
def decoderK {M : ℕ} (P : Matrix ι ι ℂ) (Q : Fin M → Matrix ι ι ℂ) (m : Fin M) : Matrix ι ι ℂ :=
  Q m*rejectPrefix Q m*P
def decoderEffect {M : ℕ} (P : Matrix ι ι ℂ) (Q : Fin M → Matrix ι ι ℂ) (m : Fin M) : Matrix ι ι ℂ :=
  (decoderK P Q m)ᴴ*decoderK P Q m
def codeWeight [Fintype J] {M : ℕ} (p : FinDist J) (C : Fin M → J) : ℝ :=
  ∏ m, p.prob (C m)
def codeError {M : ℕ} (ρ : J → Matrix ι ι ℂ) (P : Matrix ι ι ℂ)
    (Q : J → Matrix ι ι ℂ) (C : Fin M → J) : ℝ :=
  1-(1/(M : ℝ))*∑ m, ((decoderK P (Q ∘ C) m)*ρ (C m)*(decoderK P (Q ∘ C) m)ᴴ).trace.re
end GaoQuantumUnion
Source
Jingliang Gao, Quantum union bounds for sequential projective measurements, arXiv:1410.5688v2, Physical Review A 92, 052331 (2015), https://doi.org/10.1103/PhysRevA.92.052331; PDF pp. 10–13: random codebook, sequential decoder, equations (25)–(26)
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (independent blind read-back agent)

GaoQuantumUnion.rejectPrefix: For every finite type ι\iotaι equipped with decidable equality, every natural number MMM, every family Q:{0,…,M−1}→Cι×ιQ:\{0,\ldots,M-1\}\to\mathbb C^{\iota\times\iota}Q:{0,…,M−1}→Cι×ι, and every index m∈{0,…,M−1}m\in\{0,\ldots,M-1\}m∈{0,…,M−1}, this defines a matrix RmR_mRm​ by starting with the identity matrix III and, for i=0,1,…,m−1i=0,1,\ldots,m-1i=0,1,…,m−1 in increasing order, replacing the current matrix KKK by (I−Qi)K(I-Q_i)K(I−Qi​)K. Thus R0=IR_0=IR0​=I and, for m>0m>0m>0, Rm=(I−Qm−1)(I−Qm−2)⋯(I−Q0)R_m=(I-Q_{m-1})(I-Q_{m-2})\cdots(I-Q_0)Rm​=(I−Qm−1​)(I−Qm−2​)⋯(I−Q0​), with the factor having the largest index on the left; QmQ_mQm​ is excluded. The entries of the matrices QiQ_iQi​ are unrestricted. The case M=0M=0M=0 has no permitted index mmm and hence no value at an index. The finite type ι\iotaι may be empty, in which case the identity and every matrix here are the unique empty matrix.

GaoQuantumUnion.decoderK: For every finite type ι\iotaι equipped with decidable equality, every natural number MMM, every matrix P∈Cι×ιP\in\mathbb C^{\iota\times\iota}P∈Cι×ι, every family Q:{0,…,M−1}→Cι×ιQ:\{0,\ldots,M-1\}\to\mathbb C^{\iota\times\iota}Q:{0,…,M−1}→Cι×ι, and every index m∈{0,…,M−1}m\in\{0,\ldots,M-1\}m∈{0,…,M−1}, this defines Km=(QmRm)PK_m=(Q_mR_m)PKm​=(Qm​Rm​)P, where R0=IR_0=IR0​=I and Rm=(I−Qm−1)⋯(I−Q0)R_m=(I-Q_{m-1})\cdots(I-Q_0)Rm​=(I−Qm−1​)⋯(I−Q0​) for m>0m>0m>0. In particular K0=Q0PK_0=Q_0PK0​=Q0​P, and the ordered product for m>0m>0m>0 is Qm(I−Qm−1)⋯(I−Q0)PQ_m(I-Q_{m-1})\cdots(I-Q_0)PQm​(I−Qm−1​)⋯(I−Q0​)P. Neither PPP nor any QiQ_iQi​ is subject to a Hermitian, projector, or positivity hypothesis. If M=0M=0M=0, there is no index mmm; if ι\iotaι is empty, the output is the unique empty matrix.

GaoQuantumUnion.decoderEffect: For every finite type ι\iotaι equipped with decidable equality, every natural number MMM, every matrix P∈Cι×ιP\in\mathbb C^{\iota\times\iota}P∈Cι×ι, every family Q:{0,…,M−1}→Cι×ιQ:\{0,\ldots,M-1\}\to\mathbb C^{\iota\times\iota}Q:{0,…,M−1}→Cι×ι, and every index m∈{0,…,M−1}m\in\{0,\ldots,M-1\}m∈{0,…,M−1}, this defines Em=Km†KmE_m=K_m^\dagger K_mEm​=Km†​Km​, where †\dagger† denotes conjugate transpose, Km=(QmRm)PK_m=(Q_mR_m)PKm​=(Qm​Rm​)P, R0=IR_0=IR0​=I, and Rm=(I−Qm−1)⋯(I−Q0)R_m=(I-Q_{m-1})\cdots(I-Q_0)Rm​=(I−Qm−1​)⋯(I−Q0​) for m>0m>0m>0. Consequently the complete factor order is P†(I−Q0)†⋯(I−Qm−1)†Qm†Qm(I−Qm−1)⋯(I−Q0)PP^\dagger(I-Q_0)^\dagger\cdots(I-Q_{m-1})^\dagger Q_m^\dagger Q_m(I-Q_{m-1})\cdots(I-Q_0)PP†(I−Q0​)†⋯(I−Qm−1​)†Qm†​Qm​(I−Qm−1​)⋯(I−Q0​)P, with both strings of rejection factors absent when m=0m=0m=0, giving E0=P†Q0†Q0PE_0=P^\dagger Q_0^\dagger Q_0PE0​=P†Q0†​Q0​P. The inputs PPP and QiQ_iQi​ are unrestricted complex matrices. For M=0M=0M=0 there is no permitted mmm; for empty ι\iotaι the output is the unique empty matrix.

GaoQuantumUnion.codeWeight: For every finite type JJJ, every natural number MMM, every distribution ppp consisting of a real-valued function j↦pjj\mapsto p_jj↦pj​ on JJJ with pj≥0p_j\geq0pj​≥0 for every j∈Jj\in Jj∈J and ∑j∈Jpj=1\sum_{j\in J}p_j=1∑j∈J​pj​=1, and every function C:{0,…,M−1}→JC:\{0,\ldots,M-1\}\to JC:{0,…,M−1}→J, this defines the real number ∏m=0M−1pC(m)\prod_{m=0}^{M-1}p_{C(m)}∏m=0M−1​pC(m)​. The product includes one factor for every index, including repeated factors if CCC takes the same value more than once; no injectivity condition is imposed on CCC. When M=0M=0M=0, the product is empty and equals 111. If any factor is zero for M>0M>0M>0, the product equals zero. If JJJ is empty, no distribution ppp satisfies the required normalization, even when M=0M=0M=0. No matrix index type or decidable-equality assumption on JJJ is an argument of this definition.

GaoQuantumUnion.codeError: For every finite type ι\iotaι equipped with decidable equality, every type JJJ (with no finiteness or decidable-equality assumption), every natural number MMM, every family ρ:J→Cι×ι\rho:J\to\mathbb C^{\iota\times\iota}ρ:J→Cι×ι, every matrix P∈Cι×ιP\in\mathbb C^{\iota\times\iota}P∈Cι×ι, every family Q:J→Cι×ιQ:J\to\mathbb C^{\iota\times\iota}Q:J→Cι×ι, and every function C:{0,…,M−1}→JC:\{0,\ldots,M-1\}\to JC:{0,…,M−1}→J, this defines the real number 1−1M∑m=0M−1Re⁡tr⁡((KmρC(m))Km†)1-\frac{1}{M}\sum_{m=0}^{M-1}\operatorname{Re}\operatorname{tr}((K_m\rho_{C(m)})K_m^\dagger)1−M1​∑m=0M−1​Retr((Km​ρC(m)​)Km†​), where MMM is cast to a real number, Km=(QC(m)Rm)PK_m=(Q_{C(m)}R_m)PKm​=(QC(m)​Rm​)P, R0=IR_0=IR0​=I, and Rm=(I−QC(m−1))⋯(I−QC(0))R_m=(I-Q_{C(m-1)})\cdots(I-Q_{C(0)})Rm​=(I−QC(m−1)​)⋯(I−QC(0)​) for m>0m>0m>0. Thus each summand has matrix factors in the order QC(m)RmPρC(m)P†Rm†QC(m)†Q_{C(m)}R_mP\rho_{C(m)}P^\dagger R_m^\dagger Q_{C(m)}^\daggerQC(m)​Rm​PρC(m)​P†Rm†​QC(m)†​, where Rm†=(I−QC(0))†⋯(I−QC(m−1))†R_m^\dagger=(I-Q_{C(0)})^\dagger\cdots(I-Q_{C(m-1)})^\daggerRm†​=(I−QC(0)​)†⋯(I−QC(m−1)​)† and both rejection strings are empty for m=0m=0m=0. The trace is the sum of the diagonal entries indexed by ι\iotaι, and its real part is taken after the matrix multiplication and trace. All matrices are unrestricted; no density-operator, normalization, Hermitian, projector, or positivity hypothesis is imposed, and CCC may repeat values. Real division is total, with 1/0=01/0=01/0=0: when M=0M=0M=0, the sum is empty, equals zero, and this definition gives 111. If ι\iotaι is empty, all traces vanish and the result is 111 for every permitted input. If JJJ is empty and M>0M>0M>0, no function CCC exists; if JJJ is empty and M=0M=0M=0, its empty function exists and the result is 111.

Human review
  • Endorsed by Shuze Chen · Nov 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Mrnaiq · Nov 20, 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