A two-dimensional architecture is considered in which logical qubits are stored on isolated cells. Intra-logical transport is via nearest-neighbor SWAP operations and inter-logical operation is via short-distance qubit transport. Non-local quantum circuitry is adapted to this architecture to implement fault tolerant quantum computation under the [[7,1,3]] quantum code. The CNOT gate threshold for this architecture is estimated and is presented as an explicit physical gate failure rate in a number of common physical settings.
This paper proves the threshold result, which asserts that quantum computation can be made robust against errors and inaccuracies, when the error rate,
η, is smaller than a constant threshold,
ηc. The result holds for a very general, not necessarily probabilistic noise model, for quantum particles with any number of states, 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. The proceeding version was very succinct, and here we fill all the missing details, and elaborate on many parts of the proof. In particular, we devote a section for a discussion of universality issues and proofs that the sets of gates that we use are universal. Another section is devoted to a rigorous proof that fault tolerance can be achieved in the presence of general non probabilistic noise. The systematic structure of the fault tolerant procedures for polynomial codes is explained in length. The proof that the concatenation scheme works is written in a clearer way. The paper also contains new and significantly simpler proofs for most of the known results which we use. For example, we give a simple proof that it suffices to correct bit and phase flips, we significantly simplify Calderbank and Shor's original proof of the correctness of CSS codes. We also give a simple proof of the fact that two-qubit gates are universal. The paper thus provides a self contained and complete proof for universal fault tolerant quantum computation.
The performance of fault-tolerant quantum computation with concatenated codes using local gates in small numbers of spatial dimensions is discussed. It is shown that a threshold result still exists in three, two, or one spatial dimensions when next-to-nearest-neighbour gates are available, and explicit constructions are presented. In two or three dimensions, it is also shown how nearest-neighbour gates can give a threshold result. In all cases, it is simply demonstrated that a threshold exists, and no attempt to optimize the error correction circuit or to determine the exact value of the threshold is made. The additional overhead due to the fault-tolerance in both space and time is polylogarithmic in the error rate per logical gate.
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.
Estimates of the quantum accuracy threshold often tacitly assume that it is possible to interact arbitrary pairs of qubits in a quantum computer with a failure rate that is independent of the distance between them. None of the many physical systems that are candidates for quantum computing possess this property. Here we study the performance of a concatenated error-detection code in a system that permits only nearest-neighbor interactions in one dimension. We make use of a message-passing scheme that maximizes the number of errors that can be reliably corrected by the code. Our numerical results indicate that arbitrarily accurate universal quantum computation is possible if the probability of failure of each elementary physical operation is below approximately ${10}^{\ensuremath{-}5}$. This threshold is three orders of magnitude lower than the highest known.
We present a fault-tolerant universal quantum computing architecture based on a code concatenation of biased-noise qubits and the parity architecture. The parity architecture can be understood as a low-density parity-check code tailored specifically to obtain any desired logical connectivity from nearest-neighbor physical interactions. The code layout can be dynamically adjusted to algorithmic requirements on the fly. This allows for implementations with any desired code distance with a universal set of fault-tolerant gates. In addition to the previously explored toolsets for concatenated cat codes, our approach features parallelizable interactions between arbitrary sets of qubits by directly addressing the parity qubits in the code. The proposed scheme supports codes with lower physical qubit overhead than the repetition code at the same code distances, while requiring only weight-3 and weight-4 stabilizers and nearest-neighbor connectivity on a two-dimensional square lattice.