  We prove that quantum expander codes can be combined with quantum
fault-tolerance techniques to achieve constant overhead: the ratio between the
total number of physical qubits required for a quantum computation with faulty
hardware and the number of logical qubits involved in the ideal computation is
asymptotically constant, and can even be taken arbitrarily close to 1 in the
limit of small physical error rate. This improves on the polylogarithmic
overhead promised by the standard threshold theorem.
  To achieve this, we exploit a framework introduced by Gottesman together with
a family of constant rate quantum codes, quantum expander codes. Our main
technical contribution is to analyze an efficient decoding algorithm for these
codes and prove that it remains robust in the presence of noisy syndrome
measurements, a property which is crucial for fault-tolerant circuits. We also
establish two additional features of the decoding algorithm that make it
attractive for quantum computation: it can be parallelized to run in
logarithmic depth, and is single-shot, meaning that it only requires a single
round of noisy syndrome measurement.
