Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Concatenated Repetition Codes: strict threshold advantage over every single cat

Open
QAlgorithms.Papers.Independent.Intakenext100.P93.concatenation_improves_single_cat

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Consider independent depolarizing noise with total nonidentity probability ppp and px=py=pz=p/3p_x=p_y=p_z=p/3px​=py​=pz​=p/3. For an inner length A∈{3,5}A\in\{3,5\}A∈{3,5} and a positive outer length BBB, construct the encoder

VA,B=VZ,A⊗BVX,B,VX,B=H⊗BVZ,BH,V_{A,B}=V_{Z,A}^{\otimes B}V_{X,B},\qquad V_{X,B}=H^{\otimes B}V_{Z,B}H,VA,B​=VZ,A⊗B​VX,B​,VX,B​=H⊗BVZ,B​H,

where VZ,j∣c⟩=∣c⟩⊗jV_{Z,j}|c\rangle=|c\rangle^{\otimes j}VZ,j​∣c⟩=∣c⟩⊗j. Apply the physical channel and the inverse two-level decoder, measuring and retaining every inner Z syndrome and the outer X syndrome. Let RA,B(p)R_{A,B}(p)RA,B​(p) be the coherent information of this actual flagged Bell output divided by ABABAB, and let Rm(p)R_m(p)Rm​(p) be the corresponding single-cat rate. For any such rate function define its low-noise positivity threshold by t(R)=sup⁡({0}∪{p∈[0,3/4]:R(p)>0})t(R)=\sup(\{0\}\cup\{p\in[0,3/4]:R(p)>0\})t(R)=sup({0}∪{p∈[0,3/4]:R(p)>0}). Then

∃A∈{3,5}, B≥1∀m≥1:t(Rm)<t(RA,B).\exists A\in\{3,5\},\ B\ge1\quad\forall m\ge1:\qquad t(R_m)<t(R_{A,B}).∃A∈{3,5}, B≥1∀m≥1:t(Rm​)<t(RA,B​).

This is a strict zero-rate threshold advantage of some fixed concatenation over every single cat. It asserts neither pointwise superiority at every noise value nor optimality among arbitrary quantum codes; no rounded numerical optimizer is used. For these same fixed lengths and every p∈[0,3/4]p\in[0,3/4]p∈[0,3/4] with RA,B(p)≥0R_{A,B}(p)\ge0RA,B​(p)≥0, that rate is achievable by tensor copies of the constructed two-level inner encoder followed by an additive outer stabilizer encoder and a CPTP decoder. For every error ϵ>0\epsilon>0ϵ>0 and rate slack δ>0\delta>0δ>0, all sufficiently large positive outer blocklengths nnn admit a code with l≥(RA,B(p)−δ)ABnl\ge(R_{A,B}(p)-\delta)ABnl≥(RA,B​(p)−δ)ABn logical qubits and both entanglement fidelity and every normalized pure-input transmission fidelity at least 1−ϵ1-\epsilon1−ϵ. The encoder and decoder are chosen before the unknown input.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P93
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P93

open QAlgorithms

open scoped BigOperators ComplexConjugate Matrix

attribute [local instance] Classical.propDecidable Classical.decEq

/-- Smith--Smolin, PDF p.3, Concatenated Repetition Codes / Fig.2:
a fixed 3- or 5-qubit Z-inner/X-outer concatenation has a strictly larger
zero-rate noise threshold than every single cat. Its nonnegative yield is
operationally achievable by the Eq.(5) outer-stabilizer construction.
Here a+1 is the inner length; no rounded optimum is asserted. -/
theorem concatenation_improves_single_cat :
    ∃ a b : ℕ, (a = 2 ∨ a = 4) ∧
      (∀ p : ℝ, 0 ≤ p → p ≤ 3 / 4 → 0 ≤ concatenatedRate a b p →
        ConcatenatedAchievable a b p (concatenatedRate a b p)) ∧
      ∀ k : ℕ,
        noiseThreshold (fun p => catRate k (p / 3) (p / 3) (p / 3)) <
          noiseThreshold (concatenatedRate a b) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P93

end
Source
Degenerate Quantum Codes for Pauli Channels, arXiv:quant-ph/0604107v2, PDF p. 3, Concatenated Repetition Codes: strict threshold advantage over every single cat
Read-back

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

There exist natural numbers a,ba,ba,b, with a=2a=2a=2 or a=4a=4a=4, satisfying the following assertions, with the same a,ba,ba,b throughout. To specify the quantities, write Bj={0,1}j\mathcal B_j=\{0,1\}^jBj​={0,1}j, identify bits with 0,10,10,1, let Hr,s=(−1)rs/2H_{r,s}=(-1)^{rs}/\sqrt2Hr,s​=(−1)rs/2​, and define

Cj(z,c)=1{every bit of z=c},Ka,b(z,c)=∑v∈Bb+1∑d∈{0,1}Hd,c∏j=0bHvj,dCa(zj,vj).C_j(z,c)=\mathbf1_{\{\text{every bit of }z=c\}}, \qquad K_{a,b}(z,c)= \sum_{v\in\mathcal B_{b+1}}\sum_{d\in\{0,1\}} H_{d,c}\prod_{j=0}^{b}H_{v_j,d}C_a(z_j,v_j).Cj​(z,c)=1{every bit of z=c}​,Ka,b​(z,c)=v∈Bb+1​∑​d∈{0,1}∑​Hd,c​j=0∏b​Hvj​,d​Ca​(zj​,vj​).

Thus CjC_jCj​ maps a bit to a constant string of length j+1j+1j+1, while Ka,bK_{a,b}Ka,b​ has rows indexed by b+1b+1b+1 strings of length a+1a+1a+1. For u,v∈Bju,v\in\mathcal B_ju,v∈Bj​, let

Pu,v(z,x)=1{x=z⊕u}(−1)∑q=0j−1vq(zq⊕uq),Nj,p(X)=∑u,v∈Bj(∏q=0j−1wp(uq,vq))Pu,vXPu,v†,wp(r,s)={1−p,(r,s)=(0,0),p/3,otherwise.P_{u,v}(z,x)= \mathbf1_{\{x=z\oplus u\}} (-1)^{\sum_{q=0}^{j-1}v_q(z_q\oplus u_q)},\qquad \mathcal N_{j,p}(X)= \sum_{u,v\in\mathcal B_j} \left(\prod_{q=0}^{j-1}w_p(u_q,v_q)\right)P_{u,v}XP_{u,v}^{\dagger}, \quad w_p(r,s)= \begin{cases}1-p,&(r,s)=(0,0),\\p/3,&\text{otherwise}.\end{cases}Pu,v​(z,x)=1{x=z⊕u}​(−1)∑q=0j−1​vq​(zq​⊕uq​),Nj,p​(X)=u,v∈Bj​∑​(q=0∏j−1​wp​(uq​,vq​))Pu,v​XPu,v†​,wp​(r,s)={1−p,p/3,​(r,s)=(0,0),otherwise.​

Tensor extensions of matrix maps are defined entrywise by

[Φ⊗r(X)]y,y′=∑x,x′Xx,x′∏i=0r−1[Φ(∣xi⟩⟨xi′∣)]yi,yi′.[\Phi^{\otimes r}(X)]_{y,y'} =\sum_{x,x'}X_{x,x'}\prod_{i=0}^{r-1} [\Phi(|x_i\rangle\langle x'_i|)]_{y_i,y'_i}.[Φ⊗r(X)]y,y′​=x,x′∑​Xx,x′​i=0∏r−1​[Φ(∣xi​⟩⟨xi′​∣)]yi​,yi′​​.

Put ∣Ω⟩=(∣0,0⟩+∣1,1⟩)/2|\Omega\rangle=(|0,0\rangle+|1,1\rangle)/\sqrt2∣Ω⟩=(∣0,0⟩+∣1,1⟩)/2​, write Ad⁡A(X)=AXA†\operatorname{Ad}_A(X)=AXA^\daggerAdA​(X)=AXA†, and define the decoding matrices

Bj,s(c,x)=1{x0=c,  x0⊕xq+1=sq for every q<j},(Hj)x,y=2−j/2(−1)∑q<jxqyq.B_{j,s}(c,x)= \mathbf1_{\{x_0=c,\;x_0\oplus x_{q+1}=s_q\text{ for every }q<j\}}, \qquad (\mathcal H_j)_{x,y}=2^{-j/2}(-1)^{\sum_{q<j}x_qy_q}.Bj,s​(c,x)=1{x0​=c,x0​⊕xq+1​=sq​ for every q<j}​,(Hj​)x,y​=2−j/2(−1)∑q<j​xq​yq​.

For t∈Bbt\in\mathcal B_bt∈Bb​ and s=(s0,…,sb)∈Ba b+1s=(s_0,\ldots,s_b)\in\mathcal B_a^{\,b+1}s=(s0​,…,sb​)∈Bab+1​, define

Ms(v,z)=∏j=0bBa,sj(vj,zj),Lt,s=HBb,tHb+1Ms.M_s(v,z)=\prod_{j=0}^{b}B_{a,s_j}(v_j,z_j), \qquad L_{t,s}=H B_{b,t}\mathcal H_{b+1}M_s.Ms​(v,z)=j=0∏b​Ba,sj​​(vj​,zj​),Lt,s​=HBb,t​Hb+1​Ms​.

Define raw output matrices and matrices with additional classical labels by

ρj,p=(id⁡⊗(Nj+1,p∘Ad⁡Cj))(∣Ω⟩⟨Ω∣),τj,p[(r,c,s),(r′,c′,s′)]=1{s=s′}[(id⁡⊗Ad⁡Bj,s)(ρj,p)](r,c),(r′,c′),\rho_{j,p}= (\operatorname{id}\otimes(\mathcal N_{j+1,p}\circ\operatorname{Ad}_{C_j})) (|\Omega\rangle\langle\Omega|), \qquad \tau_{j,p}[(r,c,s),(r',c',s')] = \mathbf1_{\{s=s'\}} [(\operatorname{id}\otimes\operatorname{Ad}_{B_{j,s}})(\rho_{j,p})]_{(r,c),(r',c')},ρj,p​=(id⊗(Nj+1,p​∘AdCj​​))(∣Ω⟩⟨Ω∣),τj,p​[(r,c,s),(r′,c′,s′)]=1{s=s′}​[(id⊗AdBj,s​​)(ρj,p​)](r,c),(r′,c′)​, ρa,b,p=(id⁡⊗(Na+1,p⊗(b+1)∘Ad⁡Ka,b))(∣Ω⟩⟨Ω∣),τa,b,p[(r,c,t,s),(r′,c′,t′,s′)]=1{(t,s)=(t′,s′)}[(id⁡⊗Ad⁡Lt,s)(ρa,b,p)](r,c),(r′,c′).\rho_{a,b,p}= (\operatorname{id}\otimes (\mathcal N_{a+1,p}^{\otimes(b+1)}\circ\operatorname{Ad}_{K_{a,b}})) (|\Omega\rangle\langle\Omega|), \qquad \tau_{a,b,p}[(r,c,t,s),(r',c',t',s')] = \mathbf1_{\{(t,s)=(t',s')\}} [(\operatorname{id}\otimes\operatorname{Ad}_{L_{t,s}})(\rho_{a,b,p})]_{(r,c),(r',c')}.ρa,b,p​=(id⊗(Na+1,p⊗(b+1)​∘AdKa,b​​))(∣Ω⟩⟨Ω∣),τa,b,p​[(r,c,t,s),(r′,c′,t′,s′)]=1{(t,s)=(t′,s′)}​[(id⊗AdLt,s​​)(ρa,b,p​)](r,c),(r′,c′)​.

Here an identity extension applies the indicated map to each block indexed by the reference bits r,r′r,r'r,r′. For a matrix XXX, let S(X)=−Re⁡Tr⁡f(X)S(X)=-\operatorname{Re}\operatorname{Tr}f(X)S(X)=−ReTrf(X), using continuous functional calculus with f(x)=xlog⁡2xf(x)=x\log_2xf(x)=xlog2​x and its totalized value f(0)=0f(0)=0f(0)=0; let Tr⁡ref\operatorname{Tr}_{\mathrm{ref}}Trref​ mean summing over equal row and column indices of the reference-bit register. The two rate functions occurring in the assertion are

rj(p)=S(Tr⁡refτj,p)−S(τj,p)j+1,ra,b(p)=S(Tr⁡refτa,b,p)−S(τa,b,p)(a+1)(b+1).r_j(p)=\frac{S(\operatorname{Tr}_{\mathrm{ref}}\tau_{j,p})-S(\tau_{j,p})}{j+1}, \qquad r_{a,b}(p)= \frac{S(\operatorname{Tr}_{\mathrm{ref}}\tau_{a,b,p})-S(\tau_{a,b,p})}{(a+1)(b+1)}.rj​(p)=j+1S(Trref​τj,p​)−S(τj,p​)​,ra,b​(p)=(a+1)(b+1)S(Trref​τa,b,p​)−S(τa,b,p​)​.

First, for every real ppp with 0≤p≤3/40\le p\le3/40≤p≤3/4 and ra,b(p)≥0r_{a,b}(p)\ge0ra,b​(p)≥0, the following property holds: for every ϵ,δ>0\epsilon,\delta>0ϵ,δ>0, there exists n0≥1n_0\ge1n0​≥1 such that every natural number n≥n0n\ge n_0n≥n0​ admits a natural number lll, a matrix E:CBl→CBnE:\mathbb C^{\mathcal B_l}\to\mathbb C^{\mathcal B_n}E:CBl​→CBn​, and a map DDD from matrices indexed by (Ba+1 b+1)n(\mathcal B_{a+1}^{\,b+1})^n(Ba+1b+1​)n to matrices indexed by Bl\mathcal B_lBl​, with

(ra,b(p)−δ)(a+1)(b+1)n≤l,l≤n,E†E=I.(r_{a,b}(p)-\delta)(a+1)(b+1)n\le l,\qquad l\le n,\qquad E^\dagger E=I.(ra,b​(p)−δ)(a+1)(b+1)n≤l,l≤n,E†E=I.

There must be a commuting subgroup S0S_0S0​ of the unitaries on CBn\mathbb C^{\mathcal B_n}CBn​, contained in the subgroup generated by all phase multiples ic⨂qQqi^c\bigotimes_qQ_qic⨂q​Qq​, where c∈{0,1,2,3}c\in\{0,1,2,3\}c∈{0,1,2,3} and Qq∈{I,X,Y,Z}Q_q\in\{I,X,Y,Z\}Qq​∈{I,X,Y,Z}, such that −I∉S0-I\notin S_0−I∈/S0​ and range⁡E={ξ:Uξ=ξ for every U∈S0}\operatorname{range}E=\{\xi:U\xi=\xi\text{ for every }U\in S_0\}rangeE={ξ:Uξ=ξ for every U∈S0​}. The map DDD must be expressible as D(X)=∑hAhXAh†D(X)=\sum_hA_hXA_h^\daggerD(X)=∑h​Ah​XAh†​ for finitely many matrices AhA_hAh​ satisfying ∑hAh†Ah=I\sum_hA_h^\dagger A_h=I∑h​Ah†​Ah​=I. Writing

Bn(y,x)=∏i=0n−1Ka,b(yi,xi),T=D∘(Na+1,p⊗(b+1))⊗n∘Ad⁡Bn∘Ad⁡E,∣Φl⟩=2−l/2∑x∈Bl∣x,x⟩,B_n(y,x)=\prod_{i=0}^{n-1}K_{a,b}(y_i,x_i),\qquad \mathcal T=D\circ(\mathcal N_{a+1,p}^{\otimes(b+1)})^{\otimes n} \circ\operatorname{Ad}_{B_n}\circ\operatorname{Ad}_E, \qquad |\Phi_l\rangle=2^{-l/2}\sum_{x\in\mathcal B_l}|x,x\rangle,Bn​(y,x)=i=0∏n−1​Ka,b​(yi​,xi​),T=D∘(Na+1,p⊗(b+1)​)⊗n∘AdBn​​∘AdE​,∣Φl​⟩=2−l/2x∈Bl​∑​∣x,x⟩,

one must have

Re⁡⟨Φl∣(id⁡⊗T)(∣Φl⟩⟨Φl∣)∣Φl⟩≥1−ϵ,Re⁡Tr⁡(∣ψ⟩⟨ψ∣ T(∣ψ⟩⟨ψ∣))≥1−ϵfor every ∥ψ∥=1.\operatorname{Re}\langle\Phi_l| (\operatorname{id}\otimes\mathcal T)(|\Phi_l\rangle\langle\Phi_l|) |\Phi_l\rangle\ge1-\epsilon, \qquad \operatorname{Re}\operatorname{Tr} \bigl(|\psi\rangle\langle\psi|\,\mathcal T(|\psi\rangle\langle\psi|)\bigr) \ge1-\epsilon \quad\text{for every }\|\psi\|=1.Re⟨Φl​∣(id⊗T)(∣Φl​⟩⟨Φl​∣)∣Φl​⟩≥1−ϵ,ReTr(∣ψ⟩⟨ψ∣T(∣ψ⟩⟨ψ∣))≥1−ϵfor every ∥ψ∥=1.

Second, define for any real-valued function rrr

Θ(r)=sup⁡({0}∪{p∈R:0≤p≤3/4, r(p)>0}).\Theta(r)=\sup\bigl(\{0\}\cup \{p\in\mathbb R:0\le p\le3/4,\ r(p)>0\}\bigr).Θ(r)=sup({0}∪{p∈R:0≤p≤3/4, r(p)>0}).

For every natural number kkk, including k=0k=0k=0, the strict inequality Θ(rk)<Θ(ra,b)\Theta(r_k)<\Theta(r_{a,b})Θ(rk​)<Θ(ra,b​) holds. The supremum includes 000 even when there are no parameters with positive rate. No positivity assumption is imposed on bbb, so b=0b=0b=0 is included among the possible witnesses; likewise l=0l=0l=0 is allowed in the quantified coding property, and the achievability assertion includes parameters where ra,b(p)=0r_{a,b}(p)=0ra,b​(p)=0.

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

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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