Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
- 1Graduate School of Engineering Science, The University of Osaka
- 2Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
Abstract
Reducing space and time overheads of fault-tolerant quantum computation (FTQC) has received increasing attention as it is crucial for the development of quantum computers and plays a fundamental role in understanding the feasibility and limitations of realizing quantum advantages. Shorter time overheads are particularly essential for demonstrating quantum computational speedups without compromising runtime advantages. However, surpassing the conventional polylogarithmic (polylog) scaling of time overheads has remained a significant challenge, since it requires addressing all potential bottlenecks, including the nonzero runtime of classical computation for decoding in practical implementations. In this work, we construct a protocol that achieves FTQC with doubly polylog time overhead while maintaining the conventional polylog space overhead. The key to our approach is the development of a highly parallelizable minimum-weight perfect matching (MWPM) decoder, which achieves a polylog parallel runtime in the code size while providing theoretical guarantees on threshold existence and overhead bounds. Our protocol integrates this decoder with a topological-code protocol that incorporates single-shot decoding for efficient syndrome extraction; furthermore, we concatenate this with the concatenated Steane codes to guarantee the threshold while avoiding a backlog problem. These results suggest the feasibility of surpassing the conventional polylog-time-overhead barrier, opening a new frontier in low-overhead FTQC.
Related
- Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation
- Taming Spacetime Overhead and Design Complexity in Distributed Fault-Tolerant Superconducting Quantum Computation
- Planar fault-tolerant logical measurements with low qubit overhead
- Need One Bell-pair Only (NOBOL) for Low-Overhead Fault-Tolerant Quantum Computing
- Reducing the Entanglement Cost of Distributed Bipartite Quantum Computation with Constant Qubit Overhead
BibTeX
@article{takada2026doublypolylogtimeoverhead,
title = {{Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder}},
author = {Yugo Takada and Hayata Yamasaki},
journal = {npj Quantum Information},
year = {2026},
month = jul,
doi = {10.1038/s41534-026-01312-0},
url = {https://doi.org/10.1038/s41534-026-01312-0},
note = {CC BY},
}
RIS
TY - JOUR
TI - Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
AU - Yugo Takada
AU - Hayata Yamasaki
PY - 2026
DA - 2026/07/01
JO - npj Quantum Information
DO - 10.1038/s41534-026-01312-0
UR - https://doi.org/10.1038/s41534-026-01312-0
AB - Reducing space and time overheads of fault-tolerant quantum computation (FTQC) has received increasing attention as it is crucial for the development of quantum computers and plays a fundamental role in understanding the feasibility and limitations of realizing quantum advantages. Shorter time overheads are particularly essential for demonstrating quantum computational speedups without compromising runtime advantages. However, surpassing the conventional polylogarithmic (polylog) scaling of time overheads has remained a significant challenge, since it requires addressing all potential bottlenecks, including the nonzero runtime of classical computation for decoding in practical implementations. In this work, we construct a protocol that achieves FTQC with doubly polylog time overhead while maintaining the conventional polylog space overhead. The key to our approach is the development of a highly parallelizable minimum-weight perfect matching (MWPM) decoder, which achieves a polylog parallel runtime in the code size while providing theoretical guarantees on threshold existence and overhead bounds. Our protocol integrates this decoder with a topological-code protocol that incorporates single-shot decoding for efficient syndrome extraction; furthermore, we concatenate this with the concatenated Steane codes to guarantee the threshold while avoiding a backlog problem. These results suggest the feasibility of surpassing the conventional polylog-time-overhead barrier, opening a new frontier in low-overhead FTQC.
SN - 2056-6387
ER -