Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

CRC Press eBooks

Quantum Mechanics

Frank Gaitan

Published Feb 7, 2008• 0 citations
Publisher

Abstract

In Chapters 2-5 we gave a detailed presentation of the theory of quantum error correction and fault-tolerant quantum computing. The stage is finally set for a proof of the accuracy threshold theorem [2-9]. As pointed out in Chapter 1, this theorem spells out the conditions under which quantum computing can be done reliably using imperfect quantum gates and in the presence of noise. The proof presented in this chapter follows Ref. [6]. Section 6.1 addresses a number of preliminary topics. It explains why a concatenated quantum error correcting code (QECC) should be used to protect the computational data when fault-tolerance is an issue; it states the principal assumptions underlying the threshold calculations presented in Section 6.2; and finally, it closes with a statement of the accuracy threshold theorem. The proof of this theorem is taken up in Section 6.2. For the error model introduced in Section 6.1, the accuracy threshold is calculated for gates in the Clifford group N(Qn), storage registers, and the Toffoli gate. The calculations make explicit use of the recursive structure of a concatenated QECC and the fault-tolerant procedures introduced in Chapter 5. The theorem is proved by showing that all three cases yield non-zero threshold values.

DOI
10.1201/b15868-10

Related papers

Quantum Error Correction and Fault Tolerant Quantum Computing

Frank Gaitan

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.

CRC Press eBooks•Dec 19, 2013•97 citations

Accuracy Threshold Theorem

Frank Gaitan

In this chapter we begin to examine quantum stabilizer codes in detail. Sec­ tion 3.1 introduces the theoretical framework that underlies this class of quan­ tum error correcting codes, and some examples are given in Section 3.2. Sec­ tion 3.3 shows how these codes can be described in terms of a binary vector space with symplectic inner product, and finally, concatenated quantum er­ ror correcting codes are introduced in Section 3.4. The latter discussion will focus on concatenated codes that are put together using quantum stabilizer codes. We will see in Chapter 6 that concatenated codes play an important role in establishing the accuracy threshold theorem for fault-tolerant quantum computing.

CRC Press eBooks•Feb 7, 2008•0 citations

QUANTUM ERROR CORRECTION AND FAULT-TOLERANT QUANTUM COMPUTING

Frank Gaitan, Ran Li

We review the theories of quantum error correction, and of fault-tolerant quantum computing, and show how these powerful tools are combined to prove the accuracy threshold theorem for a particular error model. One of the theorem's assumptions is the availability of a universal set of unencoded quantum gates whose error probabilities P e fall below a value known as the accuracy threshold P a . For many, P a ~ 10 -4 has become a rough estimate for the threshold so that quantum gates are anticipated to be approaching the accuracies needed for fault-tolerant quantum computing when P e < 10 -4 . We show how controllable quantum interference effects that arise during a type of non-adiabatic rapid passage can be used to produce a universal set of quantum gates whose error probabilities satisfy P e < 10 -4 . We close with a discussion of the current challenges facing an experimental implementation of this approach to reliable universal quantum computation.

•Nov 1, 2009•44 citations

An introduction to quantum error correction and fault-tolerant quantum computation

Daniel Gottesman

Quantum states are very delicate, so it is likely some sort of quantum error correction will be necessary to build reliable quantum computers.The theory of quantum error-correcting codes has some close ties to and some striking differences from the theory of classical error-correcting codes.Many quantum codes can be described in terms of the stabilizer of the codewords.The stabilizer is a finite Abelian group, and allows a straightforward characterization of the error-correcting properties of the code.The stabilizer formalism for quantum codes also illustrates the relationships to classical coding theory, particularly classical codes over GF(4), the finite field with four elements.To build a quantum computer which behaves correctly in the presence of errors, we also need a theory of fault-tolerant quantum computation, instructing us how to perform quantum gates on qubits which are encoded in a quantum errorcorrecting code.The threshold theorem states that it is possible to create a quantum computer to perform an arbitrary quantum computation provided the error rate per physical gate or time step is below some constant threshold value.

arXiv:0904.2557•Proceedings of symposia in applied mathematics•Jan 1, 2010•798 citations

Fault-tolerant computation without concatenation

Eric Dennis

It has been known that error-correction via concatenated codes can be done with exponentially small failure rate if the error rate for physical qubits is below a certain accuracy threshold (probably ∼ 10 −3 –10 −6). Other, un-concatenated codes with their own attractive features—e.g., an accuracy threshold ∼ 10 −2 —have also been studied. A method to obtain universal computation is presented here which does not rely on any concatenated structure within the code itself, but instead emulates this structure with logical qubits in order to construct an encoded Toffoli gate. This realizes ∼ 10 −2 as a threshold for fault-tolerant quantum computation. 1 QEC codes and universal computation In the “space ” of all possible quantum error-correcting codes, much recent work has focused on a relatively small class, namely concatenated codes [1]–[7]. The basic idea behind these is to improve the results of a given few-qubit code by

•May 7, 1999•2 citations

Models of fault-tolerant quantum computation

Christopher M. Dawson

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.

•Jan 1, 2006•0 citations
In Chapters 2-5 we gave a detailed presentation of the theory of quantum error correction and fault-tolerant quantum computing. The stage is finally set for a proof of the accuracy threshold theorem [2-9]. As pointed out in Chapter 1, this theorem spells out the conditions under which quantum computing can be done reliably using imperfect quantum gates and in the presence of noise. The proof presented in this chapter follows Ref. [6]. Section 6.1 addresses a number of preliminary topics. It explains why a concatenated quantum error correcting code (QECC) should be used to protect the computational data when fault-tolerance is an issue; it states the principal assumptions underlying the threshold calculations presented in Section 6.2; and finally, it closes with a statement of the accuracy threshold theorem. The proof of this theorem is taken up in Section 6.2. For the error model introduced in Section 6.1, the accuracy threshold is calculated for gates in the Clifford group N(Qn), storage registers, and the Toffoli gate. The calculations make explicit use of the recursive structure of a concatenated QECC and the fault-tolerant procedures introduced in Chapter 5. The theorem is proved by showing that all three cases yield non-zero threshold values.
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.
In this chapter we begin to examine quantum stabilizer codes in detail. Sec­ tion 3.1 introduces the theoretical framework that underlies this class of quan­ tum error correcting codes, and some examples are given in Section 3.2. Sec­ tion 3.3 shows how these codes can be described in terms of a binary vector space with symplectic inner product, and finally, concatenated quantum er­ ror correcting codes are introduced in Section 3.4. The latter discussion will focus on concatenated codes that are put together using quantum stabilizer codes. We will see in Chapter 6 that concatenated codes play an important role in establishing the accuracy threshold theorem for fault-tolerant quantum computing.
We review the theories of quantum error correction, and of fault-tolerant quantum computing, and show how these powerful tools are combined to prove the accuracy threshold theorem for a particular error model. One of the theorem's assumptions is the availability of a universal set of unencoded quantum gates whose error probabilities P e fall below a value known as the accuracy threshold P a . For many, P a ~ 10 -4 has become a rough estimate for the threshold so that quantum gates are anticipated to be approaching the accuracies needed for fault-tolerant quantum computing when P e < 10 -4 . We show how controllable quantum interference effects that arise during a type of non-adiabatic rapid passage can be used to produce a universal set of quantum gates whose error probabilities satisfy P e < 10 -4 . We close with a discussion of the current challenges facing an experimental implementation of this approach to reliable universal quantum computation.
Quantum states are very delicate, so it is likely some sort of quantum error correction will be necessary to build reliable quantum computers.The theory of quantum error-correcting codes has some close ties to and some striking differences from the theory of classical error-correcting codes.Many quantum codes can be described in terms of the stabilizer of the codewords.The stabilizer is a finite Abelian group, and allows a straightforward characterization of the error-correcting properties of the code.The stabilizer formalism for quantum codes also illustrates the relationships to classical coding theory, particularly classical codes over GF(4), the finite field with four elements.To build a quantum computer which behaves correctly in the presence of errors, we also need a theory of fault-tolerant quantum computation, instructing us how to perform quantum gates on qubits which are encoded in a quantum errorcorrecting code.The threshold theorem states that it is possible to create a quantum computer to perform an arbitrary quantum computation provided the error rate per physical gate or time step is below some constant threshold value.
It has been known that error-correction via concatenated codes can be done with exponentially small failure rate if the error rate for physical qubits is below a certain accuracy threshold (probably ∼ 10 −3 –10 −6). Other, un-concatenated codes with their own attractive features—e.g., an accuracy threshold ∼ 10 −2 —have also been studied. A method to obtain universal computation is presented here which does not rely on any concatenated structure within the code itself, but instead emulates this structure with logical qubits in order to construct an encoded Toffoli gate. This realizes ∼ 10 −2 as a threshold for fault-tolerant quantum computation. 1 QEC codes and universal computation In the “space ” of all possible quantum error-correcting codes, much recent work has focused on a relatively small class, namely concatenated codes [1]–[7]. The basic idea behind these is to improve the results of a given few-qubit code by
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.