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

arXiv:1301.1995

Quantum Refrigerator

Michael Ben-Or, Daniel Gottesman, Avinatan Hassidim

Published Jan 9, 2013• 60 citations
arXivHTMLPDF

Abstract

We consider fault-tolerant quantum computation in the context where there are no fresh ancilla qubits available during the computation, and where the noise is due to a general quantum channel. We show that there are three classes of noisy channels: In the first, typified by the depolarizing channel, computation is only possible for a logarithmic time. In the second class, of which the dephasing channel is an example, computation is possible for polynomial time. The amplitude damping channel is an example of the third class, and for this class of channels, it is possible to compute for an exponential time in the number of qubits available.

DOI
10.48550/arxiv.1301.1995

Related papers

Fault-tolerant quantum computation with constant error

Dorit Aharonov, Michael Ben-Or

Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small. We improve this bound and describe fault tolerant quantum computation when the error probability is smaller than some constant threshold. The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The result holds also for quantum circuits which operate on nearest neighbors only. To achieve this noise resistance, we use concatenated quantum error correcting codes. The scheme presented is general, and works with all quantum codes that satisfy some restrictions, namely that the code is ``proper''. We present two explicit classes of proper quantum codes. The first example of proper quantum codes generalizes classical secret sharing with polynomials. The second uses a known class of quantum codes and converts it to a proper code. This class is defined over a field with p elements, so the elementary quantum particle is not a qubit but a ``qupit''. With our codes, the threshold is about 10^(-6). Hopefully, this paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical.

arXiv:quant-ph/9611025•ACM Symposium on Theory of Computing (STOC)•Jan 1, 1997•791 citations

Topics in Fault-Tolerant Quantum Computation

Hillary Dawkins

This thesis contains the results of research projects broadly related to the pursuit of universal fault-tolerant quantum computation. We are interested in questions such as which resources are required to achieve a quantum computational advantage, how to utilize such resources in practice, and how to characterize and control noise throughout a computation. \n \nIn part 1, we cover results pertaining to magic state distillation, one of the leading approaches to implementing universal fault-tolerant quantum computation. Early work in this area focused on determining the region of distillable states for qubit protocols, yet comparatively little is known about which states can be distilled and with what distillable region for d>2. In the first project, we focus on d=3 and present new four-qutrit distillation schemes that improve upon the known distillable region, and achieve distillation tight to the boundary of undistillable states for some classes of states. As a consequence of recent results, this implies that there is a family of quantum states that enable universality if and only if they exhibit contextuality with respect to stabilizer measurements. We also identify a new routine whose fixed point is a magic state with maximal sum-negativity i.e., it is maximally non-stabilizer in a specific sense. In the second project, we return to d=2 and present a number of interesting new distillation routines based on small codes. Many of these distill noisy states right up to the boundary of the known undististillable region, while some distill toward non-stabilizer states that have not previously been considered. \n \nIn part 2, we address the issue of noise characterization. The characterization of noise in a quantum system serves as a foundation towards meeting two important goals. Firstly, we may wish to know about specific sources of noise in order to adapt or correct errors as much as possible. Secondly, we would like a way to verify that noise is below some threshold value in order to meet the criteria of threshold theorems. We consider the case where noise is approximately known to coincide with the generalized damping channel (encompassing the common intrinsic processes of amplitude damping and dephasing), but may contain additional unknown noise sources. We provide methods to accurately obtain the noise parameters, and compare with the results of a randomized benchmarking experiment. Using this information, we show how to make meaningful statements about fault-tolerance threshold theorems by considering the diamond distance.

•Jan 12, 2017•0 citations

Fault-tolerant quantum computation with constant overhead for general noise

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

Fault-tolerant quantum computation traditionally incurs substantial resource overhead, with both qubit and time overheads scaling polylogarithmically with the size of the computation. While prior work by Gottesman showed that constant qubit overhead is achievable under stochastic noise using quantum low-density parity-check (QLDPC) codes, it has remained an open question whether similar guarantees hold under more general, non-stochastic noise models. In this work, we address this question by considering a general circuit-level noise model defined via the diamond norm, which captures both stochastic and non-stochastic noise, including coherent and amplitude damping noise. We prove that constant qubit overhead fault-tolerant quantum computation is achievable in this general setting, using QLDPC codes with constant rate and linear minimum distance. To establish our result, we develop a fault-tolerant error correction scheme and a method for implementing logic gates under general circuit noise. These results extend the theoretical foundations of fault-tolerant quantum computation and offer new directions for fault-tolerant architectures under realistic noise models.

quant-pharXiv:2512.02760•PRX Quantum•Dec 3, 2025•4 citations

Achieving fault tolerance against amplitude-damping noise

Akshaya Jayashankar, Long D. H. My, Hui Khoon Ng +1 more

With the intense interest in small, noisy quantum computing devices comes the push for larger, more accurate---and hence more useful---quantum computers. While fully fault-tolerant quantum computers are, in principle, capable of achieving arbitrarily accurate calculations using devices subjected to general noise, they require immense resources far beyond our current reach. An intermediate step would be to construct quantum computers of limited accuracy enhanced by lower-level, and hence lower-cost, noise-removal techniques. This is the motivation for our paper, which looks into fault-tolerant encoded quantum computation targeted at the dominant noise afflicting the quantum device. Specifically, we develop a protocol for fault-tolerant encoded quantum computing components in the presence of amplitude-damping noise, using a 4-qubit code and a recovery procedure tailored to such noise. We describe a universal set of fault-tolerant encoded gadgets and compute the pseudothreshold for the noise, below which our scheme leads to more accurate computation. Our paper demonstrates the possibility of applying the ideas of quantum fault tolerance to targeted noise models, generalizing the recent pursuit of biased-noise fault tolerance beyond the usual Pauli noise models. We also illustrate how certain aspects of the standard fault tolerance intuition, largely acquired through Pauli-noise considerations, can fail in the face of more general noise.

arXiv:2107.05485•Physical Review Research•Apr 11, 2022•24 citations

Aspects of Fault-Tolerant Quantum Computation

Joseph K. Iverson

This thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.

•Jun 1, 2020•2 citations

Fault-Tolerant Quantum Computation with Constant Error Rate

Dorit Aharonov, Michael Ben-Or

This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when $\eta$, the probability for an error in a qubit or a gate, is smaller than a constant threshold $\eta_c$. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate $\eta$ decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with $p>2$ states, namely, p-qudits, 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. We estimate the threshold of our construction to be $\eta_c\simeq 10^{-6}$, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that two-qubit gates are universal, together with their extensions to higher-dimensional particles. We also provide full proofs of the universality of the sets of gates we use (the proof of universality was missing in Shor's paper). This paper thus provides a self-contained and complete proof of universal fault-tolerant quantum computation in the presence of local noise.

arXiv:quant-ph/9906129•SIAM Journal on Computing•Jan 1, 2008•806 citations
We consider fault-tolerant quantum computation in the context where there are no fresh ancilla qubits available during the computation, and where the noise is due to a general quantum channel. We show that there are three classes of noisy channels: In the first, typified by the depolarizing channel, computation is only possible for a logarithmic time. In the second class, of which the dephasing channel is an example, computation is possible for polynomial time. The amplitude damping channel is an example of the third class, and for this class of channels, it is possible to compute for an exponential time in the number of qubits available.
Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small. We improve this bound and describe fault tolerant quantum computation when the error probability is smaller than some constant threshold. The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The result holds also for quantum circuits which operate on nearest neighbors only. To achieve this noise resistance, we use concatenated quantum error correcting codes. The scheme presented is general, and works with all quantum codes that satisfy some restrictions, namely that the code is ``proper''. We present two explicit classes of proper quantum codes. The first example of proper quantum codes generalizes classical secret sharing with polynomials. The second uses a known class of quantum codes and converts it to a proper code. This class is defined over a field with p elements, so the elementary quantum particle is not a qubit but a ``qupit''. With our codes, the threshold is about 10^(-6). Hopefully, this paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical.
This thesis contains the results of research projects broadly related to the pursuit of universal fault-tolerant quantum computation. We are interested in questions such as which resources are required to achieve a quantum computational advantage, how to utilize such resources in practice, and how to characterize and control noise throughout a computation. \n \nIn part 1, we cover results pertaining to magic state distillation, one of the leading approaches to implementing universal fault-tolerant quantum computation. Early work in this area focused on determining the region of distillable states for qubit protocols, yet comparatively little is known about which states can be distilled and with what distillable region for d>2. In the first project, we focus on d=3 and present new four-qutrit distillation schemes that improve upon the known distillable region, and achieve distillation tight to the boundary of undistillable states for some classes of states. As a consequence of recent results, this implies that there is a family of quantum states that enable universality if and only if they exhibit contextuality with respect to stabilizer measurements. We also identify a new routine whose fixed point is a magic state with maximal sum-negativity i.e., it is maximally non-stabilizer in a specific sense. In the second project, we return to d=2 and present a number of interesting new distillation routines based on small codes. Many of these distill noisy states right up to the boundary of the known undististillable region, while some distill toward non-stabilizer states that have not previously been considered. \n \nIn part 2, we address the issue of noise characterization. The characterization of noise in a quantum system serves as a foundation towards meeting two important goals. Firstly, we may wish to know about specific sources of noise in order to adapt or correct errors as much as possible. Secondly, we would like a way to verify that noise is below some threshold value in order to meet the criteria of threshold theorems. We consider the case where noise is approximately known to coincide with the generalized damping channel (encompassing the common intrinsic processes of amplitude damping and dephasing), but may contain additional unknown noise sources. We provide methods to accurately obtain the noise parameters, and compare with the results of a randomized benchmarking experiment. Using this information, we show how to make meaningful statements about fault-tolerance threshold theorems by considering the diamond distance.
Fault-tolerant quantum computation traditionally incurs substantial resource overhead, with both qubit and time overheads scaling polylogarithmically with the size of the computation. While prior work by Gottesman showed that constant qubit overhead is achievable under stochastic noise using quantum low-density parity-check (QLDPC) codes, it has remained an open question whether similar guarantees hold under more general, non-stochastic noise models. In this work, we address this question by considering a general circuit-level noise model defined via the diamond norm, which captures both stochastic and non-stochastic noise, including coherent and amplitude damping noise. We prove that constant qubit overhead fault-tolerant quantum computation is achievable in this general setting, using QLDPC codes with constant rate and linear minimum distance. To establish our result, we develop a fault-tolerant error correction scheme and a method for implementing logic gates under general circuit noise. These results extend the theoretical foundations of fault-tolerant quantum computation and offer new directions for fault-tolerant architectures under realistic noise models.
With the intense interest in small, noisy quantum computing devices comes the push for larger, more accurate---and hence more useful---quantum computers. While fully fault-tolerant quantum computers are, in principle, capable of achieving arbitrarily accurate calculations using devices subjected to general noise, they require immense resources far beyond our current reach. An intermediate step would be to construct quantum computers of limited accuracy enhanced by lower-level, and hence lower-cost, noise-removal techniques. This is the motivation for our paper, which looks into fault-tolerant encoded quantum computation targeted at the dominant noise afflicting the quantum device. Specifically, we develop a protocol for fault-tolerant encoded quantum computing components in the presence of amplitude-damping noise, using a 4-qubit code and a recovery procedure tailored to such noise. We describe a universal set of fault-tolerant encoded gadgets and compute the pseudothreshold for the noise, below which our scheme leads to more accurate computation. Our paper demonstrates the possibility of applying the ideas of quantum fault tolerance to targeted noise models, generalizing the recent pursuit of biased-noise fault tolerance beyond the usual Pauli noise models. We also illustrate how certain aspects of the standard fault tolerance intuition, largely acquired through Pauli-noise considerations, can fail in the face of more general noise.
This thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.
This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when η\etaη, the probability for an error in a qubit or a gate, is smaller than a constant threshold ηc\eta_cηc​. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate η\etaη decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with p>2p>2p>2 states, namely, p-qudits, 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. We estimate the threshold of our construction to be ηc≃10−6\eta_c\simeq 10^{-6}ηc​≃10−6, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that two-qubit gates are universal, together with their extensions to higher-dimensional particles. We also provide full proofs of the universality of the sets of gates we use (the proof of universality was missing in Shor's paper). This paper thus provides a self-contained and complete proof of universal fault-tolerant quantum computation in the presence of local noise.