We prove a new version of the quantum threshold theorem that applies to concatenation of a quantum code that corrects only one error, and we use this theorem to derive a rigorous lower bound on the quantum accuracy threshold
ε0. Our proof also applies to concatenation of higher-distance codes, and to noise models that allow faults to be correlated in space and in time. The proof uses new criteria for assessing the accuracy of fault-tolerant circuits, which are particularly conducive to the inductive analysis of recursive simulations. Our lower bound on the threshold,
ε0≥2.73×10−5 for an adversarial independent stochastic noise model, is derived from a computer-assisted combinatorial analysis; it is the best lower bound that has been rigorously proven so far.
We rigorously analyze Knill's Fibonacci scheme for fault-tolerant quantum computation, which is based on the recursive preparation of Bell states protected by a concatenated error-detecting code. We prove lower bounds on the threshold fault rate of $0.67\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}$ for adversarial local stochastic noise, and $1.25\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}$ for independent depolarizing noise. In contrast to other schemes with comparable proved accuracy thresholds, the Fibonacci scheme has a significantly reduced overhead cost because it uses postselection far more sparingly.
The highest current estimates for the amount of noise a quantum computer can tolerate are based on fault-tolerance schemes relying heavily on postselecting on no detected errors. However, there has been no proof that these schemes give even a positive tolerable noise threshold. A technique to prove a positive threshold, for probabilistic noise models, is presented. The main idea is to maintain strong control over the distribution of errors in the quantum state at all times. This distribution has correlations which conceivably could grow out of control with postselection. But in fact, the error distribution can be written as a mixture of nearby distributions each satisfying strong independence properties, so there are no correlations for postselection to amplify
In this paper, we place bounds on when it is impossible to purify a noisy two-qubit state if all the gates used in the purification protocol are subject to adversarial, local, independent noise. It is found that the gate operations must be subject to less than 5.3% error. An existing proof that purification is equivalent to error correction is used to show that this bound can also be applied to concatenated error correcting codes in the presence of noisy gates, and hence gives a limit to the tolerable error rate for a fault-tolerant quantum computer formed by concatenation. This is shown to apply also to the case where error detection and postselection, as proposed by Knill, is used to enhance the threshold. We demonstrate the trade-off between gate and environmentally induced faulty rotations and qubit loss errors.
In Chapters 2-5 we gave a detailed presentation of the theory of quantum error correction and fault-tolerant quantum computing. The stage is finally set for a proof of the accuracy threshold theorem [2-9]. As pointed out in Chapter 1, this theorem spells out the conditions under which quantum computing can be done reliably using imperfect quantum gates and in the presence of noise. The proof presented in this chapter follows Ref. [6]. Section 6.1 addresses a number of preliminary topics. It explains why a concatenated quantum error correcting code (QECC) should be used to protect the computational data when fault-tolerance is an issue; it states the principal assumptions underlying the threshold calculations presented in Section 6.2; and finally, it closes with a statement of the accuracy threshold theorem. The proof of this theorem is taken up in Section 6.2. For the error model introduced in Section 6.1, the accuracy threshold is calculated for gates in the Clifford group N(Qn), storage registers, and the Toffoli gate. The calculations make explicit use of the recursive structure of a concatenated QECC and the fault-tolerant procedures introduced in Chapter 5. The theorem is proved by showing that all three cases yield non-zero threshold values.
Knill demonstrated a fault-tolerant quantum computation scheme based on concatenated error-detecting codes and postselection with a simulated error threshold of
3% over the depolarizing channel. We show how to use Knill's postselection scheme in a practical two-dimensional quantum architecture that we designed with the goal to optimize the error correction properties, while satisfying important architectural constraints. In our 2D architecture, one logical qubit is embedded in a tile consisting of
5×5 physical qubits. The movement of these qubits is modeled as noisy SWAP gates and the only physical operations that are allowed are local one- and two-qubit gates. We evaluate the practical properties of our design, such as its error threshold, and compare it to the concatenated Bacon-Shor code and the concatenated Steane code. Assuming that all gates have the same error rates, we obtain a threshold of
3.06×10−4 in a local adversarial stochastic noise model, which is the highest known error threshold for concatenated codes in 2D. We also present a Monte Carlo simulation of the 2D architecture with depolarizing noise and we calculate a pseudo-threshold of about
0.1%. With memory error rates one-tenth of the worst gate error rates, the threshold for the adversarial noise model, and the pseudo-threshold over depolarizing noise, are
4.06×10−4 and
0.2%, respectively. In a hypothetical technology where memory error rates are negligible, these thresholds can be further increased by shrinking the tiles into a
4×4 layout.