Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error–correction, fault–tolerant state recovery, fault–tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.
Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error–correction, fault–tolerant state recovery, fault–tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.
Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error-correction, fault tolerant state recovery, fault tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.
Quantum computers have the potential to solve several interesting problems in polynomial \ntime for which no polynomial time classical algorithms have been found. However, \none of the major challenges in building quantum devices is that quantum systems are very \nsensitive to noise arising from undesired interactions with the environment. Noise can lead \nto errors which can corrupt the results of the computation. Quantum error correction is \none way to mitigate the effects of noise arising in quantum devices. \nWith a plethora of quantum error correcting codes that can be used in various settings, \none of the main challenges of quantum error correction is understanding how well various \ncodes perform under more realistic noise models that can be observed in experiments. \nThis thesis proposes a new decoding algorithm which can optimize threshold values of \nerror correcting codes under different noise models. The algorithm can be applied to \nany Markovian noise model. Further, it is shown that for certain noise models, logical \nClifford corrections can further improve a code's threshold value if the code obeys certain \nsymmetries. \n \nSince gates and measurements cannot in general be performed with perfect precision, \nthe operations required to perform quantum error correction can introduce more errors \ninto the system thus negating the benefits of error correction. Fault-tolerant quantum \ncomputing is a way to perform quantum error correction with imperfect operations while \nretaining the ability to suppress errors as long as the noise is below a code's threshold. \nOne of the main challenges in performing fault-tolerant error correction is the high resource \nrequirements that are needed to obtain very low logical noise rates. With the use of \nflag qubits, this thesis develops new fault-tolerant error correction protocols that are applicable \nto arbitrary distance codes. Various code families are shown to satisfy the requirements \nof flag fault-tolerant error correction. We also provide circuits using a constant number of \nqubits for these codes. It is shown that the proposed flag fault-tolerant method uses fewer \nqubits than previous fault-tolerant error correction protocols. \n \nIt is often the case that the noise afflicting a quantum device cannot be fully characterized. \nFurther, even with some knowledge of the noise, it can be very challenging to use \nanalytic decoding methods to improve the performance of a fault-tolerant scheme. This \nthesis presents decoding schemes using several state of the art machine learning techniques \nwith a focus on fault-tolerant quantum error correction in regimes that are relevant to near \nterm experiments. It is shown that even in low noise rate regimes and with no knowledge \nof the noise, noise can be further suppressed for small distance codes. Limitations of machine \nlearning decoders as well as the classical resources required to perform active error \ncorrection are discussed. \n \nIn many cases, gate times can be much shorter than typical measurement times of \nquantum states. Further, classical decoding of the syndrome information used in quantum \nerror correction to compute recovery operators can also be much slower than gate times. \nFor these reasons, schemes where error correction can be implemented in a frame (known \nas the Pauli frame) have been developed to avoid active error correction. In this thesis, we \ngeneralize previous Pauli frame schemes and show how Clifford frame error correction can \nbe implemented with minimal overhead. Clifford frame error correction is necessary if the \nlogical component of recovery operators were chosen from the Clifford group, but could \nalso be used in randomized benchmarking schemes.
This thesis is concerned with certain theoretical problems that arise naturally in the context of fault-tolerant quantum computation. Fault-tolerance can be defined as the art of building reliable devices from unreliable components, and is of particular importance for quantum computers that aim to precisely control the dynamics of extremely sensitive quantum systems. A model of quantum computation is a specification of the basic building blocks by which a quantum computation is implemented. The best known model is the quantum circuit model, where computations are implemented by means of unitary quantum gates that are applied to two-level quantum systems known as qubits. In a physical implementation of a quantum circuit, the gates and qubits will inevitably be affected by noise. Fault-tolerant quantum circuits are designed to be resilient against the effects of this noise, provided that it is not too strong. Fault-tolerance in the quantum circuit model is well developed thanks to the theory of quantum error-correcting codes. These codes allow for the correction of small numbers of errors introduced by a variety of noise processes. In a fault-tolerant quantum circuit, qubits are replaced with encoded qubits, and quantum gates with encoded gates that are immediately followed by special quantum circuits for error correction. Provided the rate at which errors occur is below a constant threshold value, the accumulation of errors can be checked so that the correct output of the computation correctly determined. The threshold acts as both a measure of how good the design of a quantum circuit is, and also as a target for experimenters aiming to implement quantum circuits. Much current research in quantum computation is aimed at designing quantum circuits that increase the noise threshold, hopefully to the point where it becomes within the reach of experimenters. A fault-tolerant encoded quantum gate must limit the propagation of errors so that the code’s corrective capabilities are not overwhelmed. It is not so easy to design encoded gates that satisfy this property, and to date only a finite handful of such gates are known. In a faulttolerant quantum circuit, all quantum gates must be decomposed or compiled in terms of those that may be implemented fault-tolerantly. In the first part of this thesis, we present two results that may be applied to this problem of gate compilation. The first is a generic method based on the Solovay-Kitaev theorem that may be applied to all quantum gates, but is most effective for those that act on single qubits. We present the Solovay-Kitaev theorem in its simples known form as an algorithm, together with novel constructions that can be used to implement it. Following this we give a two specialized methods for two-qubit gate decomposition, based on the Cartan decomposition of the Lie group SU(4). The cluster-state model of computation is an alternative to the quantum circuit model, and makes use of quantum measurements and highly entangled cluster-states to implement a quantum computation. The fault-tolerant techniques developed for quantum circuits are not immediately applicable in this model, so in order for it to be a realistic candidate for performing computations we prove that such techniques are possible. In the second part of the thesis we prove that constant fault-tolerance thresholds may be achieved in the cluster-state model, and in particular in an adaption to an optical implementation. Following this we design a complete error correction scheme for optical cluster-state computation, and numerically determine the threshold of this model in the face of the dominant noise models likely to affect such an implementation.
Abstract Quantum computing1—the processing of information according to the fundamental laws of physics—offers a means to solve efficiently a small but significant set of classically intractable problems. Quantum computers are based on the controlled manipulation of entangled quantum states, which are extremely sensitive to noise and imprecision; active correction of errors must therefore be implemented without causing loss of coherence. Quantum error-correction theory2, 3, 4, 5, 6, 7, 8, 9 has made great progress in this regard, by predicting error-correcting ‘codeword’ quantum states. But the coding is inefficient and requires many quantum bits10, 11, 12, which results in physically unwieldy fault-tolerant quantum circuits10, 11, 12, 13, 14, 15, 16, 17, 18. Here I report a general technique for circumventing the trade-off between the achieved noise tolerance and the scale-up in computer size that is required to realize the error correction. I adapt the recovery operation (the process by which noise is suppressed through error detection and correction) to simultaneously correct errors and perform a useful measurement that drives the computation. The result is that a quantum computer need be only an order of magnitude larger than the logic device contained within it. For example, the physical scale-up factor10, 11 required to factorize a thousand-digit number is reduced from 1, 500 to 22, while preserving the original tolerated gate error rate (10−5) and memory noise per bit (10−7). The difficulty of realizing a useful quantum computer is therefore significantly reduced.
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.