LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generated

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.

Recursive Bad-Rectangle Probability

Statement

Let $a \geq 2$ and $1 \leq q < a$ be integers and let $η \in [0, 1]$ . For each integer $r \geq 0$ , suppose every level- $(r + 1)$ rectangle has at most $a$ level- $r$ children, the family has full depth $r + 1$ (every root-to-leaf path has exactly $r + 1$ child edges), the leaves are single elementary locations, and sibling elementary-location sets are pairwise disjoint. A level-zero rectangle is bad exactly when its location faults, and a parent is bad only if at least $q + 1$ children are bad. Put $A = (\binom{a}{q + 1})$ , the number of $(q + 1)$ -subsets of an $a$ -element set, and define $p_{0} = η$ and $p_{r + 1} = \min {1, A p_{r}^{q + 1}}$ . Under independent local faults of rate $η$ , $p_{r}$ is a uniform upper bound for the probability that a level- $r$ rectangle is bad. Moreover, $p_{r + 1} \leq A p_{r}^{q + 1}$ and $p_{r} \leq A^{- 1 / q} (A^{1 / q} η)^{(q + 1)^{r}}$ . If $A η^{q} < 1$ , then $p_{r} \to 0$ super-exponentially in $r$ . No independence of child badness is inferred without the disjoint-location hypothesis.

Facts & Assumptions

Given: A finite independent local fault model, a full-depth rooted hierarchy with one elementary location per leaf and pairwise disjoint sibling location sets, and a parent bad only when at least $q + 1$ of at most $a$ children are bad. Prove the recurrence and closed form.

[F1]

Independent Local Quantum Fault Model: Elementary fault indicators are mutually independent and each has probability $η$ .

[F2]

Good and Bad Concatenated Rectangles: A parent has at most $a$ disjoint child rectangles and is bad only if at least $q + 1$ children are bad.

[F3]

Disjoint Fault-Location Events Are Independent: Events determined by disjoint child location sets are independent.

Proof

1.1givenF1F2constructinduction

Define a dominating event $B_{v}$ for each rectangle $v$ : at a leaf it is the event that its location faults, and at a parent it is the event that at least $q + 1$ children satisfy their events $B$ . By finite induction, actual badness implies $B_{v}$ , using the stated one-sided badness rule. Each $B_{v}$ depends only on the fault indicators in $v$ . At level zero its probability is $η = p_{0}$ by [F1]. For a level- $(r + 1)$ parent, $B_{v}$ is the union over the at most $A = (\binom{a}{q + 1})$ child subsets $J$ of the events that all their $B_{j}$ occur.

2.1givenF1F2F3step 1.1inductionalgebra

Suppose every level- $r$ event $B_{j}$ has probability at most $p_{r}$ . For each fixed $J$ , these events depend on pairwise disjoint location sets, so they are independent by [F3], and their intersection has probability at most $p_{r}^{q + 1}$ . The indicator of a finite union is at most the sum of its event indicators. Summing probabilities over the at most $A$ choices of $J$ , and also using that a probability is at most one, gives $P (B_{v}) \leq \min {1, A p_{r}^{q + 1}} = p_{r + 1}$ . Induction from step 1.1 proves that $p_{r}$ bounds every $B_{v}$ and hence every actual bad probability at its level. Its defining recursion also gives $p_{r + 1} \leq A p_{r}^{q + 1}$ .

3.1step 2.1algebra

Set $θ = A^{1 / q} η$ . The asserted closed form holds at $r = 0$ , since $A^{- 1 / q} θ = η$ . If it holds at $r$ , then $p_{r + 1} \leq A (A^{- 1 / q} θ^{(q + 1)^{r}})^{q + 1} = A^{- 1 / q} θ^{(q + 1)^{r + 1}}$ , because $1 - (q + 1) / q = - 1 / q$ . Induction proves the formula for every $r$ .

4.1givenstep 3.1algebra∎

The condition $A η^{q} < 1$ is equivalent to $0 \leq θ < 1$ . For $A \geq 1$ and $q + 1 > 1$ , the exponent $(q + 1)^{r}$ tends to infinity, so the closed-form upper bound tends to zero.

Depends on

Used by

Conditional Concatenated Threshold for Proper Codes Theorem

Dependency tree · two levels

8 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

D. Aharonov and M. Ben-Or, Fault-Tolerant Quantum Computation With Constant Error (standard reference, not scraped)
John Preskill, Quantum Computation, Chapter 7: Quantum Error Correction (standard reference, not scraped)