The University of Tokyo: Protocol Achieves FTQC With Doubly-Polylog Time, Polylog Space

Researchers Yugo Takada of The University of Osaka and Hayata Yamasaki of The University of Tokyo have developed a protocol that achieves fault-tolerant quantum computation with a doubly-polylog time overhead, potentially exceeding the conventionally accepted polylogarithmic scaling of time demands. Central to this advancement is a polylog-time parallel minimum-weight perfect matching (MWPM) decoder, which scales runtime with code size and establishes theoretical guarantees for threshold existence and overhead bounds. This protocol maintains a polylog space overhead while addressing a critical bottleneck in practical implementations and the pursuit of quantum advantages. The team reports these results suggest the feasibility of surpassing the conventional polylog-time-overhead barrier, opening new possibilities in low-overhead FTQC.

While reducing both space and time overheads is critical for building practical quantum computers, minimizing runtime has proven particularly challenging; the researchers directly addressed this bottleneck with a novel approach to decoding. This decoder offers speed and provides theoretical guarantees on threshold existence and overhead bounds, ensuring the stability and efficiency of the quantum computation. The protocol integrates this decoder with a topological-code protocol featuring single-shot decoding for rapid syndrome extraction, further enhanced by concatenation with Steane codes to maintain a robust error threshold and prevent processing delays.

The pursuit of practical fault-tolerant quantum computation (FTQC) increasingly focuses on minimizing both the space and time required for error correction, a challenge that has historically seen time overheads scale according to polylogarithmic laws. The team reports this decoder achieves a parallel runtime relative to the code size, a significant improvement over existing methods. The decoder operates by efficiently extracting syndromes, indicators of errors, from the quantum system, a process integrated with a topological code protocol utilizing single-shot decoding. To bolster the system’s resilience, the researchers concatenated the protocol with Steane codes, preventing potential errors that could compromise the computation.