Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.28461

Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation

Zhengyi Han, Zi-Wen Liu

quant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 2 citations• Revised Sep 24, 2026 (v2)
v1 · Sep 23, 2026v2 · Sep 24, 2026
arXivHTMLPDF

Abstract

We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time factor.

AI Summary

The paper addresses whether universal fault-tolerant quantum computation can achieve constant quantum-space overhead with strictly logarithmic time overhead, removing the subpolylogarithmic factor in the previous $O(\log^{1+o(1)}(WD/\varepsilon))$ bound. For adaptive Clifford+$\mathrm{CCZ}$ circuits of width $W$, depth $D$, and target output error $\varepsilon$, the main construction uses code length $n=\Theta(\log(WD/\varepsilon))$ and achieves physical depth $O(D\log(WD/\varepsilon))$ and quantum space $O(W+F(n))$, where $\log F(n)=O(\log n\log\log n)$. Space overhead is constant when $W\ge C_FF(n)$; this holds asymptotically for polynomial depth and inverse-polynomial target error in $W$. The construction uses good quantum locally testable codes whose transversal action supplies $r=n^{\Omega(1)}$ independent logical $\mathrm{CCZ}$ gates. Code switching, reversible linear embeddings, and logical routing transfer dense logical storage into active subspaces in $O(n/r)$ batches, reusing ancillary workspace. Decoder contraction, single-shot error correction, stabilizer-resource preparation, and fault-support weight enumerators establish a constant threshold under locally stochastic noise with arbitrary supported CPTP faults. An alternative construction recursively applies a fixed Reed–Solomon magic-state distillation circuit protected at increasing code lengths, obtaining the same time bound with larger additive space. The model allows arbitrary connectivity and noiseless polynomial-size classical hardware, whose runtime—but not hardware space—is charged. Optimality, the necessity of the width condition, and overheads under noisy classical control or geometric connectivity remain unresolved.

Some signs of AI-generated textAI use disclosedStrong assumptions
The authors set the overall strategy, and generative AI tools provided substantial assistance in developing the proof details and presentation.

Central claim may not hold: The abstract's constant-space-overhead claim needs a width qualification: both constructions prove O(W) physical space only when the circuit width dominates an additive workspace depending on log(WD/epsilon), a condition not guaranteed for arbitrary widths and depths.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation — E8 Intelligence Research

Andrew Stewart Caldin

We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 11, 2026•0 citations

Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads

Quynh T. Nguyen, Christopher A. Pattison

In a model of fault-tolerant quantum computation with quick and noiseless polyloglog-time auxiliary classical computation, we construct a fault tolerance protocol with constant-space and $\widetilde{O}(\log N)$-time overhead, where $\widetilde{O}(\cdot)$ hides sub-polylog factors. Our construction utilizes constant-rate quantum locally testable codes (qLTC), new fault-tolerant gadgets on qLTCs and qLDPC codes, and a new analysis framework. In particular, 1) we develop a new simple and self-contained construction of magic state distillation for qubits using qudit quantum Reed-Solomon codes with $(\log \frac{1}{\varepsilon})^γ$ spacetime overhead, where $γ\rightarrow 0$. 2) We prove that the recent family of almost-good qLTCs of Dinur-Lin-Vidick admit parallel single-shot decoders against adversarial errors of weight scaling with the code distance. 3) We develop logical state preparation and logical gate procedures with $\widetilde{O}(1)$-spacetime overhead on qLTCs. 4) To combine these ingredients, we introduce a new framework of fault tolerance analysis called the weight enumerator formalism. The framework permits easy formal composition of fault-tolerant gadgets, so we expect it to be of independent interest. Our work gives the lowest spacetime overhead to date, which, for the first time, matches that of classical fault tolerance up to sub-polylog factors. We conjecture this is optimal up to sub-polylog factors.

arXiv:2411.03632•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•37 citations

Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes

Ali Lavasani, Guanyu Zhu, Maissam Barkeshli

A basic question in the theory of fault-tolerant quantum computation is to understand the fundamental resource costs for performing a universal logical set of gates on encoded qubits to arbitrary accuracy. Here we consider qubits encoded with constant space overhead (i.e. finite encoding rate) in the limit of arbitrarily large code distance d through the use of topological codes associated to triangulations of hyperbolic surfaces. We introduce explicit protocols to demonstrate how Dehn twists of the hyperbolic surface can be implemented on the code through constant depth unitary circuits, without increasing the space overhead. The circuit for a given Dehn twist consists of a permutation of physical qubits, followed by a constant depth local unitary circuit, where locality here is defined with respect to a hyperbolic metric that defines the code. Applying our results to the hyperbolic Fibonacci Turaev-Viro code implies the possibility of applying universal logical gate sets on encoded qubits through constant depth unitary circuits and with constant space overhead. Our circuits are inherently protected from errors as they map local operators to local operators while changing the size of their support by at most a constant factor; in the presence of noisy syndrome measurements, our results suggest the possibility of universal fault tolerant quantum computation with constant space overhead and time overhead of O(d/log⁡d) . For quantum circuits that allow parallel gate operations, this yields the optimal scaling of space-time overhead known to date.

arXiv:1901.11029•Quantum•Aug 26, 2019•42 citations

Constant-Overhead Addressable Gates via Single-Shot Code Switching

Louis Golowich, Kathleen Chang, Guanyu Zhu

It is a major challenge to perform addressable and parallel logical operations on constant-rate quantum LDPC (qLDPC) codes. Indeed, the overhead of targeting specific logical qubits represents a crucial bottleneck in many quantum fault-tolerance schemes. We introduce fault-tolerant protocols for performing various addressable as well as parallel logical operations with constant space-time overhead, on a family of constant-rate and polynomial-distance qLDPC codes. Specifically, we construct gadgets for a large class of permutations of logical qubits. We apply these logical permutations to construct gadgets for applying a targeted Hadamard (or $CNOT$) gate on any chosen logical qubit (pair). We also construct gadgets for preparing logical code states, and for applying Hadamard gates on all logical qubits in a codeblock. All of our gadgets use constant quantum space-time overhead along with polynomially bounded classical computation. Prior protocols for such operations required larger overhead, or else relied on codes with certain symmetries that lack known asymptotic constructions. Our codes are given by tensor products of classical codes constructed from lossless expander graphs. Our core technical contribution is a constant-overhead code-switching procedure between 2- and 3-dimensional product codes, which generalizes Bombin's dimensional jump (arXiv:1412.5079). We prove that all of our gadgets exhibit a constant threshold under locally stochastic noise. Along the way, we develop a small-set flip decoder for high-dimensional product codes from lossless expanders. Our techniques yield additional interesting consequences, such as single-shot state preparation of 2-dimensional product codes with constant space-time overhead. We also propose a method for performing parallel non-Clifford gates by extending our techniques to codes supporting transversal application of such gates.

arXiv:2510.06760•Oct 8, 2025•22 citations

Fault-tolerant interfaces for quantum LDPC codes

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

The preparation of a quantum state using a noisy quantum computer (gate noise strength $δ$) will necessarily affect an O($δ$)-fraction of the qubits, no matter which protocol is used. Here, we show that fault-tolerant quantum state preparation can be achieved with constant space overhead improving on previous constructions requiring polylogarithmic overhead. To achieve this, we add to the toolbox of fault-tolerant schemes for circuits with quantum input and output. More specifically, we construct fault-tolerant interfaces that decrease the level of protection for quantum low-density parity-check (LDPC) codes. When information is encoded in multiple code blocks, our interfaces have constant space overhead. In our decoder construction that change the level of protection by an arbitrary amount, we circumvent bottlenecks to error pileup and overhead by gradual lowering of the level of encoding at the same time as we increase the number of blocks on which decoding is carried out simultaneously.

quant-pharXiv:2602.16948•Feb 20, 2026•1 citation

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

Kishor Bharti, Tobias Haug, Andrew Tanggara

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.

quant-pharXiv:2608.26272•Aug 28, 2026•2 citations
We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical \CCZ\CCZ\CCZ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical \CCZ\CCZ\CCZ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time factor.
The paper addresses whether universal fault-tolerant quantum computation can achieve constant quantum-space overhead with strictly logarithmic time overhead, removing the subpolylogarithmic factor in the previous O(log⁡1+o(1)(WD/ε))O(\log^{1+o(1)}(WD/\varepsilon))O(log1+o(1)(WD/ε)) bound.
For adaptive Clifford+CCZ\mathrm{CCZ}CCZ circuits of width WWW, depth DDD, and target output error ε\varepsilonε, the main construction uses code length n=Θ(log⁡(WD/ε))n=\Theta(\log(WD/\varepsilon))n=Θ(log(WD/ε)) and achieves physical depth O(Dlog⁡(WD/ε))O(D\log(WD/\varepsilon))O(Dlog(WD/ε)) and quantum space O(W+F(n))O(W+F(n))O(W+F(n)), where log⁡F(n)=O(log⁡nlog⁡log⁡n)\log F(n)=O(\log n\log\log n)logF(n)=O(lognloglogn). Space overhead is constant when W≥CFF(n)W\ge C_FF(n)W≥CF​F(n); this holds asymptotically for polynomial depth and inverse-polynomial target error in WWW.
The construction uses good quantum locally testable codes whose transversal action supplies r=nΩ(1)r=n^{\Omega(1)}r=nΩ(1) independent logical CCZ\mathrm{CCZ}CCZ gates. Code switching, reversible linear embeddings, and logical routing transfer dense logical storage into active subspaces in O(n/r)O(n/r)O(n/r) batches, reusing ancillary workspace. Decoder contraction, single-shot error correction, stabilizer-resource preparation, and fault-support weight enumerators establish a constant threshold under locally stochastic noise with arbitrary supported CPTP faults. An alternative construction recursively applies a fixed Reed–Solomon magic-state distillation circuit protected at increasing code lengths, obtaining the same time bound with larger additive space.
The model allows arbitrary connectivity and noiseless polynomial-size classical hardware, whose runtime—but not hardware space—is charged. Optimality, the necessity of the width condition, and overheads under noisy classical control or geometric connectivity remain unresolved.
We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
In a model of fault-tolerant quantum computation with quick and noiseless polyloglog-time auxiliary classical computation, we construct a fault tolerance protocol with constant-space and O~(log⁡N)\widetilde{O}(\log N)O(logN)-time overhead, where O~(⋅)\widetilde{O}(\cdot)O(⋅) hides sub-polylog factors. Our construction utilizes constant-rate quantum locally testable codes (qLTC), new fault-tolerant gadgets on qLTCs and qLDPC codes, and a new analysis framework. In particular, 1) we develop a new simple and self-contained construction of magic state distillation for qubits using qudit quantum Reed-Solomon codes with (log⁡1ε)γ(\log \frac{1}{\varepsilon})^γ(logε1​)γ spacetime overhead, where γ→0γ\rightarrow 0γ→0. 2) We prove that the recent family of almost-good qLTCs of Dinur-Lin-Vidick admit parallel single-shot decoders against adversarial errors of weight scaling with the code distance. 3) We develop logical state preparation and logical gate procedures with O~(1)\widetilde{O}(1)O(1)-spacetime overhead on qLTCs. 4) To combine these ingredients, we introduce a new framework of fault tolerance analysis called the weight enumerator formalism. The framework permits easy formal composition of fault-tolerant gadgets, so we expect it to be of independent interest. Our work gives the lowest spacetime overhead to date, which, for the first time, matches that of classical fault tolerance up to sub-polylog factors. We conjecture this is optimal up to sub-polylog factors.
A basic question in the theory of fault-tolerant quantum computation is to understand the fundamental resource costs for performing a universal logical set of gates on encoded qubits to arbitrary accuracy. Here we consider qubits encoded with constant space overhead (i.e. finite encoding rate) in the limit of arbitrarily large code distance d through the use of topological codes associated to triangulations of hyperbolic surfaces. We introduce explicit protocols to demonstrate how Dehn twists of the hyperbolic surface can be implemented on the code through constant depth unitary circuits, without increasing the space overhead. The circuit for a given Dehn twist consists of a permutation of physical qubits, followed by a constant depth local unitary circuit, where locality here is defined with respect to a hyperbolic metric that defines the code. Applying our results to the hyperbolic Fibonacci Turaev-Viro code implies the possibility of applying universal logical gate sets on encoded qubits through constant depth unitary circuits and with constant space overhead. Our circuits are inherently protected from errors as they map local operators to local operators while changing the size of their support by at most a constant factor; in the presence of noisy syndrome measurements, our results suggest the possibility of universal fault tolerant quantum computation with constant space overhead and time overhead of O(d/log⁡d) . For quantum circuits that allow parallel gate operations, this yields the optimal scaling of space-time overhead known to date.
It is a major challenge to perform addressable and parallel logical operations on constant-rate quantum LDPC (qLDPC) codes. Indeed, the overhead of targeting specific logical qubits represents a crucial bottleneck in many quantum fault-tolerance schemes. We introduce fault-tolerant protocols for performing various addressable as well as parallel logical operations with constant space-time overhead, on a family of constant-rate and polynomial-distance qLDPC codes. Specifically, we construct gadgets for a large class of permutations of logical qubits. We apply these logical permutations to construct gadgets for applying a targeted Hadamard (or CNOTCNOTCNOT) gate on any chosen logical qubit (pair). We also construct gadgets for preparing logical code states, and for applying Hadamard gates on all logical qubits in a codeblock. All of our gadgets use constant quantum space-time overhead along with polynomially bounded classical computation. Prior protocols for such operations required larger overhead, or else relied on codes with certain symmetries that lack known asymptotic constructions. Our codes are given by tensor products of classical codes constructed from lossless expander graphs. Our core technical contribution is a constant-overhead code-switching procedure between 2- and 3-dimensional product codes, which generalizes Bombin's dimensional jump (arXiv:1412.5079). We prove that all of our gadgets exhibit a constant threshold under locally stochastic noise. Along the way, we develop a small-set flip decoder for high-dimensional product codes from lossless expanders. Our techniques yield additional interesting consequences, such as single-shot state preparation of 2-dimensional product codes with constant space-time overhead. We also propose a method for performing parallel non-Clifford gates by extending our techniques to codes supporting transversal application of such gates.
The preparation of a quantum state using a noisy quantum computer (gate noise strength δδδ) will necessarily affect an O(δδδ)-fraction of the qubits, no matter which protocol is used. Here, we show that fault-tolerant quantum state preparation can be achieved with constant space overhead improving on previous constructions requiring polylogarithmic overhead. To achieve this, we add to the toolbox of fault-tolerant schemes for circuits with quantum input and output. More specifically, we construct fault-tolerant interfaces that decrease the level of protection for quantum low-density parity-check (LDPC) codes. When information is encoded in multiple code blocks, our interfaces have constant space overhead. In our decoder construction that change the level of protection by an arbitrary amount, we circumvent bottlenecks to error pileup and overhead by gradual lowering of the level of encoding at the same time as we increase the number of blocks on which decoding is carried out simultaneously.
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.