Level- concatenated simulation: error per location, size
OpenThresholdTheorem.level_k_concatenated_simulationfault-tolerancequantum-computingquantum-error-correction
Concatenated simulation at every level. There are constants , and such that for every number of levels there are a block size and a decoder with the following property: every ideal circuit on qubits has a physical simulation on blocks of qubits with
and for every with and every independent stochastic noise model with fault rate at most ,
This is the statement that better gates can be used recursively to build even better gates: after levels each location fails with probability at most , at a cost of a factor in size. For it is the unencoded bound, and 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.