Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead

• URL: http://arxiv.org/abs/2608.26272v1
• Date: Wed, 26 Aug 2026 18:00:25 GMT
• Title: Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead
• Abstract summary: threshold theorem states that quantum computations can be made reliable below a physical error threshold.<n>Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings.<n>We show that even for the simplest task of preserving quantum information in a quantum memory, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead.
• Score: 0.4750231394252795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Fidelity bounds for adiabatic gates and other quantum operations with time-dependent dissipation [0.0]
  As quantum-computing platforms are susceptible to noise, the fidelity of quantum operations is limited by decoherence.<n>We show that flux-dependent noise sensitivity, combined with qubit-coupler hybridization, significantly reduces the fidelity of adiabatic controlled-Z gates in superconducting quantum computers.
  arXiv  Detail & Related papers  (2026-06-18T17:15:19Z)
• Asymptotic Limits of Entanglement Distribution [43.748379918040854]
  We investigate the limits of entanglement distribution across quantum networks utilizing intermediate stations and local operations.<n>We establish a strict dichotomy: the preservation of entanglement over arbitrarily long distances is possible if the underlying quantum channel admits a correctable subspace.<n>We derive a fundamental lower bound on the physical resource requirements, proving that for channels without a correctable subspace, the number of parallel channels per link must scale at least logarithmically with the number of intermediate stations to sustain a non-zero amount of entanglement.
  arXiv  Detail & Related papers  (2026-05-22T09:56:38Z)
• Quantum reservoir computing induced by controllable damping [0.9374652839580183]
  We propose an algorithm for inducing damping by applying a controlled rotation to each qubit in a quantum reservoir.<n>It enables tunable, circuit-level amplitude amplification of the zero state.<n>We show that quantum correlations between qubits provide an improvement in terms of memory retention.
  arXiv  Detail & Related papers  (2025-08-20T11:18:57Z)
• Measurement-Based Long-Range Entangling Gates in Constant Depth [0.46040036610482665]
  We show how to reduce the depth of quantum sub-routines to a constant depth using mid-circuit measurements and feed-forward operations. We verify the feasibility by implementing the measurement-based quantum fan-out gate and long-range CNOT gate on real quantum hardware.
  arXiv  Detail & Related papers  (2024-08-06T09:35:42Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation [2.3020018305241337]
  Protocols for fault-tolerant quantum computation demand excessive space overheads.<n>We introduce an alternative approach to constant-space-overhead fault-tolerant quantum computing.<n>Our protocol is fault tolerant even if a decoder has a non-constant runtime.
  arXiv  Detail & Related papers  (2022-07-18T18:00:00Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  We provide the first complete characterization of sources of error in a neutral-atom quantum computer. We develop a novel and distinctly efficient method to address the most important errors associated with the decay of atomic qubits to states outside of the computational subspace. Our protocols can be implemented in the near-term using state-of-the-art neutral atom platforms with qubits encoded in both alkali and alkaline-earth atoms.
  arXiv  Detail & Related papers  (2021-05-27T23:29:53Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Eliminating Intermediate Measurements in Space-Bounded Quantum Computation [0.0]
  We show that it is possible to defer measurements to the end of a quantum computation without increasing the number of ancillary qubits. A key component of our approach involves showing that the well-conditioned versions of many standard linear-algebraic problems may be solved by a quantum computer in less space than seems possible by a classical computer.
  arXiv  Detail & Related papers  (2020-06-05T16:05:49Z)
• Efficient simulatability of continuous-variable circuits with large Wigner negativity [62.997667081978825]
  Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures. We identify vast families of circuits that display large, possibly unbounded, Wigner negativity, and yet are classically efficiently simulatable. We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.
  arXiv  Detail & Related papers  (2020-05-25T11:03:42Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.