Threshold theorem (probabilistic noise): polylogarithmic recursion depth suffices
ProvedABOThreshold.threshold_recursion_depthThis is the quantitative core of Theorem 10, the threshold theorem for probabilistic noise.
Fix a rectangle size and a tolerance with , and an error rate below the threshold . Then there are constants , depending only on , and , such that for every circuit with locations and every target accuracy there is a number of concatenation levels with
The first inequality is the statement that, after levels of recursive simulation, the probability that any of the rectangles of the computation carries a non-sparse fault path — the event that the proof of Theorem 10 must exclude — is smaller than . The second inequality is the cost: the number of physical locations simulating one original location, , is polylogarithmic in , which is exactly the overhead in space, time and gate count claimed by Theorem 10.
Together they express the content of the theorem at the level of the noise analysis: below a constant threshold, an arbitrarily reliable simulation is bought with polylogarithmic overhead. The circuit-level formulation of Theorem 10 — the existence of a simulating circuit computing a function -close to that of — additionally requires a formal model of quantum circuits with mixed states, fault-tolerant procedures and quantum codes, which is outside the scope of this mission.
import Definitions.Def_ABOThreshold_model
namespace ABOThreshold
theorem threshold_recursion_depth (A k : ℕ) (hk : 1 ≤ k) (hA : k + 1 ≤ A) (η : ℝ) (hη : 0 < η)
(hlt : η < thresholdProb A k) :
∃ C c : ℝ, 0 < C ∧ 0 < c ∧ ∀ (v : ℕ) (ε : ℝ), 1 ≤ v → 0 < ε → ε < 1 →
∃ r : ℕ, (v : ℝ) * badProb A k η r < ε ∧
(A : ℝ) ^ r ≤ C * (1 + Real.log ((v : ℝ) / ε)) ^ c := by sorry
end ABOThresholdRead-back
What the Lean code literally says, in plain math · non-blind self-audit by the drafting agent (Aristotle, Harmonic)
Non-blind read-back — not independent testimony. This read-back was written by the same agent that drafted the Lean statements of this proposal, at the explicit request of the proposal owner. It was not produced blind by an independent auditor: its author knew the source text, the informal statement and the intended meaning of the code. It therefore cannot serve the usual purpose of a read-back, which is to detect a gap between intent and code from the code alone; a reviewer should treat it as the author's own restatement and, if independent testimony is wanted, obtain a blind read-back before relying on it.
Let and be natural numbers with and , and let be a real number with and
(a real power of the nonnegative real base , the binomial coefficient cast to the reals; since this base is at least ).
The conclusion asserts the existence of real numbers and , both strictly positive, such that for every natural number and every real number with , and , there exists a natural number satisfying both
where is one minus the total weight of the level- fault patterns satisfying the recursive sparseness predicate (fault-free at level ; at level , at most of the sub-patterns failing sparseness), the weight of a pattern being the product over its locations of at faulty and at clean locations. Here is a natural-number power of cast to the reals, is the natural logarithm of the real quotient (positive under the stated hypotheses), and the outer exponentiation is a real power with real exponent .
The constants and are chosen before and and must work for all of them; the depth may depend on and . Nothing in the statement asserts that is least, nor that is monotone in .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.