arXiv:2609.35239
Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
Keisuke Fujii
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 $\mathrm{NP}\cap\mathrm{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 $\mathbb{F}_{2^r}^{\times}$. 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.
AI Summary
The paper studies an inverse problem for efficiently simulable Clifford dynamics: given an ordered template $(U_1,\ldots,U_k)$ and Paulis $P,P'$, choose repetition counts so that $U_k^{e_k}\cdots U_1^{e_1}$ maps $P$ to $P'$ up to phase. This specifies one Pauli image, not a full Clifford transformation. It classifies complexity according to commutativity of the induced Pauli actions, exponent restrictions, and repetition cost. For commuting templates with unrestricted integer exponents, decision lies in $\mathrm{NP}\cap\mathrm{BQP}$; quantum polynomial time also returns a particular solution and the full exponent-relation lattice. The algorithm converts orbit membership into constructive membership in an Abelian matrix group, then uses quantum group algorithms and classical integer normal forms. One-operation witness recovery contains discrete logarithm over $\mathbb{F}_{2^r}^{\times}$, via binary-linear multiplication maps; a qudit extension includes $\mathbb{F}_p^{\times}$. Restricting exponents to $\{0,1\}$ makes commuting feasibility NP-complete for variable $k$, even with CNOT-only templates, through a Positive 1-in-3 SAT reduction. Commuting self-inverse actions instead admit deterministic polynomial-time feasibility and recovery of the full affine binary solution set, using a nilpotent filtration. Adding a bound on total operation uses makes feasibility NP-complete by syndrome decoding. Without commutativity, integer-exponent feasibility is NP-complete already at $k=3$, by embedding three-cyclic-subgroup permutation membership into SWAP-only templates. The noncommuting $k=2$ case remains open. No unconditional quantum speedup or practical resource advantage is established; small-characteristic discrete logarithms admit quasi-polynomial classical algorithms in relevant regimes. Full logical-Clifford compilation and circuit-level resource comparisons remain future directions.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 12 pages, 2 figures, 1 table