Computers have led society to the information age revolutionizing central aspects of our lives from production and communication to education and entertainment. There exist, however, important problems which are intractable with the computers available today and, experience teaches us, will remain so even with the more advanced computers we can envision for tomorrow. Quantum computers promise speedups to some of these important but classically intractable problems. Simulating physical systems, a problem of interest in a diverse range of areas from testing physical theories to understanding chemical reactions, and solving number factoring, a problem at the basis of cryptographic protocols that are used widely today on the internet, are examples of applications for which quantum computers, when built, will offer a great advantage over what is possible with classical computer technology. The construction of a quantum computer of sufficient scale to solve interesting problems is, however, especially challenging. The reason for this is that, by its very nature, operating a quantum computer will require the coherent control of the quantum state of a very large number of particles. Fortunately, the theory of quantum error correction and fault-tolerant quantum computation gives us confidence that such quantum states can be created, can be stored in memory and can also be manipulated provided the quantum computer can be isolated to a sufficient degree from sources of noise. One of the central results in the theory of fault-tolerant quantum computation, the quantum threshold theorem shows that a noisy quantum computer can accurately and efficiently simulate any ideal quantum computation provided that noise is weakly correlated and its strength is below a critical value known as the quantum accuracy threshold. This thesis provides a simpler and more transparent non-inductive proof of this theorem based on the concept of level reduction. This concept is also used in proving the quantum threshold theorem for coherent and leakage noise and for quantum computation by measurements. In addition, the proof provides a methodology which allows us to establish improved rigorous lower bounds on the value of the quantum accuracy threshold.
Computers have led society to the information age revolutionizing central aspects of our lives from production and communication to education and entertainment. There exist, however, important problems which are intractable with the computers available today and, experience teaches us, will remain so even with the more advanced computers we can envision for tomorrow. Quantum computers promise speedups to some of these important but classically intractable problems. Simulating physical systems, a problem of interest in a diverse range of areas from testing physical theories to understanding chemical reactions, and solving number factoring, a problem at the basis of cryptographic protocols that are used widely today on the internet, are examples of applications for which quantum computers, when built, will offer a great advantage over what is possible with classical computer technology. The construction of a quantum computer of sufficient scale to solve interesting problems is, however, especially challenging. The reason for this is that, by its very nature, operating a quantum computer will require the coherent control of the quantum state of a very large number of particles. Fortunately, the theory of quantum error correction and fault-tolerant quantum computation gives us confidence that such quantum states can be created, can be stored in memory and can also be manipulated provided the quantum computer can be isolated to a sufficient degree from sources of noise. One of the central results in the theory of fault-tolerant quantum computation, the quantum threshold theorem shows that a noisy quantum computer can accurately and efficiently simulate any ideal quantum computation provided that noise is weakly correlated and its strength is below a critical value known as the quantum accuracy threshold. This thesis provides a simpler and more transparent non-inductive proof of this theorem based on the concept of level reduction. This concept is also used in proving the quantum threshold theorem for coherent and leakage noise and for quantum computation by measurements. In addition, the proof provides a methodology which allows us to establish improved rigorous lower bounds on the value of the quantum accuracy threshold.
The quantum threshold theorem shows that a noisy quantum computer can accurately and efficiently simulate any ideal quantum computation provided that noise is weakly correlated and its strength is below a critical value known as the quantum accuracy threshold. This thesis provides a simpler and more transparent non-inductive proof of this theorem based on the concept of level reduction. This concept is also used in proving the quantum threshold theorem for coherent and leakage noise and for quantum computation by measurements. In addition, the proof provides a methodology which allows us to establish improved rigorous lower bounds on the value of the quantum accuracy threshold.
It was once widely believed that quantum computation would never become a reality. However, the discovery of quantum error correction and the proof of the accuracy threshold theorem nearly ten years ago gave rise to extensive development and research aimed at creating a working, scalable quantum computer. Over a decade has passed since this monumental accomplishment yet no book-length pedagogical presentation of this important theory exists. Quantum Error Correction and Fault Tolerant Quantum Computing offers the first full-length exposition on the realization of a theory once thought impossible. It provides in-depth coverage on the most important class of codes discovered to date—quantum stabilizer codes. It brings together the central themes of quantum error correction and fault-tolerant procedures to prove the accuracy threshold theorem for a particular noise error model. The author also includes a derivation of well-known bounds on the parameters of quantum error correcting code. Packed with over 40 real-world problems, 35 field exercises, and 17 worked-out examples, this book is the essential resource for any researcher interested in entering the quantum field as well as for those who want to understand how the unexpected realization of quantum computing is possible.
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.
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 computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.