Summary
The paper studies how hard it is to figure out the right number of times to repeat certain quantum operations called Clifford operations to get a desired effect. While some forward quantum operations are easy to simulate, solving the reverse problem can be very complicated, even impossible to do quickly in some cases. The authors show that some versions of this problem can be solved by classical or quantum computers efficiently, but others are proven to be computationally hard. Their work maps out which cases are easy and which are hard when trying to compile these quantum operations.
What this means in practice
- •For quantum hardware engineers: Design error-correcting circuits efficiently when only certain Clifford operations can be implemented, understanding which compilation problems are solvable in practice.
- •For quantum algorithm developers: Identify which quantum compilation problems can benefit from quantum algorithms and which are computationally intractable, guiding resource allocation.
A theory result. No direct application yet.
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.