This paper aims to give an overview of the current state of fault-tolerant quantum computing, by surveying a number of results in the field. We show that thresholds can be obtained for a simple noise model as first proved in [AB97, Kit97, KLZ98], by presenting a proof for statistically independent noise, following the presentation of Aliferis, Gottesman and Preskill [AGP06]. We also present a result by Terhal and Burkard [TB05] and later improved upon by Aliferis, Gottesman and Preskill [AGP06] that shows a threshold can still be obtained for local non-Markovian noise, where we allow the noise to be weakly correlated in space and time. We then turn to negative results, presenting work by Ben-Aroya and Ta-Shma [BT11] who showed conditional errors cannot be perfectly corrected. We end our survey by briefly mentioning some more speculative objections, as put forth by Kalai [Kal08, Kal09, Kal11].
Aliferis, Gottesman and Preskill [1] reduce a non-Markovian noise model to a local noise model, under assumptions on the smallness of the norm of the system-bath interaction. They also prove constructively that given a local noise model, it is possible to simulate an ideal quantum circuit with size L and depth D up to any accuracy, using circuit constructed out of noisy gates from the Boykin set with size
L′=O(L(logL)a) and depth
D′=O(D(logD)b), where
a and
b are constants that depend on the error correction code that we choose and the design of the fault-tolerant architecture, in addition to more assumptions [1]. These two results combined give us a fault-tolerant threshold theorem for non-Markovian noise, provided that the strength of the effective local noise model is smaller than a positive number that depends on the fault-tolerant architecture we choose. However the ideal measurement process may involve a strong system-bath interaction which necessarily gives a local noise model of large strength. We refine the reduction of the non-Markovian noise model to the local noise model such that this need not be the case, provided that system-bath interactions from the non-ideal operations is sufficiently small. We make all assumptions that [1] has already made, in addition to a few more assumptions to obtain our result. We also give two specific instances where the norm of the fault gets suppressed by some paramater other than the norm of the system-bath interaction. These include the large ratio of the norm of the ideal Hamiltonian to the norm of the perturbation, and frequency of oscillation of the perturbation. We hence suggest finding specific phenomenological models of noise that exhibit these properties.
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on
Nˉ logical qudits of depth
Tˉ, we construct a fault-tolerant circuit on
N=poly(Nˉ) physical qudits of depth
Tˉ⋅Nˉo(1), which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number
N1−o(1) of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits.
Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance.
Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.
This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when
η, the probability for an error in a qubit or a gate, is smaller than a constant threshold
ηc. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate
η decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with
p>2 states, namely, p-qudits, and is also generalized to one-dimensional quantum computers with only nearest-neighbor interactions. No measurements, or classical operations, are required during the quantum computation. We estimate the threshold of our construction to be
ηc≃10−6, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that two-qubit gates are universal, together with their extensions to higher-dimensional particles. We also provide full proofs of the universality of the sets of gates we use (the proof of universality was missing in Shor's paper). This paper thus provides a self-contained and complete proof of universal fault-tolerant quantum computation in the presence of local noise.