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.
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.
Fault-tolerant quantum computation (FTQC) requires fast and accurate decoding of quantum errors, which is often formulated as a minimum-weight perfect matching (MWPM) problem. A determinant-based approach has been proposed as a novel method to surpass the conventional polynomial runtime of MWPM decoding via the blossom algorithm, asymptotically achieving polylogarithmic parallel runtime. However, the existing approach requires an impractically large bit length to represent intermediate values during the computation of the matrix determinant; moreover, when implemented on a finite-bit machine, the algorithm cannot detect overflow, and therefore, the mathematical correctness of such algorithms cannot be guaranteed. In this work, we address these issues by presenting a polylog-time MWPM decoder that detects overflow in finite-bit representations by employing an algebraic framework over a truncated polynomial ring. Within this framework, all arithmetic operations are implemented using bitwise XOR and shift operations, enabling efficient and hardware-friendly implementation. Furthermore, with algorithmic optimizations tailored to the structure of the determinant-based approach, we reduce the arithmetic bit length required to represent intermediate values in the determinant computation by more than 99.9%, making it possible to implement it on machines supporting 512-bit computing while preserving the decoder's polylog runtime scaling. These results open the possibility of a proof-of-principle demonstration of the polylog-time MWPM decoding in the early FTQC regime.
Abstract Scalable realization of quantum computing to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation (FTQC) demand excessive space overhead of physical qubits per logical qubit. A more recent protocol to achieve constant-space-overhead FTQC using quantum low-density parity-check (LDPC) codes thus attracts considerable attention but suffers from another drawback: it incurs polynomially long time overhead. To address these problems, we here introduce an alternative approach using a concatenation of multiple small-size quantum codes for the constant-space-overhead FTQC rather than a single large-size quantum LDPC code. We develop techniques for concatenating different quantum Hamming codes with growing sizes. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol accomplishes FTQC even if a decoder has non-constant runtime, unlike the existing constant-space-overhead protocol. These results establish a foundation for FTQC realizing a large class of quantum speedups within feasibly bounded space overhead yet negligibly short time overhead. This achievement opens a promising avenue for the low-overhead FTQC based on code concatenation.
Sparse-Blossom Decoding in o(1) Time
Matching-based decoding is widely used in quantum error correction, and accelerating it is key to enabling fast and scalable fault-tolerant quantum computation. Minimum-weight perfect matching (MWPM) decoding provides rigorous guarantees for error suppression, while sparse blossom enables its practical implementation at modest problem sizes. However, the runtime of existing sparse-blossom implementations unavoidably increases with problem size, motivating a rigorous parallelization framework that guarantees correctness and a runtime shorter than the syndrome-extraction timescale. Here, we present such a framework and prove that the resulting parallel sparse-blossom algorithm produces the same correction as the original, non-parallel sparse blossom. For the rotated surface code with code distance d and physical error rates below a finite threshold, we prove that the average parallel runtime of decoding for O(d) rounds of syndrome extraction is upper bounded by a quasi-polylogarithmic function of d. For a d-round decoding window, this implies that the average parallel runtime per round is o(1). We also perform numerical simulation to identify conditions under which the parallel runtime per round decreases with increasing code distance. These results suggest that increasing code distance need not lead to longer parallel decoding times, providing a foundation for scalable parallel matching-based decoding.
A major challenge in fault-tolerant quantum computation (FTQC) is to reduce both space overhead -- the large number of physical qubits per logical qubit -- and time overhead -- the long physical gate sequences per logical gate. We prove that a protocol using non-vanishing-rate quantum low-density parity-check (LDPC) codes, combined with concatenated Steane codes, achieves constant space overhead and polylogarithmic time overhead, even when accounting for non-zero classical computation time. This protocol offers an improvement over existing constant-space-overhead protocols, which have polynomial time overhead using quantum LDPC codes and quasi-polylogarithmic time overhead using concatenated quantum Hamming codes. To ensure the completeness of this proof, we develop a technique called partial circuit reduction, which enables error analysis for the entire fault-tolerant circuit by examining smaller parts composed of a few gadgets. With this technique, we resolve a previously unaddressed logical gap in the existing arguments and complete the proof of the threshold theorem for the constant-space-overhead protocol with quantum LDPC codes. Our work highlights that the quantum-LDPC-code approach can realize FTQC with a negligibly small slowdown and a bounded overhead of physical qubits, similar to the code-concatenation approach, underscoring the importance of a comprehensive comparison of the future realizability of these two approaches.
Abstract The essential requirement for fault-tolerant quantum computation (FTQC) is the total protocol design to achieve a fair balance of all the critical factors relevant to its practical realization, such as the space overhead, the threshold, and the modularity. A major obstacle in realizing FTQC with conventional protocols, such as those based on the surface code and the concatenated Steane code, has been the space overhead, i.e., the required number of physical qubits per logical qubit. Protocols based on high-rate quantum low-density parity-check (LDPC) codes gather considerable attention as a way to reduce the space overhead, but problematically, the existing fault-tolerant protocols for such quantum LDPC codes sacrifice other factors. Here, we construct a new fault-tolerant protocol to meet these requirements simultaneously based on more recent progress on the techniques for concatenated codes rather than quantum LDPC codes, achieving a constant space overhead, a high threshold, and flexibility in modular architecture designs. In particular, under a physical error rate of 0.1%, our protocol reduces the space overhead to achieve the logical CNOT error rates 10 −10 and 10 −24 by more than 90% and 96%, respectively, compared to the protocol for the surface code. Furthermore, our protocol achieves the threshold of 2.5% under a conventional circuit-level error model, substantially outperforming that of the surface code. The use of concatenated codes also naturally introduces abstraction layers essential for the modularity of FTQC architectures. These results indicate that the code-concatenation approach opens a way to significantly save qubits in realizing FTQC while fulfilling the other essential requirements for the practical protocol design.
Decoding a quantum error correction code is generally NP-hard, but corrections must be applied at a high frequency to suppress noise successfully. Matchable codes, like the surface code, exhibit a special structure that makes it possible to efficiently, approximately solve the decoding problem through minimum-weight perfect matching (MWPM). However, this efficiency-enabling property can be lost when constructing implementations for fault-tolerant gadgets such as syndrome-extraction circuits or logical operations.
In this work, we take a circuit-centric perspective to formalise how the decoding problem changes when applying ZX rewrites to a ZX diagram with a given detector basis. We demonstrate a set of rewrites that preserve MWPM-decodability of circuits and show that these matchability-preserving rewrites can be used to fault-tolerantly extract quantum circuits from phase-free ZX diagrams. In particular, this allows us to build efficiently decodable, fault-tolerant syndrome-extraction circuits for matchable codes.