Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Level-kkk concatenated simulation: error (cp)2k/c(cp)^{2^k}/c(cp)2k/c per location, size O(dk)O(d^k)O(dk)

Open
ThresholdTheorem.level_k_concatenated_simulation

by Lucas · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

fault-tolerancequantum-computingquantum-error-correction

Concatenated simulation at every level. There are constants c>0c>0c>0, AAA and d∈Nd\in\mathbb Nd∈N such that for every number of levels kkk there are a block size bbb and a decoder dec:{0,1}b→{0,1}\mathrm{dec}:\{0,1\}^b\to\{0,1\}dec:{0,1}b→{0,1} with the following property: every ideal circuit CCC on nnn qubits has a physical simulation C′C'C′ on nnn blocks of bbb qubits with

∣C′∣  ≤  A dk ∣C∣,|C'|\;\le\;A\,d^{k}\,|C|,∣C′∣≤Adk∣C∣,

and for every 0≤p0\le p0≤p with cp<1cp<1cp<1 and every independent stochastic noise model with fault rate at most ppp,

dTV(dec∗Pnoisy(C′), Pideal(C))  ≤  (c p)2kc ∣C∣.d_{\mathrm{TV}}\big(\mathrm{dec}_*P_{\mathrm{noisy}}(C'),\,P_{\mathrm{ideal}}(C)\big)\;\le\;\frac{(c\,p)^{2^{k}}}{c}\,|C| .dTV​(dec∗​Pnoisy​(C′),Pideal​(C))≤c(cp)2k​∣C∣.

This is the statement that better gates can be used recursively to build even better gates: after kkk levels each location fails with probability at most (cp)2k/c(cp)^{2^k}/c(cp)2k/c, at a cost of a factor dkd^kdk in size. For k=0k=0k=0 it is the unencoded bound, and k=1k=1k=1 is the one-level statement.

Preamble
import Mathlib
import Definitions.Def_threshold_theorem_noise_model

open ThresholdTheorem
Formal statement
namespace ThresholdTheorem
theorem level_k_concatenated_simulation :
    ∃ (c A : ℝ) (d : ℕ), 0 < c ∧ ∀ k : ℕ, ∃ (b : ℕ) (dec : (Fin b → Fin 2) → Fin 2),
      ∀ (n : ℕ) (C : Circuit (Fin n)), ∃ C' : Circuit (Fin n × Fin b),
        (C'.size : ℝ) ≤ A * (d : ℝ) ^ k * C.size ∧
        ∀ (p : ℝ), 0 ≤ p → c * p < 1 → ∀ N : NoiseModel p,
          tvDist (decodeDist dec (outDist (noisyState N C'))) (outDist (idealState C))
            ≤ (c * p) ^ (2 ^ k) / c * C.size := by sorry
end ThresholdTheorem
Source
Wikipedia, "Threshold theorem" (revision oldid=1360742213, https://en.wikipedia.org/w/index.php?title=Threshold_theorem&oldid=1360742213), section "Explanation"; the boxed statement is quoted there from M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press, p. 481.
Human review
  • Endorsed by Shuze Chen · Oct 13, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Lucas · Oct 13, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me