Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 58 / 3

Number the physical wires $1,\dots ,5$ from top to bottom and write a computational basis ket in that order. The first four are ancilla qubits and the fifth carries the input. It is enough to follow the basis input $|b⟩$, $b\in \{0,1\}$, because the encoding quantum circuit acts linearly.

The first fan-out consists of four controlled-NOT gates from wire 5 to wires 1–4. It sends $|0000b⟩$ to $|bbbbb⟩$. The three Hadamard gates then giveThe two Pauli X gates on wires 2 and 3, followed by a Controlled-Z gate and the same two X gates, restore the bits but contribute $(-1{)}^{(1-c)(1-d)}$: the sign is negative exactly when the original bits on both wires were zero. Finally, the right-hand controlled-NOT gates are $3\to 4$, $2\to 5$, $1\to 4$ and $1\to 5$. They leave the first three bits unchanged and turn the last two into $b\oplus a\oplus d$ and $b\oplus a\oplus c$. ThusExplicitly, the logical basis quantum states produced by the printed gates areEach has eight orthogonal terms of equal magnitude, and their supports are disjoint, so they are normalized and mutually orthogonal. The arbitrary input is therefore encoded asThis is a realization of the five-qubit error correcting code. The input amplitudes and their relative quantum phase are preserved in the logical subspace; the encoding is an entangled-state linear isometry, not five independent copies of the unknown input. The explicit signs and bit ordering above are fixed by this circuit, rather than by a convention for a different encoder.

Assume independent physical-qubit errors with common probability $p$, ideal encoding and recovery, and the specified rule that every block with two or more errors fails. The number of physical errors has a binomial distribution with parameters $5,p$. Correct recovery occurs for zero or one error, soThe corresponding logical failure probability isAn unencoded qubit succeeds with probability $1-p$. Thus encoding improves this probability precisely when $f(p)<p$. Factoring givesOn $0<p<1$, the sign is the sign of $g(p)=4p^3-11p^2+9p-1$. Its derivative is $12p^2-22p+9$: it is positive until $(11-\sqrt{13})/12$ and negative afterwards on $[0,1]$. Since $g(0)=-1$, $g(1)=1$ and its interior maximum is positive, there is exactly one zero in $(0,1)$. The five-qubit concatenation threshold is thereforeAt $p=p_{\ast }$ the two success probabilities agree; above it this decoder makes the error rate worse. At $p=0$ both schemes succeed perfectly, and at $p=1$ both fail under the stated error model. The small-$p$ behavior $f(p)=10p^2+O(p^3)$ exhibits cancellation of every single-qubit-error contribution.

Use a concatenated quantum error-correcting code: each of the five outer-code qubits is encoded in its own five-qubit inner block. Independent physical errors and ideal inner correction make each decoded block act as one outer qubit with error probability $q=f(p)$. Errors in distinct inner blocks remain independent in this model. Outer recovery succeeds if at most one of the five decoded blocks is bad, givingThus the two-level logical failure probability isThis improves the leading error order from $p$ for a bare qubit to $p^2$ for one level and $p^4$ for two. At least two physical errors must occur in each of two different inner blocks to defeat the prescribed two-stage decoder. Many error patterns with more than one error in the full 25-qubit register are therefore corrected: one error in each of all five blocks is removed at the inner level, and a single failed inner block is corrected at the outer level. Concentrating several physical errors in one block can be easier for this decoder than placing two errors in each of two blocks.

More generally, $\ell$ levels use $5^{\ell }$ physical qubits with recursion $p_{\ell +1}=f(p_{\ell })$. For $0<p<p_{\ast }$, one has $f(f(p))<f(p)<p$. Repeated concatenation decreases to zero: its limit must be a fixed point of the continuous function $f$, and below $p_{\ast }$ the only fixed point is zero. A simple quantitative bound is $f(x)\le 10x^2$, obtained by the union bound over the ten pairs of possible error positions. Induction giveswhich proves rapid suppression when $p<1/10$; the exact threshold is the larger value $p_{\ast }$. Above $p_{\ast }$ this recursion amplifies errors instead.

Below threshold, concatenation suppresses logical errors while allowing an entire bad inner block to be corrected at the next level. The cost is additional physical qubits, gates, syndrome extraction and recovery. The calculated threshold concerns the independent transmission-noise model with perfect encoding and recovery; including noisy operations or correlated channel errors requires a different error analysis.