The threshold theorem is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a faulty quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices. In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation. On a technical level, our main contribution is the analysis of the SMALL-SET-FLIP decoding algorithm applied to the family of quantum expander codes. We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the BIT-FLIP algorithm applied to the (classical) expander codes of Sipser and Spielman. Quantum computers are expected to offer significant, sometimes exponential, speedups compared to classical computers.

Two researchers at Université de Sherbrooke, in Canada, have recently developed and trained neural belief-propagation (BP) decoders for quantum low-density parity-check (LDPC) codes. Their study, outlined in a paper published in Physical Review Letters, suggests that training can enhance the performance of BP decoders significantly, helping to solve issues that are commonly associated with their application in quantum research. "Ten years ago, I wrote an article with Yeojin Chung explaining how standard decoding algorithms for LDPC codes, which are broadly used in classical communication, would fail in the quantum setting," David Poulin, one of the researchers who carried out the study, told Phys.org. "This problem has been obsessing me ever since. Recently, people have started to investigate the use of neural networks to decode quantum codes, but they all focused on a problem (decoding topological codes) that already had a number of good human-designed solutions. This was the perfect occasion to revisit my favorite open problem and use neural networks to decode quantum codes that had no previously known decoder."