Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
Abstract
A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in NP∩BQP and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at k=1, recovering the repetition number contains finite-field discrete logarithm over 𝔽2r×. In general, restricting every exponent to {0,1} removes the Abelian-group closure and makes feasibility NP-complete for variable k, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.
Related
- Compiling Together: High-Throughput Distributed Quantum Computing via Multi-Compilation
- BRIDGE: Lazy-Move Compilation for Dual-Species Neutral-Atom Quantum Computers
- A Memory-Magic Exchange Law in Streaming Clifford+T Compilation
- Quantum computational advantage in random-circuit sampling on IBM superconducting quantum computers
- Benchmarking the computational power of quantum computers
BibTeX
@misc{fujii2026computational,
title = {{Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?}},
author = {Keisuke Fujii},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35239},
eprint = {2609.35239},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35239},
}
RIS
TY - UNPB
TI - Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
AU - Keisuke Fujii
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35239
UR - https://arxiv.org/abs/2609.35239
AB - A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in NP∩BQP and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at k=1, recovering the repetition number contains finite-field discrete logarithm over 𝔽_2^r^×. In general, restricting every exponent to {0,1} removes the Abelian-group closure and makes feasibility NP-complete for variable k, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.
ER -