TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Planar Surface-Code Memory Bound Under IID Z Noise

Statement

For each integer $d \geq 2$ , use the relative $d \times d$ square patch, which has $n = 2 d^{2}$ data qubits. On a finite probability space, let each data edge independently carry a $Z$ error with probability $ϵ \in [0, 1]$ . For each syndrome, choose any minimum-cardinality correction; the bound below holds for every such choice. Under one perfect syndrome round, the logical-memory failure probability satisfies

P_{l o g i c a l} \leq (d + 1) \sum_{ℓ = d}^{n} (36 ϵ)^{ℓ / 2} .

Consequently $P_{l o g i c a l}$ decays exponentially in $d$ , up to a polynomial prefactor, for $ϵ < 1 / 36$ . This is an ideal-syndrome memory theorem; it is not a faulty-gate circuit threshold.

Facts & Assumptions

Given: An integer $d \geq 2$ , the finite relative square patch with data-edge count $n = 2 d^{2}$ , a finite family of mutually independent Bernoulli $Z$ -error indicators each of rate $ϵ \in [0, 1]$ , one perfect syndrome round, minimum-cardinality recovery, and the geometric path interface in [F3].

[F1]

Finite probability spaces, outcome weights, events, and event probabilities: A finite probability space is a pair $(Ω, w)$ consisting of a finite set and nonnegative weights summing to one; event probabilities are sums of outcome weights.

[F2]

Minimum-Weight Recovery Failure Yields a Half-Error Crossing Path: On logical failure, a minimum-cardinality correction with the same perfect syndrome yields a self-avoiding left-to-right path of length $d \leq ℓ \leq n$ containing at least $⌈ ℓ / 2 ⌉$ actual error edges.

[F3]

Square planar surface-code distance and path count: For each $ℓ \geq 1$ , the number of self-avoiding rough-to-rough paths of length $ℓ$ is at most $(d + 1) 3^{ℓ}$ .

[F4]

Independent families of event classes: The family $(C_{i})_{i \in I}$ is independent when for every natural number $n \geq 1$ , every choice of distinct indices $i_{0}, \dots, i_{n - 1}$ , and every choice of events $A_{k} \in C_{i_{k}}$ , one has $P (⋂_{k < n} A_{k}) = \prod_{k < n} P (A_{k})$ .

[F5]

The finite union bound: For every finite family of events $A_{0}, \dots, A_{n - 1}$ , $P ⁣ (⋃_{i < n} A_{i}) \leq \sum_{i < n} P (A_{i}) .$

Proof

1.1givenF1F2F4F5algebra

Fix a candidate path $P$ of length $ℓ$ . A logical failure witness on it requires at least $k = ⌈ ℓ / 2 ⌉$ actual errors by [F2]. If at least $k$ of its $ℓ$ edges are faulty, some $k$ -subset is entirely faulty. There are at most $(\binom{ℓ}{k}) \leq 2^{ℓ}$ such subsets; by [F4] each has probability $ϵ^{k} \leq ϵ^{ℓ / 2}$ for $ϵ \in [0, 1]$ . The union bound [F5] gives $P (P is a failure witness) \leq 2^{ℓ} ϵ^{ℓ / 2}$ .

2.1F2F3F5step 1.1algebra

There are at most $(d + 1) 3^{ℓ}$ candidate paths of length $ℓ$ by [F3]. By [F2], every logical failure lies in the union of witness events for paths with $d \leq ℓ \leq n$ . The finite union bound [F5] and step 1.1 therefore give $P_{l o g i c a l} \leq \sum_{ℓ = d}^{n} (d + 1) 3^{ℓ} 2^{ℓ} ϵ^{ℓ / 2} = (d + 1) \sum_{ℓ = d}^{n} (36 ϵ)^{ℓ / 2}$ .

3.1step 2.1algebra∎

If $ϵ < 1 / 36$ , set $r = 6 \sqrt{ϵ} < 1$ . The finite sum is at most $\sum_{ℓ = d}^{\infty} r^{ℓ} = r^{d} / (1 - r)$ , so $P_{l o g i c a l} \leq \frac{d + 1}{1 - 6 \sqrt{ϵ}} (6 \sqrt{ϵ})^{d}$ . The denominator is a fixed positive constant for fixed $ϵ < 1 / 36$ , while $d + 1$ is polynomial in $d$ ; hence the bound decays exponentially up to a polynomial prefactor.

Remarks

The geometric inputs are the relative-cycle crossing property and the finite path count in [F2] and [F3]. The probability argument uses their stated directions only; it needs no enumeration of all logical operators and no assumption about independence of recovery choices. Perfect syndrome and iid $Z$ -noise are essential hypotheses. No circuit-level gate threshold follows.

Depends on

Used by

Surface-Code Memory Bound Under IID Z Noise Example

Dependency tree · two levels

28 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

John Preskill, Quantum Computation, Chapter 7: Quantum Error Correction (standard reference, not scraped)
John Preskill, Toric code recovery, fault-tolerant recovery, fault-tolerant gates (2011 handwritten lecture notes) (standard reference, not scraped)