Achieving the limits of automorphism gates
Abstract
Universal fault-tolerant quantum computing combines versatile but expensive operations with specialized but cheap ones. Its efficiency depends on how much computation can be pushed onto the cheap operations and on the size of the code needed to do so. Automorphism gates provide such cheap operations using only physical single-qubit Clifford gates and qubit permutations. Yet no general theory characterizes their maximum logical power or the minimum code size needed to attain it. We develop such a theory. For stabilizer codes encoding k≥3 logical qubits, we show that the largest logical group attainable by automorphisms is generated by all addressable S and CX gates, and we construct codes attaining it. While this group contains exponentially fewer gates than the full Clifford group, adding one suitable non-Clifford gate yields universality. We further classify the largest logical groups attainable using qubit permutations, physical single-qubit Cliffords, or both across general stabilizer and CSS codes, and derive refined bounds for self-dual CSS subclasses. Achieving the maximum-size logical group through automorphisms requires n=Θ(2k) physical qubits. By contrast, all addressable diagonal Clifford gates, generated by S and CZ, require only n=Θ(k2) physical qubits when implemented using physical single-qubit Cliffords alone. Both bounds are tight. This polynomial qubit cost extends beyond Cliffords to all addressable diagonal gates at any fixed level of the Clifford hierarchy, using physical single-qubit diagonal gates. Thus, for full addressability, the sharpest physical-qubit cost divide lies between diagonal and CX-type gates, not between Clifford and non-Clifford gates.
Related
- Achieving the Quantum Limits with Twin-Field Sensors
- Simultaneously achieving Heisenberg- and Landau-limited precision in equilibrium quantum thermometry
- Achieving high filling of an optical lattice by light-assisted redistribution of atoms
- Achieving high quality 3D RI reconstructions from sparse data in high-throughput Holographic Tomography through CNN-based 2D projection synthesis
- Achieving Heisenberg limit under noisy conditions with quantum Zeno dynamics and dynamical decoupling
BibTeX
@misc{koh2026achieving,
title = {{Achieving the limits of automorphism gates}},
author = {Jin Ming Koh and Shayan Majidy and Aranya Chakraborty and Anqi Gong and Shi Jie Samuel Tan and Norman Y. Yao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19250},
eprint = {2609.19250},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19250},
}
RIS
TY - UNPB
TI - Achieving the limits of automorphism gates
AU - Jin Ming Koh
AU - Shayan Majidy
AU - Aranya Chakraborty
AU - Anqi Gong
AU - Shi Jie Samuel Tan
AU - Norman Y. Yao
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19250
UR - https://arxiv.org/abs/2609.19250
AB - Universal fault-tolerant quantum computing combines versatile but expensive operations with specialized but cheap ones. Its efficiency depends on how much computation can be pushed onto the cheap operations and on the size of the code needed to do so. Automorphism gates provide such cheap operations using only physical single-qubit Clifford gates and qubit permutations. Yet no general theory characterizes their maximum logical power or the minimum code size needed to attain it. We develop such a theory. For stabilizer codes encoding k≥3 logical qubits, we show that the largest logical group attainable by automorphisms is generated by all addressable S and CX gates, and we construct codes attaining it. While this group contains exponentially fewer gates than the full Clifford group, adding one suitable non-Clifford gate yields universality. We further classify the largest logical groups attainable using qubit permutations, physical single-qubit Cliffords, or both across general stabilizer and CSS codes, and derive refined bounds for self-dual CSS subclasses. Achieving the maximum-size logical group through automorphisms requires n=Θ(2^k) physical qubits. By contrast, all addressable diagonal Clifford gates, generated by S and CZ, require only n=Θ(k^2) physical qubits when implemented using physical single-qubit Cliffords alone. Both bounds are tight. This polynomial qubit cost extends beyond Cliffords to all addressable diagonal gates at any fixed level of the Clifford hierarchy, using physical single-qubit diagonal gates. Thus, for full addressability, the sharpest physical-qubit cost divide lies between diagonal and CX-type gates, not between Clifford and non-Clifford gates.
ER -