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.
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.
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 and any quantum fault tolerance schemes against i.i.d. noise modeled by N, we prove a lower bound of max{Q(N)−1n,αNlogT} on the number of physical qubits, for circuits of length T and width n. Here, Q(N) denotes the quantum capacity of N and αN>0 is a constant only depending on the channel 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).
Rigorously establishing that the error in an experimental quantum operation is beneath the threshold for fault-tolerant quantum computation currently requires considering the worst-case error, which can be orders of magnitude smaller than the average gate infidelities routinely reported in experiments. We show that an improved bound on the worst-case error can be obtained by also considering the recently-introduced unitarity of the noise where the upper and lower bounds differ by a factor of ≈2.45 for unital qubit channels. We prove that the contribution from the nonunital part of any noise map is at most on the order of the average gate infidelity and so is negligible relative to any coherent contribution. We also show that the "average" error rate when measurements are not restricted to an eigenbasis containing the state of the system exhibits the same scaling as the worst-case error, which, for coherent noise, is the square-root of the infidelity. We also obtain improved bounds for the diamond distance when the noise map is known (or approximately known).
The threshold theorem states that quantum computations can be made reliable below a physical error threshold, at the cost of additional physical qubits and circuit depth. Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings, but whether the cumulative spacetime overhead can be constant has remained unclear. Here, we show that even for the simplest task of preserving quantum information in a quantum memory, under an optimistic noise model and allowing general adaptive protocols, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead. This additional cost can nevertheless be shared among many logical qubits, so sufficiently wide computations, including standard implementations of Shor's algorithm, may still achieve constant relative overhead. We further give a positive-rate CSS code construction that attains the memory bound, identify sufficient conditions under which the same scaling extends from quantum memory to fault-tolerant circuit implementations, and derive circuit-size bounds for subsystem spacetime codes. Our work establishes fundamental limits on the resources required for quantum fault tolerance.
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.
Abstract Scaling up quantum computers to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation demand excessive space overheads by using many physical qubits for each logical qubit. A more recent protocol using quantum analogues of low-density parity-check codes needs only a constant space overhead that does not grow with the number of logical qubits. However, the overhead in the processing time required to implement this protocol grows polynomially with the number of computational steps. To address these problems, here we introduce an alternative approach to constant-space-overhead fault-tolerant quantum computing using a concatenation of multiple small-size quantum codes rather than a single large-size quantum low-density parity-check code. We develop techniques for concatenating different quantum Hamming codes with growing size. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol is fault tolerant even if a decoder has a non-constant runtime, unlike the existing constant-space-overhead protocol. This code concatenation approach will make possible a large class of quantum speedups with feasibly bounded space overhead yet negligibly short time overhead.
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.