A quantum computer is a powerful machine that provides a new approach to information processing based on quantum mechanics. However, basically, qubits are very vulnerable to errors, thus a quantum error correction code (QECC) is needed to build a reliable quantum computer. Moreover, simply using QECCs is not sufficient in order that a quantum computer can tolerate errors. In quantum computation, each operation must be performed on the encoded states. Even when the gates used to perform these operations are noisy, the quantum computation must be tolerable to the errors. This is called fault-tolerant quantum computation and it is an essential condition for implementing a quantum computer. However, considering the fault tolerance, the overhead of the quantum computer increases exponentially. In this paper, we introduce fault-tolerant quantum computation and schemes to reduce the its overhead.
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.
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).