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:2204.14205 · Electronic Proceedings in Theoretical Computer Science

Symbolic Synthesis of Clifford Circuits and Beyond

Matthew Amy, Owen Bennett-Gibbs, Neil J. Ross

Published Nov 14, 2023• 7 citations
arXivHTMLPDF

Abstract

Path sums are a convenient symbolic formalism for quantum operations with applications to the simulation, optimization, and verification of quantum protocols.Unlike quantum circuits, path sums are not limited to unitary operations, but can express arbitrary linear ones.Two problems, therefore, naturally arise in the study of path sums: the unitarity problem and the extraction problem.The former is the problem of deciding whether a given path sum represents a unitary operator.The latter is the problem of constructing a quantum circuit, given a path sum promised to represent a unitary operator.In this paper, we show that the unitarity problem is co-NP-hard in general, but that it is in P when restricted to Clifford path sums.We then provide an algorithm to synthesize a Clifford circuit from a unitary Clifford path sum.The circuits produced by our extraction algorithm are of the form C 1 HC 2 , where C 1 and C 2 are Hadamard-free circuits and H is a layer of Hadamard gates.We also provide a heuristic generalization of our extraction algorithm to arbitrary path sums.While this algorithm is not guaranteed to succeed, it often succeeds and typically produces natural looking circuits.Alongside applications to the optimization and decompilation of quantum circuits, we demonstrate the capability of our algorithm by synthesizing the standard quantum Fourier transform directly from a path sum.

DOI
10.4204/eptcs.394.17

Related papers

(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

A SAT Encoding for Optimal Clifford Circuit Synthesis

Sarah Schneider, Lukas Burgholzer, Robert Wille

Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.

arXiv:2208.11713•Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 16, 2023•30 citations

Clifford synthesis is NP-complete

Søren Fuglede Jørgensen

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

quant-pharXiv:2610.40886•Nov 2, 2026•0 citations

Parallelizing quantum circuit synthesis

Olivia Di Matteo, Michele Mosca

Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.

arXiv:1606.07413•Quantum Science and Technology•Mar 1, 2016•42 citations

Unitary Synthesis of Clifford+T Circuits with Reinforcement Learning

Sebastian Rietsch, Abhishek Y. Dubey, Christian Ufrecht +4 more

This paper presents a deep reinforcement learning approach for synthesizing unitaries into quantum circuits. Unitary synthesis aims to identify a quantum circuit that represents a given unitary while minimizing circuit depth, total gate count, a specific gate count, or a combination of these factors. While past research has focused predominantly on continuous gate sets, synthesizing unitaries from the parameter-free Clifford+T gate set remains a challenge. Although the time complexity of this task will inevitably remain exponential in the number of qubits for general unitaries, reducing the runtime for simple problem instances still poses a significant challenge. In this study, we apply the tree-search method Gumbel AlphaZero to solve the problem for a subset of exactly synthesizable Clifford+T unitaries. Our method effectively synthesizes circuits for up to five qubits generated from randomized circuits with up to 60 gates, outperforming existing tools like QuantumCircuitOpt and MIN-T-SYNTH in terms of synthesis time for larger qubit counts. Furthermore, it surpasses Synthetiq in successfully synthesizing random, exactly synthesizable unitaries. These results establish a strong baseline for future unitary synthesis algorithms.

arXiv:2404.14865•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•20 citations

An ASP Approach for the Synthesis of CNOT Minimal Quantum Circuits

Piazza C., Romanello R., Wille R.

In the last year, physical working Quantum Computers have been built and made available for the end users. Such devices, working under the rules of Quantum Mechanics, can only apply a finite set of one/two qubit operations that form a universal set of gates. Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. This synthesis procedure, however, is not constraint-free. In fact, we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. We start from a SAT encoding of the problem, and we translate it into an ASP model over a graph, by first working with a generic graph, and then by adopting the structure of a layered DAG. We provide experimental evidence of the scalability of our proposal.

•Jan 1, 2023•0 citations
Path sums are a convenient symbolic formalism for quantum operations with applications to the simulation, optimization, and verification of quantum protocols.Unlike quantum circuits, path sums are not limited to unitary operations, but can express arbitrary linear ones.Two problems, therefore, naturally arise in the study of path sums: the unitarity problem and the extraction problem.The former is the problem of deciding whether a given path sum represents a unitary operator.The latter is the problem of constructing a quantum circuit, given a path sum promised to represent a unitary operator.In this paper, we show that the unitarity problem is co-NP-hard in general, but that it is in P when restricted to Clifford path sums.We then provide an algorithm to synthesize a Clifford circuit from a unitary Clifford path sum.The circuits produced by our extraction algorithm are of the form C 1 HC 2 , where C 1 and C 2 are Hadamard-free circuits and H is a layer of Hadamard gates.We also provide a heuristic generalization of our extraction algorithm to arbitrary path sums.While this algorithm is not guaranteed to succeed, it often succeeds and typically produces natural looking circuits.Alongside applications to the optimization and decompilation of quantum circuits, we demonstrate the capability of our algorithm by synthesizing the standard quantum Fourier transform directly from a path sum.
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.
Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.
We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.
Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.
This paper presents a deep reinforcement learning approach for synthesizing unitaries into quantum circuits. Unitary synthesis aims to identify a quantum circuit that represents a given unitary while minimizing circuit depth, total gate count, a specific gate count, or a combination of these factors. While past research has focused predominantly on continuous gate sets, synthesizing unitaries from the parameter-free Clifford+T gate set remains a challenge. Although the time complexity of this task will inevitably remain exponential in the number of qubits for general unitaries, reducing the runtime for simple problem instances still poses a significant challenge. In this study, we apply the tree-search method Gumbel AlphaZero to solve the problem for a subset of exactly synthesizable Clifford+T unitaries. Our method effectively synthesizes circuits for up to five qubits generated from randomized circuits with up to 60 gates, outperforming existing tools like QuantumCircuitOpt and MIN-T-SYNTH in terms of synthesis time for larger qubit counts. Furthermore, it surpasses Synthetiq in successfully synthesizing random, exactly synthesizable unitaries. These results establish a strong baseline for future unitary synthesis algorithms.
In the last year, physical working Quantum Computers have been built and made available for the end users. Such devices, working under the rules of Quantum Mechanics, can only apply a finite set of one/two qubit operations that form a universal set of gates. Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. This synthesis procedure, however, is not constraint-free. In fact, we prefer circuits with minimum number of qubits and with minimum circuit depth. Clifford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many efforts have been directed to devise algorithms that synthesize general unitary matrices into Clifford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Clifford+T circuit. We start from a SAT encoding of the problem, and we translate it into an ASP model over a graph, by first working with a generic graph, and then by adopting the structure of a layered DAG. We provide experimental evidence of the scalability of our proposal.