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:0810.4953 · Physical Review A

Fault-tolerant quantum computation versus Gaussian noise

Hui Khoon Ng, John P. Preskill

Published Mar 16, 2009• 63 citations
arXivHTMLPDF

Abstract

We study the robustness of a fault-tolerant quantum computer subject to Gaussian non-Markovian quantum noise, and we show that scalable quantum computation is possible if the noise power spectrum satisfies an appropriate ``threshold condition.'' Our condition is less sensitive to very-high-frequency noise than previously derived threshold conditions for non-Markovian noise.

DOI
10.1103/physreva.79.032318

Related papers

Fault-tolerant quantum computation for local non-Markovian noise

Barbara M. Terhal, Guido Burkard

We derive a threshold result for fault-tolerant quantum computation for local non-Markovian noise models. The role of error amplitude in our analysis is played by the product of the elementary gate time ${t}_{0}$ and the spectral width of the interaction Hamiltonian between system and bath. We discuss extensions of our model and the applicability of our analysis.

arXiv:quant-ph/0402104•Physical Review A•Jan 31, 2005•180 citations

Fault-Tolerant Quantum Computation with Long-Range Correlated Noise

Dorit Aharonov, Alexei Kitaev, John P. Preskill

We prove a new version of the quantum accuracy threshold theorem that applies to non-Markovian noise with algebraically decaying spatial correlations. We consider noise in a quantum computer arising from a perturbation that acts collectively on pairs of qubits and on the environment, and we show that an arbitrarily long quantum computation can be executed with high reliability in D spatial dimensions, if the perturbation is sufficiently weak and decays with the distance r between the qubits faster than 1/r(D).

arXiv:quant-ph/0510231•Physical Review Letters•Feb 7, 2006•243 citations

Fault-Tolerant Quantum Computation with Adversarial Errors

Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani

We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we construct a fault-tolerant circuit on $N=\text{poly}(\bar{N})$ physical qudits of depth $\bar{T}\cdot\bar{N}^{o(1)}$, which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number $N^{1-o(1)}$ of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.

quant-pharXiv:2608.16857•Aug 18, 2026•0 citations

Comments on "Fault-Tolerant Quantum Computation for Local Non-Markovian Noise"

Robert Alicki

In the recent paper Terhal and Burkard derived a threshold result for fault-tolerant quantum computation under the assumption of the non-Markovian noise and claimed to rebut the objections rised by Alicki and Horodecki's. The purpose of this note is to show that the main condition used by Terhal and Burkard, although looking quite innocently, implies the assumption of the extremally low probability error per single quantum gate - p < 10^{-8} - 10^{-12} - i.e. the square of the expected threshold value for the case of Markovian noise.

arXiv:quant-ph/0402139•Feb 19, 2004•7 citations

Sufficient condition on noise correlations for scalable quantum computing

PreskillJohn

I study the effectiveness of fault-tolerant quantum computation against correlated Hamiltonian noise, and derive a sufficient condition for scalability. Arbitrarily long quantum computations can be...

Quantum Information and Computation•Mar 1, 2013•0 citations

QuEST: Robust Quantum Gadgets

Aram W. Harrow

Abstract : That quantum computation is a realistic model of computation rests heavily upon the legs of the threshold theorem for fault-tolerant quantum computation. This theorem tells us roughly that, if noise is weak enough and quantum control is strong enough, then robust quantum computation is possible with the added overhead of using more qubits and more time spent performing quantum gates. These added resources scale efficiently with the desired accuracy of the quantum computation and yet, because a theorem is not a technology, the quantum computing community is technically far from achieving the break-even point for these methods. Here we propose revolutionary ideas in fault-tolerant quantum computing which will jump-start the building of a quantum computer. Among the threads in our approach are the construction of small scale gadgets for energetic protection of quantum information, the construction of novel and robust perturbation theory gadgets, the construction of scalable stabilizer Hamiltonians, and methods for achieving the fault-tolerant adiabatic quantum computation.

•Feb 28, 2013•0 citations
We study the robustness of a fault-tolerant quantum computer subject to Gaussian non-Markovian quantum noise, and we show that scalable quantum computation is possible if the noise power spectrum satisfies an appropriate ``threshold condition.'' Our condition is less sensitive to very-high-frequency noise than previously derived threshold conditions for non-Markovian noise.
We derive a threshold result for fault-tolerant quantum computation for local non-Markovian noise models. The role of error amplitude in our analysis is played by the product of the elementary gate time t0{t}_{0}t0​ and the spectral width of the interaction Hamiltonian between system and bath. We discuss extensions of our model and the applicability of our analysis.
We prove a new version of the quantum accuracy threshold theorem that applies to non-Markovian noise with algebraically decaying spatial correlations. We consider noise in a quantum computer arising from a perturbation that acts collectively on pairs of qubits and on the environment, and we show that an arbitrarily long quantum computation can be executed with high reliability in D spatial dimensions, if the perturbation is sufficiently weak and decays with the distance r between the qubits faster than 1/r(D).
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on Nˉ\bar{N}Nˉ logical qudits of depth Tˉ\bar{T}Tˉ, we construct a fault-tolerant circuit on N=poly(Nˉ)N=\text{poly}(\bar{N})N=poly(Nˉ) physical qudits of depth Tˉ⋅Nˉo(1)\bar{T}\cdot\bar{N}^{o(1)}Tˉ⋅Nˉo(1), which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number N1−o(1)N^{1-o(1)}N1−o(1) of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.
In the recent paper Terhal and Burkard derived a threshold result for fault-tolerant quantum computation under the assumption of the non-Markovian noise and claimed to rebut the objections rised by Alicki and Horodecki's. The purpose of this note is to show that the main condition used by Terhal and Burkard, although looking quite innocently, implies the assumption of the extremally low probability error per single quantum gate - p < 10^{-8} - 10^{-12} - i.e. the square of the expected threshold value for the case of Markovian noise.
Abstract : That quantum computation is a realistic model of computation rests heavily upon the legs of the threshold theorem for fault-tolerant quantum computation. This theorem tells us roughly that, if noise is weak enough and quantum control is strong enough, then robust quantum computation is possible with the added overhead of using more qubits and more time spent performing quantum gates. These added resources scale efficiently with the desired accuracy of the quantum computation and yet, because a theorem is not a technology, the quantum computing community is technically far from achieving the break-even point for these methods. Here we propose revolutionary ideas in fault-tolerant quantum computing which will jump-start the building of a quantum computer. Among the threads in our approach are the construction of small scale gadgets for energetic protection of quantum information, the construction of novel and robust perturbation theory gadgets, the construction of scalable stabilizer Hamiltonians, and methods for achieving the fault-tolerant adiabatic quantum computation.