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

Limits of fault tolerance on resource-constrained quantum circuits for classical problems

G Uthirakalyani, Anuj Keshava Nayak, Avhishek Chatterjee, Lav R. Varshney

Published Nov 22, 2023• 2 citations
arXivHTMLPDF

Abstract

Existing lower bounds on redundancy in fault-tolerant quantum circuits are applicable when both the input and the intended output are quantum states. These bounds may not necessarily hold, however, when the intended outputs are classical bits, as in Shor's or Grover's algorithms. Here we show that, indeed, noise thresholds obtained from existing bounds do not apply to a simple fault-tolerant implementation of the quantum phase estimation algorithm where the output quantum state suffers from noise before the measurement. Then we obtain a nonasymptotic lower bound on the minimum required redundancy for fault-tolerant quantum circuits with classical inputs and outputs. Further, recent results show that, due to physical resource constraints in quantum circuits, increasing redundancy can increase noise, which in turn may render many fault-tolerance schemes useless. So it is of both practical and theoretical interest to characterize the effect of resource constraints on the fundamental limits of fault-tolerant quantum circuits. As an application of our lower bound, we characterize the fundamental limit of fault-tolerant quantum circuits with classical inputs and outputs under resource-constraint-induced noise models.

DOI
10.1103/physreva.108.052425

Related papers

Fault-Tolerant Quantum Input/Output

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

Usual scenarios of fault-tolerant computation are concerned with the fault-tolerant realization of quantum algorithms that compute classical functions, such as Shor’s algorithm for factoring. In particular, this means that input and output to the quantum algorithm are classical. In contrast to stand-alone single-core quantum computers, in many distributed scenarios, quantum information might have to be passed on from one quantum information processing system to another one, possibly via noisy quantum communication channels with noise levels above fault-tolerant thresholds. In such situations, quantum information processing devices will have quantum inputs, quantum outputs or even both, which pass qubits among each other. Working in the fault-tolerant framework of [Kitaev, 1997], we show that any quantum circuit with quantum input and output can be transformed into a fault-tolerant circuit that produces the ideal circuit with some controlled noise applied at the input and output. The framework allows the direct composition of the statements, enabling versatile future applications. We illustrate this with a concrete application, namely, communication over a noisy channel with faulty encoding and decoding operations [Christandl and Müller-Hermes, 2024]. For communication codes with linear minimum distance, we construct fault-tolerant encoders and decoders for general noise (including coherent errors). For the weaker, but standard model of local stochastic noise, we obtain fault-tolerant encoders and decoders for any communication code that can correct a constant fraction of random errors.

arXiv:2408.05260•IEEE Transactions on Information Theory•Mar 10, 2026•11 citations

Upper bounds on the noise threshold for fault-tolerant quantum computing

Julia Kempe, Oded Regev, Falk Unger +1 more

We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary $k$-qubit gates each of whose input wires is subject to depolarizing noise of strength $p$, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for $p>1-\Theta(1/\sqrt{k})$, the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of $k=2$, our bound is $p>35.7\%$. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes $29.3\%$. These bounds on $p$ are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.

arXiv:0802.1464•Quantum Information and Computation•May 1, 2010•12 citations

A Converse for Fault-tolerant Quantum Computation

G Uthirakalyani, Anuj Keshava Nayak, Avhishek Chatterjee

As techniques for fault-tolerant quantum computation keep improving, it is natural to ask: what is the fundamental lower bound on space overhead? In this paper, we obtain a lower bound on the space overhead required for ϵ -accurate implementation of a large class of operations that includes unitary operators. For the practically relevant case of sub-exponential depth and sub-linear gate size, our bound on space overhead is tighter than the known lower bounds. We obtain this bound by connecting fault-tolerant computation with a set of finite blocklength quantum communication problems whose accuracy requirements satisfy a joint constraint. The lower bound on space overhead obtained here leads to a strictly smaller upper bound on the noise threshold for noise that are not degradable. Our bound directly extends to the case where noise at the outputs of a gate are non-i.i.d. but noise across gates are i.i.d.

arXiv:2211.00697•Quantum•Aug 16, 2023•3 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

Fault-tolerant threshold of quantum circuit under correlated noise

Zhan-Yun Wang

Abstract We investigate the impact of the correlation between error gates on the fault-tolerant threshold in quantum circuits under three typical noise models. In the fault-tolerant encoding schemes for two fundamental quantum logical operations, we extend the conventional error injection method by simultaneously applying error gates to both control and target qubits after two-qubit gate operations, with a quantitative characterization of the correlation strength between these error gates. The results show that the fault-tolerant error threshold can be noticeably enhanced by the presence of correlations between error gates, resulting in more robust quantum circuit implementations. We further apply fault-tolerant encoding to the single-qubit teleportation circuit and investigate the effect of correlated noise on its error threshold. The results show that the threshold varies non-monotonically with the correlation strength and that the system’s fault-tolerance differs significantly across noise models.

Communications in Theoretical Physics•Feb 27, 2026•0 citations

A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Omar Fawzi, Alexander Müller‐Hermes, Ala Shayeghi

The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel $\mathcal{N}$ and any quantum fault tolerance schemes against $\mathrm{i.i.d.}$ noise modeled by $\mathcal{N}$, we prove a lower bound of $\max\left\{\mathrm{Q}(\mathcal{N})^{-1}n,α_\mathcal{N} \log T\right\}$ on the number of physical qubits, for circuits of length $T$ and width $n$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum capacity of $\mathcal{N}$ and $α_\mathcal{N}>0$ is a constant only depending on the channel $\mathcal{N}$. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).

arXiv:2202.00119•Leibniz international proceedings in informatics•Jan 1, 2022•11 citations
Existing lower bounds on redundancy in fault-tolerant quantum circuits are applicable when both the input and the intended output are quantum states. These bounds may not necessarily hold, however, when the intended outputs are classical bits, as in Shor's or Grover's algorithms. Here we show that, indeed, noise thresholds obtained from existing bounds do not apply to a simple fault-tolerant implementation of the quantum phase estimation algorithm where the output quantum state suffers from noise before the measurement. Then we obtain a nonasymptotic lower bound on the minimum required redundancy for fault-tolerant quantum circuits with classical inputs and outputs. Further, recent results show that, due to physical resource constraints in quantum circuits, increasing redundancy can increase noise, which in turn may render many fault-tolerance schemes useless. So it is of both practical and theoretical interest to characterize the effect of resource constraints on the fundamental limits of fault-tolerant quantum circuits. As an application of our lower bound, we characterize the fundamental limit of fault-tolerant quantum circuits with classical inputs and outputs under resource-constraint-induced noise models.
Usual scenarios of fault-tolerant computation are concerned with the fault-tolerant realization of quantum algorithms that compute classical functions, such as Shor’s algorithm for factoring. In particular, this means that input and output to the quantum algorithm are classical. In contrast to stand-alone single-core quantum computers, in many distributed scenarios, quantum information might have to be passed on from one quantum information processing system to another one, possibly via noisy quantum communication channels with noise levels above fault-tolerant thresholds. In such situations, quantum information processing devices will have quantum inputs, quantum outputs or even both, which pass qubits among each other. Working in the fault-tolerant framework of [Kitaev, 1997], we show that any quantum circuit with quantum input and output can be transformed into a fault-tolerant circuit that produces the ideal circuit with some controlled noise applied at the input and output. The framework allows the direct composition of the statements, enabling versatile future applications. We illustrate this with a concrete application, namely, communication over a noisy channel with faulty encoding and decoding operations [Christandl and Müller-Hermes, 2024]. For communication codes with linear minimum distance, we construct fault-tolerant encoders and decoders for general noise (including coherent errors). For the weaker, but standard model of local stochastic noise, we obtain fault-tolerant encoders and decoders for any communication code that can correct a constant fraction of random errors.
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary kkk-qubit gates each of whose input wires is subject to depolarizing noise of strength ppp, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1−Θ(1/k)p>1-\Theta(1/\sqrt{k})p>1−Θ(1/k​), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2k=2k=2, our bound is p>35.7%p>35.7\%p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%29.3\%29.3%. These bounds on ppp are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.
As techniques for fault-tolerant quantum computation keep improving, it is natural to ask: what is the fundamental lower bound on space overhead? In this paper, we obtain a lower bound on the space overhead required for ϵ -accurate implementation of a large class of operations that includes unitary operators. For the practically relevant case of sub-exponential depth and sub-linear gate size, our bound on space overhead is tighter than the known lower bounds. We obtain this bound by connecting fault-tolerant computation with a set of finite blocklength quantum communication problems whose accuracy requirements satisfy a joint constraint. The lower bound on space overhead obtained here leads to a strictly smaller upper bound on the noise threshold for noise that are not degradable. Our bound directly extends to the case where noise at the outputs of a gate are non-i.i.d. but noise across gates are i.i.d.
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.
Abstract We investigate the impact of the correlation between error gates on the fault-tolerant threshold in quantum circuits under three typical noise models. In the fault-tolerant encoding schemes for two fundamental quantum logical operations, we extend the conventional error injection method by simultaneously applying error gates to both control and target qubits after two-qubit gate operations, with a quantitative characterization of the correlation strength between these error gates. The results show that the fault-tolerant error threshold can be noticeably enhanced by the presence of correlations between error gates, resulting in more robust quantum circuit implementations. We further apply fault-tolerant encoding to the single-qubit teleportation circuit and investigate the effect of correlated noise on its error threshold. The results show that the threshold varies non-monotonically with the correlation strength and that the system’s fault-tolerance differs significantly across noise models.
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel N\mathcal{N}N and any quantum fault tolerance schemes against i.i.d.\mathrm{i.i.d.}i.i.d. noise modeled by N\mathcal{N}N, we prove a lower bound of max⁡{Q(N)−1n,αNlog⁡T}\max\left\{\mathrm{Q}(\mathcal{N})^{-1}n,α_\mathcal{N} \log T\right\}max{Q(N)−1n,αN​logT} on the number of physical qubits, for circuits of length TTT and width nnn. Here, Q(N)\mathrm{Q}(\mathcal{N})Q(N) denotes the quantum capacity of N\mathcal{N}N and αN>0α_\mathcal{N}>0αN​>0 is a constant only depending on the channel N\mathcal{N}N. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).