The discovery of quantum error correction has greatly improved the long-term prospects for quantum computing technology. Encoded quantum information can be protected from errors that arise due to uncontrolled interactions with the environment, or due to imperfect implementations of quantum logical operations. Recovery from errors can work effectively even if occasional mistakes occur during the recovery procedure. Furthermore, encoded quantum information can be processed without serious propagation of errors. In principle, an arbitrarily long quantum computation can be performed reliably, provided that the average probability of error per gate is less than a certain critical value, the accuracy threshold. It may be possible to incorporate intrinsic fault tolerance into the design of quantum computing hardware, perhaps by invoking topological Aharonov-Bohm interactions to process quantum information.
The discovery of quantum error correction has greatly improved the long-term prospects for quantum computing technology. Encoded quantum information can be protected from errors that arise due to uncontrolled interactions with the environment, or due to imperfect implementations of quantum logical operations. Recovery from errors can work effectively even if occasional mistakes occur during the recovery procedure. Furthermore, encoded quantum information can be processed without serious propagation of errors. In principle, an arbitrarily long quantum computation can be performed reliably, provided that the average probability of error per gate is less than a certain critical value, the accuracy threshold. It may be possible to incorporate intrinsic fault tolerance into the design of quantum computing hardware, perhaps by invoking topological Aharonov-Bohm interactions to process quantum information.
The new field of quantum error correction has developed spectacularly since its origin less than two years ago. Encoded quantum information can be protected from errors that arise due to uncontrolled interactions with the environment. Recovery from errors can work effectively even if occasional mistakes occur during the recovery procedure. Furthermore, encoded quantum information can be processed without serious propagation of errors. Hence, an arbitrarily long quantum computation can be performed reliably, provided that the average probability of error per quantum gate is less than a certain critical value, the accuracy threshold. A quantum computer storing about 106 qubits, with a probability of error per quantum gate of order 10–6, would be a formidable factoring engine. Even a smaller less–accurate quantum computer would be able to perform many useful tasks. This paper is based on a talk presented at the ITP Conference on Quantum Coherence and Decoherence, 15 to 18 December 1996.
One of the applications of quantum error correction is protecting quantum computers from noise. Certainly, there is nothing particularly quantum mechanical in the idea of protecting information by encoding it. Even ordinary digital computers use various fault tolerance methods at the software level to correct errors during the storage or the transmission of information; e.g., the integrity of the bits stored in hard disks is verified by using parity checks (checksums). In addition, for critical computing systems such as those inside airplanes or nuclear reactors, software fault tolerance methods are also applied during the processing of information; e.g., airplane control computers compare the results from multiple parallel processors to detect faults. In general, however, the hardware of modern computers is remarkably robust to noise, so that for most applications the processing of information can be executed with high reliability without using software error correction. In contrast to the ease and robustness with which classical information can be processed, the processing of quantum information appears at present to be much more challenging. Although constructing reliable quantum computing hardware is certainly a daunting task, we have nevertheless strong hopes that large-scale quantum computers, able to implement useful long computations, can in fact be realized. This optimism is founded on methods of quantum fault tolerance , which show that scalable quantum computation is, in principle, possible against a variety of noise processes.
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.
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.
The construction of a large-scale fault-tolerant quantum computer is an outstanding scientific and technological goal. It holds the promise to allow us to solve a variety of complex problems such as factoring large numbers, quick database search, and the quantum simulation of many-body quantum systems in fields as diverse as condensed matter, quantum chemistry, and even high-energy physics. Sophisticated theoretical protocols for reliable quantum information processing under imperfect conditions have been de-veloped, when errors affect and corrupt the fragile quantum states during storage and computations. Arguably, the most realistic and promising ap-proach towards practical fault-tolerant quantum computation are topologi-cal quantum error-correcting codes, where quantum information is stored in interacting, topologically ordered 2D or 3D many-body quantum systems. This approach offers the highest known error thresholds, which are already today within reach of the experimental accuracy in state-of-the-art setups. A combination of theoretical and experimental research is needed to store, protect and process fragile quantum information in logical qubits effectively so that they can outperform their constituting physical qubits. Whereas small-scale quantum error correction codes have been implemented, one of the main theoretical challenges remains to develop new and improve existing efficient strategies (so-called decoders) to derive (near-)optimal error cor-rection operations in the presence of experimentally accessible measurement information and realistic noise sources. One main focus of this project is the development and numerical implementation of scalable, efficient decoders to operate topological color codes. Additionally, we study the feasibility of im-plementing quantum error-correcting codes fault-tolerantly in near-term ion traps. To this end, we use realistic modeling of the different noise sources, computer simulations, and most modern quantum information approaches to quantum circuitry and noise suppression techniques.
The so-called "threshold" theorem says that, once the error rate per qubit per gate is below a certain value, indefinitely long quantum computation becomes feasible, even if all of the qubits involved are subject to relaxation processes, and all the manipulations with qubits are not exact. The purpose of this article, intended for physicists, is to outline the ideas of quantum error correction and to take a look at the proposed technical instruction for fault-tolerant quantum computation. It seems that the mathematics behind the threshold theorem is somewhat detached from the physical reality, and that some ideal elements are always present in the construction. This raises serious doubts about the possibility of large scale quantum computations, even as a matter of principle.