Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.35239

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

Keisuke Fujii

quant-phcs.CCSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textIncremental

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
12 pages, 2 figures, 1 table

Related papers

Quantum Fourier transform toolbox

Carli Bruinsma, Pietro M. Posta, Joppe Stokvis +2 more

Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over $\mathrm{GL}_2(F_q)$ that scale polynomially in $\log q$, rather than polynomially in $q$. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products $F\wr S_n$, whose cost depends on the cost of a QFT over $F$ and the size of its representation registers. This removes the restriction $|F|=\operatorname{poly}(n)$ required by previous generic constructions and can yield exponential improvements when $F$ itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.

quant-pharXiv:2608.28573•Aug 31, 2026•2 citations

Trapdoored Clifford Operators and Applications

Minki Hhan, Hojune Lee

Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random $n$-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.

quant-pharXiv:2610.01848•Oct 2, 2026•2 citations

(A Variant of) Clifford Circuit Synthesis is NP-Complete

Luna Lima Keller, Richard Kueng

Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.

quant-pharXiv:2610.02029•Oct 2, 2026•2 citations

New methods for Quantum Compiling

Vadym Kliuchnikov

The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.

•Apr 30, 2014•3 citations

A polynomial time and space heuristic algorithm for T-count

Michele Mosca, Priyanka Mukhopadhyay

Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.

arXiv:2006.12440•Quantum Science and Technology•Oct 7, 2021•34 citations

Clifford Circuit Optimization with Templates and Symbolic Pauli Gates

Sergey B. Bravyi, Ruslan Shaydulin, Shaohan Hu +1 more

The Clifford group is a finite subgroup of the unitary group generated by the Hadamard, the CNOT, and the Phase gates. This group plays a prominent role in quantum error correction, randomized benchmarking protocols, and the study of entanglement. Here we consider the problem of finding a short quantum circuit implementing a given Clifford group element. Our methods aim to minimize the entangling gate count assuming all-to-all qubit connectivity. First, we consider circuit optimization based on template matching and design Clifford-specific templates that leverage the ability to factor out Pauli and SWAP gates. Second, we introduce a symbolic peephole optimization method. It works by projecting the full circuit onto a small subset of qubits and optimally recompiling the projected subcircuit via dynamic programming. CNOT gates coupling the chosen subset of qubits with the remaining qubits are expressed using symbolic Pauli gates. Software implementation of these methods finds circuits that are only 0.2% away from optimal for 6 qubits and reduces the two-qubit gate count in circuits with up to 64 qubits by 64.7% on average, compared with the Aaronson-Gottesman canonical form.

arXiv:2105.02291•Quantum•Nov 16, 2021•53 citations
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\mathrm{NP}\cap\mathrm{BQP}NP∩BQP and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at k=1k=1k=1, recovering the repetition number contains finite-field discrete logarithm over F2r×\mathbb{F}_{2^r}^{\times}F2r×​. In general, restricting every exponent to {0,1}\{0,1\}{0,1} removes the Abelian-group closure and makes feasibility NP-complete for variable kkk, 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.
The paper studies an inverse problem for efficiently simulable Clifford dynamics: given an ordered template (U1,…,Uk)(U_1,\ldots,U_k)(U1​,…,Uk​) and Paulis P,P′P,P'P,P′, choose repetition counts so that Ukek⋯U1e1U_k^{e_k}\cdots U_1^{e_1}Ukek​​⋯U1e1​​ maps PPP to P′P'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 NP∩BQP\mathrm{NP}\cap\mathrm{BQP}NP∩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 F2r×\mathbb{F}_{2^r}^{\times}F2r×​, via binary-linear multiplication maps; a qudit extension includes Fp×\mathbb{F}_p^{\times}Fp×​.
Restricting exponents to {0,1}\{0,1\}{0,1} makes commuting feasibility NP-complete for variable kkk, 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=3k=3k=3, by embedding three-cyclic-subgroup permutation membership into SWAP-only templates.
The noncommuting k=2k=2k=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.
Quantum Fourier transforms (QFTs) are essential primitives in quantum algorithms. While abelian groups admit efficient QFT circuits, with circuit size polynomial in the logarithm of the group order, efficient constructions are known for relatively few non-abelian families. We develop two new approaches to QFT circuit construction, based on Mackey theory and Clifford theory, respectively, and use them to show exponential improvement in circuit cost for specific group families. Using the Mackey-theoretic approach, we obtain explicit quantum circuits for the QFT over GL2(Fq)\mathrm{GL}_2(F_q)GL2​(Fq​) that scale polynomially in log⁡q\log qlogq, rather than polynomially in qqq. Using the Clifford-theoretic approach, we obtain QFT circuits for wreath products F≀SnF\wr S_nF≀Sn​, whose cost depends on the cost of a QFT over FFF and the size of its representation registers. This removes the restriction ∣F∣=poly⁡(n)|F|=\operatorname{poly}(n)∣F∣=poly(n) required by previous generic constructions and can yield exponential improvements when FFF itself has an efficient QFT. Together, these methods provide new systematic tools to construct QFTs for broad classes of finite groups.
Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random nnn-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.
Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.
The Clifford group is a finite subgroup of the unitary group generated by the Hadamard, the CNOT, and the Phase gates. This group plays a prominent role in quantum error correction, randomized benchmarking protocols, and the study of entanglement. Here we consider the problem of finding a short quantum circuit implementing a given Clifford group element. Our methods aim to minimize the entangling gate count assuming all-to-all qubit connectivity. First, we consider circuit optimization based on template matching and design Clifford-specific templates that leverage the ability to factor out Pauli and SWAP gates. Second, we introduce a symbolic peephole optimization method. It works by projecting the full circuit onto a small subset of qubits and optimally recompiling the projected subcircuit via dynamic programming. CNOT gates coupling the chosen subset of qubits with the remaining qubits are expressed using symbolic Pauli gates. Software implementation of these methods finds circuits that are only 0.2% away from optimal for 6 qubits and reduces the two-qubit gate count in circuits with up to 64 qubits by 64.7% on average, compared with the Aaronson-Gottesman canonical form.