Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Explicit linear-BSC-to-CSS code conversion

Proved
QAlgorithms.Papers.Independent.Support50.P04.linear_bsc_css_conversion

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

prove2quantum

Let n≥1n\ge1n≥1, 0≤k≤n0\le k\le n0≤k≤n, and let H:F2n→F2n−kH:\mathbb F_2^n\to\mathbb F_2^{n-k}H:F2n​→F2n−k​ be surjective. Let the injective linear encoder c:F2k→F2nc:\mathbb F_2^k\to\mathbb F_2^nc:F2k​→F2n​ have image ker⁡H\ker HkerH, and let the classical syndrome decoder choose u0(s)u_0(s)u0​(s) with Hu0(s)=sHu_0(s)=sHu0​(s)=s for every syndrome. For 0≤γ≤10\le\gamma\le10≤γ≤1, give errors uuu probability pγ(u)=∏i[(1−γ)1ui=0+γ1ui=1]p_\gamma(u)=\prod_i[(1-\gamma)\mathbf1_{u_i=0}+\gamma\mathbf1_{u_i=1}]pγ​(u)=∏i​[(1−γ)1ui​=0​+γ1ui​=1​]. The CSS isometry is V∣m⟩=∣cm⟩XV|m\rangle=|c_m\rangle_XV∣m⟩=∣cm​⟩X​; its decoder measures the syndrome projector Ps=∑Hx=s∣x⟩X⟨x∣P_s=\sum_{Hx=s}|x\rangle_X\langle x|Ps​=∑Hx=s​∣x⟩X​⟨x∣ and uses Kraus operators V†Zu0(s)PsV^\dagger Z^{u_0(s)}P_sV†Zu0​(s)Ps​. There is an actual CPTP entanglement-transmission code with exactly these maps, M=2kM=2^kM=2k, and

F=2−k∑m∈F2k∑u∈F2npγ(u) 1{cm+u−u0(H(cm+u))=cm}.F=2^{-k}\sum_{m\in\mathbb F_2^k}\sum_{u\in\mathbb F_2^n}p_\gamma(u)\,\mathbf1\{c_m+u-u_0(H(c_m+u))=c_m\}.F=2−km∈F2k​∑​u∈F2n​∑​pγ​(u)1{cm​+u−u0​(H(cm​+u))=cm​}.

Thus the quantum squared entanglement fidelity equals the classical uniform-message average decoding success at the same block length and dimension.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P04
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder

open QAlgorithms

namespace QAlgorithms.Papers.Independent.Support50.P04

variable {A B E : Type} [Fintype A] [DecidableEq A]

variable [Fintype B] [DecidableEq B] [Fintype E] [DecidableEq E]

/-- arXiv:1504.04617v2, PDF pp.16–17: explicit linear-BSC-to-CSS conversion.
Printed parity-check row count log n-log M; changed to n-k for binary [n,k] codes.
The syndrome-consistent decoder and all syndrome outcomes are retained. Its actual
entanglement fidelity equals the classical UNIFORM-message average success. -/
theorem linear_bsc_css_conversion {n k : ℕ} (hn : 0 < n) (hk : k ≤ n)
    (H : BinaryWord n →ₗ[ZMod 2] BinaryWord (n-k)) (hH : Function.Surjective H)
    (word : BinaryWord k →ₗ[ZMod 2] BinaryWord n) (hword : Function.Injective word)
    (hker : LinearMap.range word = LinearMap.ker H)
    (estimate : BinaryWord (n-k) → BinaryWord n) (hestimate : ∀ s, H (estimate s) = s)
    (gamma : ℝ) (hg0 : 0 ≤ gamma) (hg1 : gamma ≤ 1) :
    ∃ C : QAlgorithms.Papers.Independent.Information100.P80.TransmissionCode (Fin n → Fin 2) (Fin n → Fin 2),
      C.M = 2^k ∧
      HEq C.encoder (conjSuperop (cssIsometry word)) ∧
      HEq C.decoder (cssDecoder H word estimate) ∧
      QAlgorithms.Papers.Independent.Information100.P80.transmissionFidelity (piSuperop (fun _ : Fin n => (QAlgorithms.Papers.Independent.Information100.P27.qubitDephasing (1-2*gamma)))) C = classicalLinearSuccess gamma H word estimate := by sorry

end QAlgorithms.Papers.Independent.Support50.P04

end
Source
Quantum Coding with Finite Resources, arXiv:1504.04617v2, PDF p. 16, §V.B, pp.16–17
Read-back

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

Let n,kn,kn,k be natural numbers with n>0n>0n>0 and k≤nk\le nk≤n, let H:F2n→F2 n−kH:\mathbb F_2^n\to\mathbb F_2^{\,n-k}H:F2n​→F2n−k​ be a surjective linear map, and let W:F2k→F2nW:\mathbb F_2^k\to\mathbb F_2^nW:F2k​→F2n​ be an injective linear map with im⁡W=ker⁡H\operatorname{im}W=\ker HimW=kerH. Let e:F2 n−k→F2ne:\mathbb F_2^{\,n-k}\to\mathbb F_2^ne:F2n−k​→F2n​ be any function satisfying H(e(s))=sH(e(s))=sH(e(s))=s for every syndrome sss, and let 0≤γ≤10\le\gamma\le10≤γ≤1. For c∈F2nc\in\mathbb F_2^nc∈F2n​, define

∣xc⟩z=2−n/2(−1)∑icivalzival,z∈{0,1}n,|x_c\rangle_z= 2^{-n/2}(-1)^{\sum_i c_i^{\mathrm{val}}z_i^{\mathrm{val}}}, \qquad z\in\{0,1\}^n,∣xc​⟩z​=2−n/2(−1)∑i​cival​zival​,z∈{0,1}n,

where values of F2\mathbb F_2F2​ are represented by 0,10,10,1. Using the fixed finite-set enumeration m↦m~m\mapsto\widetilde mm↦m of F2k\mathbb F_2^kF2k​, define the matrix VVV from 2k2^k2k dimensions into nnn qubits by Vz,m=∣xWm~⟩zV_{z,m}=|x_{W\widetilde m}\rangle_zVz,m​=∣xWm​⟩z​, define Πs=∑c:Hc=s∣xc⟩⟨xc∣\Pi_s=\sum_{c:Hc=s}|x_c\rangle\langle x_c|Πs​=∑c:Hc=s​∣xc​⟩⟨xc​∣, and define the diagonal matrix ZuZ_uZu​ by (Zu)zz=(−1)∑iuivalzival(Z_u)_{zz}=(-1)^{\sum_i u_i^{\mathrm{val}}z_i^{\mathrm{val}}}(Zu​)zz​=(−1)∑i​uival​zival​. The assertion is that there exists a transmission code with message dimension exactly M=2k>0M=2^k>0M=2k>0, whose encoder, after identifying its message space with dimension 2k2^k2k, is exactly X↦VXV†X\mapsto VXV^\daggerX↦VXV†, and whose decoder is exactly

X⟼∑s∈F2 n−kV†Ze(s)Πs X Πs†Ze(s)†V.X\longmapsto\sum_{s\in\mathbb F_2^{\,n-k}} V^\dagger Z_{e(s)}\Pi_s\,X\,\Pi_s^\dagger Z_{e(s)}^\dagger V.X⟼s∈F2n−k​∑​V†Ze(s)​Πs​XΠs†​Ze(s)†​V.

Both maps are channels, meaning finite Kraus sums with complete Kraus families, and its entanglement fidelity through nnn independent copies of the map preserving diagonal entries and multiplying off-diagonal entries by 1−2γ1-2\gamma1−2γ is exactly

2−k∑m∈F2k∑u∈F2n1 ⁣[Wm+u−e ⁣(H(Wm+u))=Wm]∏i=1n{1−γ,ui=0,γ,ui≠0.2^{-k}\sum_{m\in\mathbb F_2^k}\sum_{u\in\mathbb F_2^n} \mathbf1\!\left[ Wm+u-e\!\left(H(Wm+u)\right)=Wm \right] \prod_{i=1}^n \begin{cases} 1-\gamma,&u_i=0,\\ \gamma,&u_i\ne0. \end{cases}2−km∈F2k​∑​u∈F2n​∑​1[Wm+u−e(H(Wm+u))=Wm]i=1∏n​{1−γ,γ,​ui​=0,ui​=0.​

Entanglement fidelity is the overlap with the normalized maximally entangled state of dimension MMM after applying the effective encoded, transmitted, and decoded map to its second half. The cases k=0k=0k=0, giving M=1M=1M=1, and k=nk=nk=n, giving a zero-dimensional syndrome vector space, are included; the subtraction n−kn-kn−k is natural-number subtraction.

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

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 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