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:1206.0758 · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

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

Matthew Amy, D. Maslov, Michele Mosca, Martin Roetteler

Published May 15, 2013• 548 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tcad.2013.2244643

Related papers

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

Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

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.

arXiv:2101.03142•npj Quantum Information•Sep 13, 2022•16 citations

Optimal Multi-Bit Toffoli Gate Synthesis

Young-Min Jun, In-Chan Choi

Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.

IEEE Access•Jan 1, 2023•3 citations

Pairwise decomposition of toffoli gates in a quantum circuit

Nathan O. Scott, Gerhard W. Dueck

Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•May 4, 2008•13 citations

High-Performance Exact Synthesis of Two-Qubit Quantum Circuits

Andrew N. Glaudell, Michael Jarret, Swan Klein +3 more

Exact synthesis provides unconditional optimality and canonical structure, but is often limited to small, carefully scoped regimes. We present an exact synthesis framework for two-qubit circuits over the Clifford+$T$ gate set that optimizes $T$-count exactly. Our approach exhausts a bounded search space, exploits algebraic canonicalization to avoid redundancy, and constructs a lookup table of optimal implementations that turns synthesis into a query. Algorithmically, we combine meet-in-the-middle ideas with provable pruning rules and problem-specific arithmetic designed for modern hardware. The result is an exact, reusable synthesis engine with substantially improved practical performance.

quant-pharXiv:2601.19166•Jan 28, 2026•0 citations

Algorithms for the Optimization of Quantum Circuits

Matthew Amy

This thesis investigates techniques for the automated optimization of quantum circuits. In the first part we develop an exponential time algorithm for synthesizing minimal depth quantum circuits. We combine this with effective heuristics for reducing the search space, and show how it can be extended to different optimization problems. We then use the algorithm to compute circuits over the Clifford group and T gate for many of the commonly used quantum gates, improving upon the former best known circuits in many cases. \n \nIn the second part, we present a polynomial time algorithm for the re-synthesis of CNOT and T gate circuits while reducing the number of phase gates and parallelizing them. We then describe different methods for expanding this algorithm to optimize circuits over Clifford and T gates.

•Aug 30, 2013•53 citations

Technology Mapping of Reversible Circuits to Clifford+T Quantum Circuits

Nabila Abdessaied, Matthew Amy, Mathias Soeken +1 more

The Clifford+T quantum gate library has attracted much interest in the design of quantum circuits, particularly since the contained operations can be implemented in a fault-tolerant manner. Since fault tolerant implementations of the T gate have very high latency, synthesis and optimization are aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to map mixed polarity multiple controlled Toffoli gates into Clifford+T quantum circuits. Our approach is based on the multiple control Toffoli mapping algorithms proposed by Barenco et al., which are given T-depth optimized Clifford+T translations. Experiments show that our approach leads to a significant T-depth reduction of 54% on average.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2016•48 citations
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 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.
Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.
Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.
Exact synthesis provides unconditional optimality and canonical structure, but is often limited to small, carefully scoped regimes. We present an exact synthesis framework for two-qubit circuits over the Clifford+TTT gate set that optimizes TTT-count exactly. Our approach exhausts a bounded search space, exploits algebraic canonicalization to avoid redundancy, and constructs a lookup table of optimal implementations that turns synthesis into a query. Algorithmically, we combine meet-in-the-middle ideas with provable pruning rules and problem-specific arithmetic designed for modern hardware. The result is an exact, reusable synthesis engine with substantially improved practical performance.
This thesis investigates techniques for the automated optimization of quantum circuits. In the first part we develop an exponential time algorithm for synthesizing minimal depth quantum circuits. We combine this with effective heuristics for reducing the search space, and show how it can be extended to different optimization problems. We then use the algorithm to compute circuits over the Clifford group and T gate for many of the commonly used quantum gates, improving upon the former best known circuits in many cases. \n \nIn the second part, we present a polynomial time algorithm for the re-synthesis of CNOT and T gate circuits while reducing the number of phase gates and parallelizing them. We then describe different methods for expanding this algorithm to optimize circuits over Clifford and T gates.
The Clifford+T quantum gate library has attracted much interest in the design of quantum circuits, particularly since the contained operations can be implemented in a fault-tolerant manner. Since fault tolerant implementations of the T gate have very high latency, synthesis and optimization are aiming at minimizing the number of T stages, referred to as the T-depth. In this paper, we present an approach to map mixed polarity multiple controlled Toffoli gates into Clifford+T quantum circuits. Our approach is based on the multiple control Toffoli mapping algorithms proposed by Barenco et al., which are given T-depth optimized Clifford+T translations. Experiments show that our approach leads to a significant T-depth reduction of 54% on average.