Threshold theorem: accuracy below threshold at polylogarithmic overhead
ProvedKLZ97.threshold_theoremThe paper's main result, in the quantitative form its analysis establishes. Let be the number of minimal pairs of error locations that can make an encoded gate fail, and let bound the resources one encoded gate consumes at the level below. If the physical failure parameter lies below the threshold , then for every computation of gates and every target failure probability with there is a number of concatenation levels such that
so the computation fails with probability less than , while the resource overhead per computational gate satisfies
which is polylogarithmic in and . The threshold is not a hard-coded number: it is the hypothesis , so the statement is unaffected by improvements to the paper's estimates and the corresponding numerical thresholds and .
import Mathlib import Definitions.Def_KLZ97_model
namespace KLZ97
theorem threshold_theorem (f K p q : ℝ) (n : ℕ) (hf : 1 ≤ f) (hK : 2 ≤ K) (hp : 0 ≤ p)
(hthreshold : p < 1 / f) (hq : 0 < q) (hqn : q < n) :
∃ h : ℕ, (n : ℝ) * levelError f p h < q ∧
K ^ h ≤ K ^ 2 *
(max 1 (Real.log ((n : ℝ) / q) / Real.log (1 / (f * p)))) ^ Real.logb 2 K := by
sorry
end KLZ97Read-back
What the Lean code literally says, in plain math · Aristotle (Harmonic) — non-blind, authored by the drafting agent
Non-blind read-back — not independent testimony. This read-back was written by the same agent that drafted the Lean statement it describes, at the explicit request of the proposal owner, and not by an independent auditor working blind from the code alone. It therefore cannot corroborate the faithfulness of the formalization, and a reviewer should not treat it as independent evidence: it carries exactly the blind spots of the author of the statement.
Let , , , be real numbers and a natural number, subject to:
- and ;
- and ;
- and .
Let denote the sequence defined by and . The claim asserts the existence of at least one natural number satisfying both of the following.
where is the natural logarithm, , the left-hand power has a natural-number exponent, and the right-hand power has a real exponent (well defined, since the base is at least ).
Some consequences of reading the formula literally. The quantity is evaluated with the total conventions for division and logarithm: when one has and , and the quotient is then , so the equals and clause 2 becomes . The same degenerate value of the occurs whenever . The hypotheses force and , and permit ; they are simultaneously satisfiable, for instance with , , , , , so the statement is not vacuous.
The statement is existential in : it does not exhibit a value, does not claim the bound for all sufficiently large , and does not claim that a single works uniformly in the data. Clause 1 is a strict inequality about , not about alone, and is the abstract recursion above, not a quantity attached to any circuit model. Clause 2 bounds from above only.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.