The model of quantum computation developed by Kitaev (1 ,∮4.1) shows that a perfect, error-free, quantum computer can lead to reliable classical outputs, despite the need to apply a necessarily probabilistic measurement. In this paper we extend the analysis to account for necessarily imperfect quantum computation. The analysis presented here is required to establish the utility of practical quantum computation even given the assumption that fault-tolerance techniques are successfully applied. This is due to the fact that the application of currently known fault-tolerance techniques does not permanently and completely remove errors. To this end we have introduced a mathematical relation that compares the accuracy of a necessarily imperfect quantum computation to a prescribed performance bound. Finally, we discuss several mathematical aspects of this bound and its usefulness in analyzing quantum computing protocols.
The model of quantum computation developed by Kitaev (1 ,∮4.1) shows that a perfect, error-free, quantum computer can lead to reliable classical outputs, despite the need to apply a necessarily probabilistic measurement. In this paper we extend the analysis to account for necessarily imperfect quantum computation. The analysis presented here is required to establish the utility of practical quantum computation even given the assumption that fault-tolerance techniques are successfully applied. This is due to the fact that the application of currently known fault-tolerance techniques does not permanently and completely remove errors. To this end we have introduced a mathematical relation that compares the accuracy of a necessarily imperfect quantum computation to a prescribed performance bound. Finally, we discuss several mathematical aspects of this bound and its usefulness in analyzing quantum computing protocols.
In this paper we extend both standard fault tolerance theory and Kitaev's model for quantum computation, combining them so as to yield quantitative results that reveal the interplay between the two. Our analysis establishes a methodology that allows us to quantitatively determine design parameters for a quantum computer, the values of which ensure that an overall computation of interest yields a correct *final result* with some prescribed probability of success, as opposed to merely ensuring that the desired *final quantum state* is obtained. As a specific example of the practical application of our approach, we explicitly calculate the number of levels of error correction concatenation needed to achieve a correct final result for the overall computation with some prescribed success probability. Since our methodology allows one to determine parameters required in order to achieve the correct final result for the overall quantum computation, as opposed to merely ensuring that the desired final quantum state is produced, our method enables the determination of complete quantum computational resource requirements associated to the actual solution of practical problems.
We extend standard fault tolerance theory and Kitaev’s model for quantum computation so as to enable quantitative determination of design parameters for quantum computers that ensure that the overall computation yields a correct final result with some prescribed probability, as opposed to merely ensuring that the desired final quantum state is obtained. Our extension allows us to explicitly calculate the number of levels of error correction concatenation needed to achieve a correct final result with some prescribed success probability and demonstrate a clear connection between error correction and fault tolerance.
The Quantum Computer Condition (QCC) provides a rigorous and completely general framework for carrying out analyses of questions pertaining to fault-tolerance in quantum computers. In this paper we apply the QCC to the problem of fluctuations and systematic errors in the values of characteristic parameters in realistic systems. We show that fault-tolerant quantum computation is possible despite variations in these parameters. We also use the QCC to explicitly show that reliable classical computation can be carried out using as input the results of fault-tolerant, but imperfect, quantum computation. Finally, we consider the advantages and disadvantages of the superoperator and diamond norms in connection with application of the QCC to various quantum information-theoretic problems.
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.
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.
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.