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

Nature Physics

Fault-tolerant quantum computation with polylogarithmic time and constant space overheads

Shiro Tamiya, Masato Koashi, Hayata Yamasaki

Published Nov 26, 2025• 0 citations
Publisher

Abstract

Abstract A major challenge in fault-tolerant quantum computation is to reduce both the space overhead, that is, the large number of physical qubits per logical qubit, and the time overhead, that is, the long physical gate sequences needed to implement a logical gate. Here we prove that a protocol using non-vanishing-rate quantum low-density parity-check (QLDPC) codes, combined with concatenated Steane codes, achieves constant space overhead and polylogarithmic time overhead, even when accounting for the required classical processing. This protocol offers an improvement over existing constant-space-overhead protocols. To prove our result, we develop a technique that we call partial circuit reduction, which enables error analysis for the entire fault-tolerant circuit by examining smaller parts composed of a few gadgets. With this approach, we resolve a logical gap in the existing arguments for the threshold theorem for the constant-space-overhead protocol with QLDPC codes and complete its proof. Our work establishes that the QLDPC-code-based approach can realize fault-tolerant quantum computation with a negligibly small slowdown and a bounded overhead of physical qubits.

DOI
10.1038/s41567-025-03102-5

Related papers

Polylog-time- and constant-space-overhead fault-tolerant quantum computation with quantum low-density parity-check codes

Shiro Tamiya, Masato Koashi, Hayata Yamasaki

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.

arXiv:2411.03683•Nov 6, 2024•0 citations

Fault-tolerant quantum computation with constant overhead for general noise

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

Fault-tolerant quantum computation traditionally incurs substantial resource overhead, with both qubit and time overheads scaling polylogarithmically with the size of the computation. While prior work by Gottesman showed that constant qubit overhead is achievable under stochastic noise using quantum low-density parity-check (QLDPC) codes, it has remained an open question whether similar guarantees hold under more general, non-stochastic noise models. In this work, we address this question by considering a general circuit-level noise model defined via the diamond norm, which captures both stochastic and non-stochastic noise, including coherent and amplitude damping noise. We prove that constant qubit overhead fault-tolerant quantum computation is achievable in this general setting, using QLDPC codes with constant rate and linear minimum distance. To establish our result, we develop a fault-tolerant error correction scheme and a method for implementing logic gates under general circuit noise. These results extend the theoretical foundations of fault-tolerant quantum computation and offer new directions for fault-tolerant architectures under realistic noise models.

quant-pharXiv:2512.02760•PRX Quantum•Dec 3, 2025•2 citations

Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation

Hayata Yamasaki, Masato Koashi

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.

arXiv:2207.08826•Nature Physics•Jan 16, 2024•54 citations

Concatenate codes, save qubits

Satoshi Yoshida, Shiro Tamiya, Hayata Yamasaki

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.

arXiv:2402.09606•npj Quantum Information•May 31, 2025•20 citations

Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable Atom Arrays

Qian Xu, J. Pablo Bonilla Ataides, Christopher A. Pattison +7 more

Quantum low-density parity-check (qLDPC) codes can achieve high encoding rates and good code distance scaling, providing a promising route to low-overhead fault-tolerant quantum computing. However, the long-range connectivity required to implement such codes makes their physical realization challenging. Here, we propose a hardware-efficient scheme to perform fault-tolerant quantum computation with high-rate qLDPC codes on reconfigurable atom arrays, directly compatible with recently demonstrated experimental capabilities. Our approach utilizes the product structure inherent in many qLDPC codes to implement the non-local syndrome extraction circuit via atom rearrangement, resulting in effectively constant overhead in practically relevant regimes. We prove the fault tolerance of these protocols, perform circuit-level simulations of memory and logical operations with these codes, and find that our qLDPC-based architecture starts to outperform the surface code with as few as several hundred physical qubits at a realistic physical error rate of $10^{-3}$. We further find that less than 3000 physical qubits are sufficient to obtain over an order of magnitude qubit savings compared to the surface code, and quantum algorithms involving thousands of logical qubits can be performed using less than $10^5$ physical qubits. Our work paves the way for explorations of low-overhead quantum computing with qLDPC codes at a practical scale, based on current experimental technologies.

arXiv:2308.08648•Aug 16, 2023•6 citations

Efficient Logic with Ultra-High-Rate Quantum Codes

Nishad Maskara, Rohan Mehta, Zhiyang He +4 more

Quantum low-density parity-check (qLDPC) codes offer a promising route to reducing the qubit overhead of fault tolerance, with recent ultra-high-rate constructions achieving encoding rates above one half. In this work, we develop fast and parallel logical computation methods for ultra-high-rate codes. We first utilize the group symmetries of the codes to partition the logical qubits into orbits, and then apply parallel surgery methods to implement group-invariant collections of logical Pauli-product measurements. These measurements are highly programmable, as we may arbitrarily couple logical orbits as long as each measurement is repeated across the whole orbit(s). To reduce the space and time overheads, we develop a technique called chain-map convolution, which uses the group structure to boost both the spatial and temporal distances of our protocol in a highly efficient manner. As case studies, we construct distance-preserving parallel measurement gadgets for the [[256, 68, 12]], [[576, 148, 18]] pair-partition codes, and a [[1152, 580, 12]] rate-$1/2$ code, with only around $2.5\times$ space overhead and 3-4 rounds of syndrome extraction each. The same methods also enable parallel injection of cultivated magic states into high-rate codes. Finally, we extend programmability through subgroup restrictions, revealing a tradeoff between logical control and the spacetime resources required for fault tolerance and highlighting the crucial role structured parallelism plays in reducing overhead. These results provide new methods for designing qLDPC logical operations with low spacetime overhead, opening a route toward more efficient fault-tolerant quantum architectures.

quant-pharXiv:2610.06749•Oct 6, 2026•0 citations
Abstract A major challenge in fault-tolerant quantum computation is to reduce both the space overhead, that is, the large number of physical qubits per logical qubit, and the time overhead, that is, the long physical gate sequences needed to implement a logical gate. Here we prove that a protocol using non-vanishing-rate quantum low-density parity-check (QLDPC) codes, combined with concatenated Steane codes, achieves constant space overhead and polylogarithmic time overhead, even when accounting for the required classical processing. This protocol offers an improvement over existing constant-space-overhead protocols. To prove our result, we develop a technique that we call partial circuit reduction, which enables error analysis for the entire fault-tolerant circuit by examining smaller parts composed of a few gadgets. With this approach, we resolve a logical gap in the existing arguments for the threshold theorem for the constant-space-overhead protocol with QLDPC codes and complete its proof. Our work establishes that the QLDPC-code-based approach can realize fault-tolerant quantum computation with a negligibly small slowdown and a bounded overhead of physical qubits.
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.
Fault-tolerant quantum computation traditionally incurs substantial resource overhead, with both qubit and time overheads scaling polylogarithmically with the size of the computation. While prior work by Gottesman showed that constant qubit overhead is achievable under stochastic noise using quantum low-density parity-check (QLDPC) codes, it has remained an open question whether similar guarantees hold under more general, non-stochastic noise models. In this work, we address this question by considering a general circuit-level noise model defined via the diamond norm, which captures both stochastic and non-stochastic noise, including coherent and amplitude damping noise. We prove that constant qubit overhead fault-tolerant quantum computation is achievable in this general setting, using QLDPC codes with constant rate and linear minimum distance. To establish our result, we develop a fault-tolerant error correction scheme and a method for implementing logic gates under general circuit noise. These results extend the theoretical foundations of fault-tolerant quantum computation and offer new directions for fault-tolerant architectures under realistic noise models.
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.
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.
Quantum low-density parity-check (qLDPC) codes can achieve high encoding rates and good code distance scaling, providing a promising route to low-overhead fault-tolerant quantum computing. However, the long-range connectivity required to implement such codes makes their physical realization challenging. Here, we propose a hardware-efficient scheme to perform fault-tolerant quantum computation with high-rate qLDPC codes on reconfigurable atom arrays, directly compatible with recently demonstrated experimental capabilities. Our approach utilizes the product structure inherent in many qLDPC codes to implement the non-local syndrome extraction circuit via atom rearrangement, resulting in effectively constant overhead in practically relevant regimes. We prove the fault tolerance of these protocols, perform circuit-level simulations of memory and logical operations with these codes, and find that our qLDPC-based architecture starts to outperform the surface code with as few as several hundred physical qubits at a realistic physical error rate of 10−310^{-3}10−3. We further find that less than 3000 physical qubits are sufficient to obtain over an order of magnitude qubit savings compared to the surface code, and quantum algorithms involving thousands of logical qubits can be performed using less than 10510^5105 physical qubits. Our work paves the way for explorations of low-overhead quantum computing with qLDPC codes at a practical scale, based on current experimental technologies.
Quantum low-density parity-check (qLDPC) codes offer a promising route to reducing the qubit overhead of fault tolerance, with recent ultra-high-rate constructions achieving encoding rates above one half. In this work, we develop fast and parallel logical computation methods for ultra-high-rate codes. We first utilize the group symmetries of the codes to partition the logical qubits into orbits, and then apply parallel surgery methods to implement group-invariant collections of logical Pauli-product measurements. These measurements are highly programmable, as we may arbitrarily couple logical orbits as long as each measurement is repeated across the whole orbit(s). To reduce the space and time overheads, we develop a technique called chain-map convolution, which uses the group structure to boost both the spatial and temporal distances of our protocol in a highly efficient manner. As case studies, we construct distance-preserving parallel measurement gadgets for the [[256, 68, 12]], [[576, 148, 18]] pair-partition codes, and a [[1152, 580, 12]] rate-1/21/21/2 code, with only around 2.5×2.5\times2.5× space overhead and 3-4 rounds of syndrome extraction each. The same methods also enable parallel injection of cultivated magic states into high-rate codes. Finally, we extend programmability through subgroup restrictions, revealing a tradeoff between logical control and the spacetime resources required for fault tolerance and highlighting the crucial role structured parallelism plays in reducing overhead. These results provide new methods for designing qLDPC logical operations with low spacetime overhead, opening a route toward more efficient fault-tolerant quantum architectures.