PaperlayerView exact revision on arXiv

Source-linked AI summary

Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?

Keisuke Fujii

arXiv:2609.35239v1quant-phcs.CC

TL;DR

Clifford template compilation asks whether repetition counts for a prescribed family of operations can realize a target Pauli, a relevant inverse problem when hardware or fault-tolerance constraints restrict available operations. The paper analyzes commuting and noncommuting templates with unrestricted or binary exponents, finding regimes from classical polynomial time to NP-completeness and quantum polynomial-time algorithms. In the commuting integer-exponent regime, a constructive quantum algorithm recovers a solution and the full exponent-relation lattice.

  • Problem

    Clifford template compilation asks how to realize a target Pauli using repetition counts from a prescribed operation family, especially when hardware or fault-tolerance constraints restrict the available Clifford operations.

    Source: §I · p. 1

  • Method

    The paper analyzes Pauli reachability across commuting and noncommuting templates, distinguishing unrestricted integer exponents from binary exponents and decision from search.

    Source: §I · p. 2, §II · p. 3

  • Results

    Commuting integer-exponent decision CTC lies in NP∩BQP and quantum search returns a solution with the full relation lattice; binary commuting decision is NP-complete, and self-inverse feasibility is polynomial-time while bounded-use feasibility is NP-complete.

    Source: §I · p. 2

  • Takeaways & Limitations

    The results place quantum witness recovery, classical tractability, and NP-complete variants in neighboring regimes of one Clifford–Pauli reachability framework.

    Source: §VII · p. 11

    The resource comparison does not establish quantum advantage, and a more detailed comparison remains future work.

    Source: §VII · p. 11

Abstract

from arXiv · show

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.

I. INTRODUCTION

The introduction defines Clifford template compilation as an inverse reachability problem: choose repetition counts so an ordered family of Clifford operations maps an input Pauli to a target. It presents sharp complexity transitions across commutativity, exponent restrictions, and whether the task is decision or search.

I. INTRODUCTION

  • The inverse problem remains challenging despite efficient forward Clifford simulation because repetition counts and the number of possible patterns can be exponentially large.Counts encoded with polynomially many bits may represent exponentially many applications, and variable template size creates exponentially many patterns.Source: §I · p. 1
  • CTC asks whether repetition counts for a prescribed ordered Clifford family map an input Pauli to a target, up to phase.The paper studies both general ordered templates and templates whose induced phase-free Pauli actions commute, with unrestricted or binary exponents.Source: §I · p. 1
  • Binary commuting decision is NP-complete for variable k, while self-inverse actions permit polynomial-time feasibility but bounded total repetition count is NP-complete.The binary hardness holds even for exactly commuting CNOT-only operations and X-type Paulis; the bounded-count hardness also holds for CNOT-only operations.Source: §I · p. 2
  • Commuting integer-exponent decision CTC lies in NP∩BQP, quantum search returns a solution and relation lattice, and its k=1 search slice contains finite-field discrete logarithm.The relation-lattice output gives all exponent relations, not just one witness.Source: §I · p. 2
  • Without commutativity, integer-exponent decision CTC is NP-complete at k=3, while the general k=2 case remains open.The hardness holds for wire-permutation Clifford operations, including SWAP-only circuits.Source: §I · p. 2
  • The paper’s distinctive point is that structured witness recovery and NP-complete selection occupy adjacent regimes of one reachability framework, not that quantum computers solve NP-complete languages.In the binary-linear subfamily, phase estimation uses CNOT-only maps, while coherent control introduces Toffoli gates.Source: §I · pp. 2–3

II. PAULI AND CLIFFORD REPRESENTATION

This section represents phase-free Clifford actions as symplectic maps on Pauli vectors and formulates compilation as deciding whether a template’s exponents reach a target Pauli. It distinguishes unrestricted integer exponents from binary exponents and establishes efficient verification of proposed solutions.

II. PAULI AND CLIFFORD REPRESENTATION

  • An n-qubit Pauli is represented up to phase by a binary vector, and a Clifford acts on it through a symplectic matrix that preserves the standard symplectic form.The construction for NP-completeness uses CNOT gates and X-type Paulis, so it can also be viewed as reversible binary linear circuits.Source: §II · p. 3
  • A Clifford template is an ordered finite tuple of Clifford operations designated for repeated use, instantiated by an exponent vector.The template size k is the number of operations in the tuple.Source: §II · p. 3
  • Commutativity means the induced phase-free Pauli actions commute as symplectic matrices; the Clifford unitaries themselves need not commute.Exact unitary commutativity implies this condition, but the converse need not hold.Source: §II · p. 3
  • Decision CTC asks whether nonnegative integer exponents map the input Pauli vector to the target, with binary CTC restricting every exponent to 0 or 1.Because each induced matrix belongs to a finite group, unrestricted integer exponents can be reduced modulo its order.Source: §II · p. 3
  • A proposed exponent vector can be verified in polynomial time by evaluating the ordered product and checking the target condition, so decision CTC lies in NP.Periodicity bounds each exponent’s representation to O(n^2) bits.Source: §II · p. 3

III. NP-COMPLETENESS OF BINARY COMMUTING CTC

A three-qubit gadget encodes whether exactly one variable is selected in a clause, yielding a reduction from Positive 1-in-3 SAT to binary-exponent commuting CTC. The reduction proves NP-completeness even for exactly commuting CNOT-only operations and X-type Paulis.

A. A three-qubit clause gadget

  • The gadget’s four-step orbit distinguishes zero, one, two, or three selected variables; its target X-support represents exactly one.The initial support is (0, 0, 1)T, and J4 = I.Source: A. A three-qubit clause gadget · p. 4

B. Variable-size template

  • Binary-exponent commuting decision CTC is NP-complete for variable template size, even with CNOT-only operations and X-type Paulis.The reduction uses exactly commuting operations of order dividing four.Source: B. Variable-size template · p. 4
  • The reduction maps satisfying Positive 1-in-3 SAT assignments to Boolean exponent vectors satisfying the Pauli-orbit equation.Each SAT variable determines whether its corresponding template operation is selected.Source: B. Variable-size template · p. 4
  • Binary search CTC reduces to binary decision CTC using at most k decision queries, respecting the given operation order.At each step, the query tests whether a solution remains with the current exponent set to zero.Source: B. Variable-size template · p. 5

C. A complete nine-qubit example

The example instantiates a six-operation commuting CNOT template derived from a three-clause, six-variable Positive 1-in-3 SAT formula. Its selected variables produce the target Pauli, giving an explicit nine-qubit instance of the reduction.

C. A complete nine-qubit example

  • The example uses three clause blocks of three qubits and six template operations built from the clause operations.The clause operations act on disjoint blocks, so the template operations commute.Source: C. A complete nine-qubit example · p. 5
  • Setting only x1 and x6 to true satisfies all three clauses, making each clause’s unique true variable correspond to the target Pauli action.The resulting assignment obeys F6F1a = b.Source: C. A complete nine-qubit example · p. 5
  • The construction gives a fully explicit nine-qubit instance in the binary symplectic representation.The example lists the six operations as blockwise combinations of the clause matrix J and identity I3.Source: C. A complete nine-qubit example · p. 5

IV. NONCOMMUTING TEMPLATES: NP-COMPLETE AT k = 3

Without commutativity, decision CTC is NP-complete already at fixed template size k = 3. The reduction embeds permutation-group 3-knapsack using wire-permutation Clifford operations and X-type Paulis.

IV. NONCOMMUTING TEMPLATES: NP-COMPLETE AT k = 3

  • The reduction represents each permutation by a wire-permutation Clifford acting on m2 qubits, with polynomial circuit size.The representation is faithful, and equality of the complete permutation is encoded in the image of a single Pauli.Source: §IV · p. 5
  • Decision CTC is NP-complete at fixed template size k = 3, even for SWAP-only operations and X-type input and target Paulis.The operations implement wire permutations as Clifford circuits.Source: §IV · p. 6
  • The construction maps permutation-group 3-knapsack to CTC, and its polynomial size establishes NP-hardness.Finite permutation orders allow exponents to be represented by canonical representatives.Source: §IV · pp. 5–6

A. Quantum algorithm for unrestricted integer exponents

For commuting templates with unrestricted integer exponents, the paper reduces Pauli reachability to constructive membership in a finite Abelian matrix group. Quantum polynomial-time algorithms find a solution and the full exponent-relation lattice, while decision lies in NP ∩ BQP.

A. Quantum algorithm for unrestricted integer exponents

  • Commuting decision CTC lies in NP ∩ BQP, and commuting search CTC is solvable in quantum polynomial time with a particular solution and full relation-lattice basis.The construction reduces the reachability question to constructive membership in a finite Abelian matrix group.Source: A. Quantum algorithm for unrestricted… · p. 6
  • The algorithm constructs the orbit span W, turns target vector b into an operator Cb on W, and tests whether Cb belongs to the group generated by the restricted matrices Bi.If b is outside W, no orbit element can equal it.Source: A. Quantum algorithm for unrestricted… · p. 6
  • Quantum order finding, group decomposition, and coordinate relation finding yield the group coordinates; classical Smith-normal-form computation then solves the integer system.The resulting solutions form an affine lattice, whose basis describes the full exponent-relation lattice.Source: A. Quantum algorithm for unrestricted… · p. 7
  • The algorithm runs in quantum polynomial time because the orbit dimension is at most 2n and the matrix-group operations have polynomial cost.Ignoring the returned witness gives the BQP decision upper bound; polynomially verifiable periodic representatives give the NP inclusion.Source: A. Quantum algorithm for unrestricted… · pp. 6–7
  • The Boolean restriction removes the group closure used by the integer-exponent method, while commutativity is essential to its upper bound.The noncommuting case is NP-complete at k = 3; the general k = 2 case remains open in the cited discussion.Source: A. Quantum algorithm for unrestricted… · p. 7

B. Self-inverse Clifford actions: reachability versus repetition cost

For commuting self-inverse Clifford actions, reachability is classically tractable because integer repetitions do not enlarge the binary orbit. Adding a bound on total operation uses changes the problem: deciding whether a solution meets the bound is NP-complete.

Reachability

  • For self-inverse actions, reducing each integer exponent modulo two preserves its action, so binary and unrestricted integer exponents have the same reachability.This equivalence does not remove the hardness introduced by a bound on total operation uses.Source: B. Self-inverse Clifford actions:… · pp. 8–9
  • Without a cost bound, commuting self-inverse actions permit deterministic polynomial-time reachability and recovery of a binary solution, with the full solution set represented as an affine subspace.The algorithm returns one representative and a basis of the homogeneous solution space rather than enumerating all solutions.Source: B. Self-inverse Clifford actions:… · p. 8

Reachability algorithm

  • The classical algorithm refines affine candidate sets by solving linear systems over F2 until the allowed error space is zero.The intermediate subspaces are computed recursively, without enumerating products of the commuting generators.Source: B. Self-inverse Clifford actions:… · p. 8

Repetition cost

  • The total-operation budget makes reachability NP-complete, even for exactly commuting CNOT-only self-inverse operations.The budget counts uses of supplied template operations, not the elementary gates inside each operation.Source: B. Self-inverse Clifford actions:… · p. 9

A. Qubit case: discrete logarithm over F2r

For a one-operation qubit template, the search for a repetition count can encode discrete logarithm over F2^r. The construction represents multiplication by a fixed field element as a Clifford action and uses Pauli reachability to recover the exponent.

Construction

  • Multiplication by a fixed nonzero field element is F2-linear and can be synthesized as a CNOT-and-SWAP circuit, giving the Clifford action used in the embedding.The construction obtains the matrix by field arithmetic in a chosen basis and synthesizes it using binary row operations.Source: A. Qubit case: discrete logarithm over… · p. 9
  • The one-operation reachability instance uses an X-type input representing 1 and a target representing h, so its repetition count recovers the exponent in the finite-field discrete logarithm instance.For X-type Paulis, only the multiplication matrix block acts.Source: A. Qubit case: discrete logarithm over… · p. 10

DLP embedding

  • Search CTC for a one-operation qubit template is discrete-logarithm hard under polynomial-time reductions, whereas the corresponding decision task only tests subgroup membership.The search task recovers an exponent; the decision task asks whether the target belongs to the cyclic subgroup generated by the input element.Source: A. Qubit case: discrete logarithm over… · p. 10

Toy example

  • In the toy instance, the target condition holds exactly for e ≡ 5 (mod 7), making e = 5 a canonical repetition count.That solution corresponds to five applications of the supplied operation.Source: A. Qubit case: discrete logarithm over… · p. 10

B. Extension to odd prime dimensions

The one-operation discrete-logarithm embedding extends from qubits to prime-dimensional qudits by representing field multiplication as a linear map over Fp. Taking r = 1 yields prime-field discrete logarithm as a one-qudit Clifford-orbit problem.

Prime-dimensional extension

  • For prime-dimensional qudits, multiplication by a field element defines an Fp-linear map and hence a Clifford action in the stated construction.The paper describes the extension for a field Fp^r represented as an r-dimensional vector space over Fp.Source: B. Extension to odd prime dimensions · p. 10

Prime-field case

  • Setting r = 1 makes prime-field discrete logarithm over Fp^× a one-qudit Clifford-orbit problem.The paper notes that no classical polynomial-time algorithm is known for prime-field DLP, while describing number-field-sieve-type attacks as subexponential.Source: B. Extension to odd prime dimensions · p. 10

Classical algorithms

  • For fixed small characteristic, including F2^r, the passage reports quasi-polynomial classical algorithms in important asymptotic regimes.This contrasts with the stated prime-field algorithmic landscape.Source: B. Extension to odd prime dimensions · p. 10

VII. DISCUSSION

The discussion frames CTC as one reachability relation with sharply different complexity regimes, including quantum-time witness recovery, NP-complete binary decision, and classical tractability under self-inverse actions. It also identifies unresolved extensions and resource questions.

Complexity landscape

  • Commuting integer-exponent CTC permits quantum polynomial-time recovery of a solution and relation lattice, while binary feasibility is NP-complete for variable k and noncommuting integer decision is NP-complete with three wire-permutation Cliffords.The DLP search and NP-complete binary-decision embeddings occupy different parameter and output regimes of the same reachability relation.Source: §VII · p. 11

Feasibility versus cost

  • For commuting self-inverse actions, a feasible vector is classically recoverable, but requiring at most m operation uses makes decision NP-complete.The syndrome-decoding construction shows the cost difficulty can persist even when a solution and the full relation lattice are already known.Source: §VII · p. 11

Resource perspective

  • The binary-linear DLP embedding may suit early fault-tolerant benchmarking, but the passage says this observation does not establish quantum advantage.Its uncontrolled maps are CNOT-and-SWAP circuits, while non-Clifford gates enter when those maps are coherently controlled.Source: §VII · p. 11

Open directions

  • Open directions include the noncommuting two-operation case, full logical Clifford transformations, and making the BQP algorithm explicit for binary linear maps with low CNOT volume and Toffoli depth.The discussion also calls for families whose classical algorithms remain costly while retaining low-non-Clifford controlled-linear structure.Source: §VII · pp. 11–12
Loading 2609.35239v1…