Curator's Take
AI Commentary
This article settles a long‑standing open question by proving that even under idealised noise and fully adaptive error‑correction protocols, fault‑tolerant quantum computing must incur at least a logarithmic spacetime overhead, ruling out truly constant‑cost schemes. By constructing a positive‑rate CSS code that meets the bound and showing how the extra cost can be amortised across many logical qubits, the work bridges recent polylogarithmic overhead improvements with realistic resource estimates for large algorithms such as Shor’s. The result gives hardware designers and algorithm developers a firm lower‑limit to target, while reminding the community that constant‑overhead fault tolerance remains impossible without fundamentally new error models or architectures.
— Mark Eatherly
Summary
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.