Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors characterize the computational complexity landscape of Clifford template compilation, the inverse problem of finding operation repetition counts to synthesize target Pauli transformations under physical or fault-tolerance constraints. While forward Clifford dynamics are classically tractable via the Gottesman-Knill theorem, this inverse compilation problem exhibits sharp complexity phase transitions. Specifically, the commuting integer-exponent regime admits an efficient quantum algorithm in $\mathrm{NP}\cap\mathrm{BQP}$ linked to finite-field discrete logarithms, whereas restricting exponents to binary choices or bounding total repetitions collapses the problem into NP-completeness even for commuting CNOT gates.
Clifford circuits may be trivial to simulate classically, but compiling them is not: inverting Clifford templates unlocks a provable quantum speedup via discrete logarithms before strict hardware constraints push the task into NP-completeness.
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.