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:2101.03142 · npj Quantum Information

A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits

Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

Published Sep 13, 2022• 16 citations
arXivHTMLPDF

Abstract

Abstract We investigate the problem of synthesizing T-depth optimal quantum circuits for exactly implementable unitaries over the Clifford+T gate set. We construct a subset, $${{\mathbb{V}}}_{n}$$ Vn , of T-depth 1 unitaries. T-depth-optimal decomposition of unitaryUis $${e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)C$$ eiϕ∏iViC , $${V}_{i}\in {{\mathbb{V}}}_{n}$$ Vi∈Vn ,Cis Clifford and $$| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}$$ ∣Vn∣≤n⋅25.6n . We use nested meet-in-the-middle technique to synthesize provably depth-optimal and T-depth-optimal circuits. For the latter, we achieve space and time complexity $$O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })$$ O((4n2)⌈d/c⌉) and $$O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })$$ O((4n2)(c−1)⌈d/c⌉) respectively (dis the minimum T-depth,c ≥ 2 a constant). The previous best algorithm had complexity $$O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})$$ O((3n⋅2kn2)⌈d2⌉⋅2kn2) (k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n, d) (or $${{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)$$ poly(nlogn,25.6n,d) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.

DOI
10.1038/s41534-022-00624-1

Related papers

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•9 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•29 citations

Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers

Tom Peham, Nina Brandl, Richard Kueng +2 more

Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems - one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy (NP), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy (Σp2). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search.

arXiv:2305.01674•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•15 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•0 citations

A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits

Matthew Amy, D. Maslov, Michele Mosca +1 more

We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide a significant speedup over simple brute force algorithms. As an illustration of our method, we implemented this algorithm and found factorizations of commonly used quantum logical operations into elementary gates in the Clifford+Tset. In particular, we report a decomposition of the Toffoli gate over the set of Clifford andTgates. Our decomposition achieves a totalT-depth of 3, thereby providing a 40% reduction over the previously best known decomposition for the Toffoli gate. Due to the size of the search space, the algorithm is only practical for small parameters, such as the number of qubits, and the number of gates in an optimal implementation.

arXiv:1206.0758•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 15, 2013•548 citations

T-count and T-depth of any multi-qubit unitary

Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

Abstract We design an algorithm to determine the (minimum) T-count of any n -qubit ( n ≥ 1) unitary W of size 2 n × 2 n , over the Clifford+T gate set. The space and time complexity of our algorithm are $$O\left({2}^{2n}\right)$$ O 2 2 n and $$O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)$$ O 2 2 n T ϵ ( W ) + 4 n , respectively. $${{{{\mathcal{T}}}}}_{\epsilon }(W)$$ T ϵ ( W ) ( ϵ -T-count) is the (minimum) T-count of an exactly implementable unitary U ( $${{{\mathcal{T}}}}(U)$$ T ( U ) ), such that d ( U , W ) ≤ ϵ and $${{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })$$ T ( U ) ≤ T ( U ′ ) where $${U}^{{\prime} }$$ U ′ is any exactly implementable unitary with $$d({U}^{{\prime} },W)\le \epsilon$$ d ( U ′ , W ) ≤ ϵ </

arXiv:2110.10292•npj Quantum Information•Nov 30, 2022•34 citations
Abstract We investigate the problem of synthesizing T-depth optimal quantum circuits for exactly implementable unitaries over the Clifford+T gate set. We construct a subset, Vn{{\mathbb{V}}}_{n}Vn​ Vn , of T-depth 1 unitaries. T-depth-optimal decomposition of unitaryUis eiϕ(∏iVi)C{e}^{i\phi }\left({\prod }_{i}{V}_{i}\right)Ceiϕ(∏i​Vi​)C eiϕ∏iViC , Vi∈Vn{V}_{i}\in {{\mathbb{V}}}_{n}Vi​∈Vn​ Vi∈Vn ,Cis Clifford and ∣Vn∣ ≤ n⋅25.6n| {{\mathbb{V}}}_{n}| \,\le \,n\cdot {2}^{5.6n}∣Vn​∣≤n⋅25.6n ∣Vn∣≤n⋅25.6n . We use nested meet-in-the-middle technique to synthesize provably depth-optimal and T-depth-optimal circuits. For the latter, we achieve space and time complexity O((4n2)⌈d/c⌉)O({({4}^{{n}^{2}})}^{\lceil d/c\rceil })O((4n2)⌈d/c⌉) O((4n2)⌈d/c⌉) and O((4n2)(c−1)⌈d/c⌉)O({({4}^{{n}^{2}})}^{(c-1)\lceil d/c\rceil })O((4n2)(c−1)⌈d/c⌉) O((4n2)(c−1)⌈d/c⌉) respectively (dis the minimum T-depth,c ≥ 2 a constant). The previous best algorithm had complexity O((3n⋅2kn2)⌈d2⌉⋅2kn2)O({({3}^{n}\cdot {2}^{k{n}^{2}})}^{\lceil \frac{d}{2}\rceil }\cdot {2}^{k{n}^{2}})O((3n⋅2kn2)⌈2d​⌉⋅2kn2) O((3n⋅2kn2)⌈d2⌉⋅2kn2) (k > 2.5 a constant). We design a more efficient algorithm with space and time complexity poly(n, 25.6n, d) (or poly(nlog⁡n,25.6n,d){{{\rm{poly}}}}({n}^{\log n},{2}^{5.6n},d)poly(nlogn,25.6n,d) poly(nlogn,25.6n,d) with weaker assumptions). The claimed efficiency, optimality depends on conjectures.
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.
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.
Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems - one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy (NP), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy (Σp2). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search.
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.
We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide a significant speedup over simple brute force algorithms. As an illustration of our method, we implemented this algorithm and found factorizations of commonly used quantum logical operations into elementary gates in the Clifford+Tset. In particular, we report a decomposition of the Toffoli gate over the set of Clifford andTgates. Our decomposition achieves a totalT-depth of 3, thereby providing a 40% reduction over the previously best known decomposition for the Toffoli gate. Due to the size of the search space, the algorithm is only practical for small parameters, such as the number of qubits, and the number of gates in an optimal implementation.
Abstract We design an algorithm to determine the (minimum) T-count of any n -qubit ( n ≥ 1) unitary W of size 2 n × 2 n , over the Clifford+T gate set. The space and time complexity of our algorithm are O(22n)O\left({2}^{2n}\right)O(22n) O 2 2 n and O(22nTϵ(W)+4n)O\left({2}^{2n{{{{\mathcal{T}}}}}_{\epsilon }(W)+4n}\right)O(22nTϵ​(W)+4n) O 2 2 n T ϵ ( W ) + 4 n , respectively. Tϵ(W){{{{\mathcal{T}}}}}_{\epsilon }(W)Tϵ​(W) T ϵ ( W ) ( ϵ -T-count) is the (minimum) T-count of an exactly implementable unitary U ( T(U){{{\mathcal{T}}}}(U)T(U) T ( U ) ), such that d ( U , W ) ≤ ϵ and T(U)≤T(U′){{{\mathcal{T}}}}(U)\le {{{\mathcal{T}}}}({U}^{{\prime} })T(U)≤T(U′) T ( U ) ≤ T ( U ′ ) where U′{U}^{{\prime} }U′ U ′ is any exactly implementable unitary with d(U′,W)≤ϵd({U}^{{\prime} },W)\le \epsilond(U′,W)≤ϵ d ( U ′ , W ) ≤ ϵ </