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.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/0402104Physical Review AJan 31, 2005180 citations

Fault-tolerant quantum computation with local interactions

Ashley M. Stephens

Jan 1, 20090 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.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/0402139Feb 19, 20047 citations

Fault-tolerant quantum computation for local leakage faults

Panos Aliferis, Barbara M. Terhal

We provide a rigorous analysis of fault-tolerant quantum computation in the presence of local leakage faults. We show that one can systematically deal with leakage by using appropriate leakage-reduction units such as quantum teleportation. The leakage noise is described microscopically, by Hamiltonian couplings, and the noise is treated coherently, similar to general non-Markovian noise analyzed in Refs. \cite{Terhal04} and \cite{Aliferis05b}. We describe ways to limit the use of leakage-reduction units while keeping the quantum circuits fault-tolerant and we also discuss how leakage reduction by teleportation is naturally achieved in measurement-based computation.We provide a rigorous analysis of fault-tolerant quantum computation in the presence of local leakage faults. We show that one can systematically deal with leakage by using appropriate leakage-reduction units such as quantum teleportation. The leakage noise is described microscopically, by Hamiltonian couplings, and the noise is treated coherently, similar to general non-Markovian noise analyzed in Refs. \cite{Terhal04} and \cite{Aliferis05b}. We describe ways to limit the use of leakage-reduction units while keeping the quantum circuits fault-tolerant and we also discuss how leakage reduction by teleportation is naturally achieved in measurement-based computation.

Quantum Information and ComputationJan 1, 200748 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.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.16857Aug 18, 20260 citations

{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.

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.