Concatenated Repetition Codes: strict threshold advantage over every single cat
OpenQAlgorithms.Papers.Independent.Intakenext100.P93.concatenation_improves_single_catConsider independent depolarizing noise with total nonidentity probability and . For an inner length and a positive outer length , construct the encoder
where . Apply the physical channel and the inverse two-level decoder, measuring and retaining every inner Z syndrome and the outer X syndrome. Let be the coherent information of this actual flagged Bell output divided by , and let be the corresponding single-cat rate. For any such rate function define its low-noise positivity threshold by . Then
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 with , 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 and rate slack , all sufficiently large positive outer blocklengths admit a code with logical qubits and both entanglement fidelity and every normalized pure-input transmission fidelity at least . The encoder and decoder are chosen before the unknown input.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P93
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exist natural numbers , with or , satisfying the following assertions, with the same throughout. To specify the quantities, write , identify bits with , let , and define
Thus maps a bit to a constant string of length , while has rows indexed by strings of length . For , let
Tensor extensions of matrix maps are defined entrywise by
Put , write , and define the decoding matrices
For and , define
Define raw output matrices and matrices with additional classical labels by
Here an identity extension applies the indicated map to each block indexed by the reference bits . For a matrix , let , using continuous functional calculus with and its totalized value ; let mean summing over equal row and column indices of the reference-bit register. The two rate functions occurring in the assertion are
First, for every real with and , the following property holds: for every , there exists such that every natural number admits a natural number , a matrix , and a map from matrices indexed by to matrices indexed by , with
There must be a commuting subgroup of the unitaries on , contained in the subgroup generated by all phase multiples , where and , such that and . The map must be expressible as for finitely many matrices satisfying . Writing
one must have
Second, define for any real-valued function
For every natural number , including , the strict inequality holds. The supremum includes even when there are no parameters with positive rate. No positivity assumption is imposed on , so is included among the possible witnesses; likewise is allowed in the quantified coding property, and the achievability assertion includes parameters where .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.