Bounded decoding complexity in transversal circuits with magic state injection
Abstract
We characterize the complexity of space-time correlated decoding for fault-tolerant quantum computing architectures that implement Clifford gates transversally and realize non-Clifford gates via magic state injection. In this approach, decoding graphs for logical measurements are constructed by backpropagating measurement operators through the circuit, which causes them to grow with circuit volume. However, the decoding volume can be substantially reduced by decoding measurements sequentially, committing corrections, and excluding syndrome data that have already been processed for earlier measurements. For random circuits, we find that the resulting decoding volume associated with mid-circuit measurements approaches a stationary average that is determined by the density of magic state injections. Large decoding instances are exponentially suppressed. We further find that the decoding complexity is remarkably insensitive to different choices of measurement products to be decoded, and that the same qualitative behavior persists across different circuit connectivities and Clifford gate ensembles. These results suggest that scalable space-time correlated decoding of large-scale fault-tolerant quantum algorithms is achievable since the magic states that make transversal architectures universal also keep them decodable.
Related
- High-Accuracy Propagation-Assisted Local Decoding for Fast Transversal Clifford Circuits
- Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity
- One Gate at a Time: Complexity Growth in Random Quantum Circuits
- Decoding complexity through machine learning is redefining scientific discovery
- Complexity of tensor network simulation for noisy quantum circuits
BibTeX
@misc{sieberer2026bounded,
title = {{Bounded decoding complexity in transversal circuits with magic state injection}},
author = {Lukas M. Sieberer and Giacomo Giudice},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05502},
eprint = {2611.05502},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05502},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bounded decoding complexity in transversal circuits with magic state injection
AU - Lukas M. Sieberer
AU - Giacomo Giudice
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05502
UR - https://arxiv.org/abs/2611.05502
AB - We characterize the complexity of space-time correlated decoding for fault-tolerant quantum computing architectures that implement Clifford gates transversally and realize non-Clifford gates via magic state injection. In this approach, decoding graphs for logical measurements are constructed by backpropagating measurement operators through the circuit, which causes them to grow with circuit volume. However, the decoding volume can be substantially reduced by decoding measurements sequentially, committing corrections, and excluding syndrome data that have already been processed for earlier measurements. For random circuits, we find that the resulting decoding volume associated with mid-circuit measurements approaches a stationary average that is determined by the density of magic state injections. Large decoding instances are exponentially suppressed. We further find that the decoding complexity is remarkably insensitive to different choices of measurement products to be decoded, and that the same qualitative behavior persists across different circuit connectivities and Clifford gate ensembles. These results suggest that scalable space-time correlated decoding of large-scale fault-tolerant quantum algorithms is achievable since the magic states that make transversal architectures universal also keep them decodable.
ER -