Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation
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.
Related
- Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
- Taming Spacetime Overhead and Design Complexity in Distributed Fault-Tolerant Superconducting Quantum Computation
- Reducing the Entanglement Cost of Distributed Bipartite Quantum Computation with Constant Qubit Overhead
- Quantum circuit compilation with constant overhead
- Need One Bell-pair Only (NOBOL) for Low-Overhead Fault-Tolerant Quantum Computing
BibTeX
@misc{han2026purelylogarithmictime,
title = {{Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation}},
author = {Zhengyi Han and Zi-Wen Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28461},
eprint = {2609.28461},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28461},
}
RIS
TY - UNPB
TI - Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation
AU - Zhengyi Han
AU - Zi-Wen Liu
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.28461
UR - https://arxiv.org/abs/2609.28461
AB - 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.
ER -