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

By Matthew Amy, Dmitri Maslov, Michele Mosca, Martin Rötteler. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012

574 citations recorded by the source corpus.

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+T set. In particular, we report a decomposition of the Toffoli gate over the set of Clifford and T gates. Our decomposition achieves a total T-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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/e819f76fda4fe5b4419871f8f7deba76fe70d705

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning (2013, methodology): “ of our work is to optimize T-depth (circuit runtime), our algorithm also provides signiﬁcant reductions to T-count (circuit volume). Some recent work has been done concerning minimization of T-depth [2, 28], though these previous results focus on ﬁnding small optimal two- and three-qubit circuits [”
An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures (2017, background): “For the Clifford + T library, Matsumoto and Amano [12] developed a normal form for single qubit operations, which allows for a unique and T-depth optimal decomposition (approximation) of arbitrary single qubit gates (e.g., rotations) into a sequence of Clifford+T gates (up to a certain error (cid:6)”
Quantum advantage with shallow circuits (2017, methodology): “Each CCZ gate can then be decomposed exactly as a product of (a constant number of) one- and two-qubit gates from the Clifford+T gate set [36].”
Automated optimization of large quantum circuits with continuous parameters (2017, methodology): “● Third, we use a generalization of the phase polynomial representation of {CNOT, T} circuits.(39) Unlike the netlist and DAG representations, this last representation applies only to circuits consisting entirely of NOT, CNOT, and Rz gates.”
Experimental comparison of two quantum computing architectures (2017, methodology): “We rely on an optimization protocol (21) to accomplish this task for the trapped ions and CNOT + T/Z algebra (22) with further manual optimization to compose the experiments for the IBM machine (23).”
Toward the first quantum simulation with quantum speedup (2017, methodology): “s gate set an NCT circuit). Of the three basic gates used by the NCT circuits, the Toﬀoli gate is the most expensive—its best known implementation uses 6 cnotgates, 2 Hadamard gates, and 7 T/T† gates [2]—so we ﬁrst focus on optimizing the Toﬀoli gate count. We use Toﬀoli gates with controls of arbit”
Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers (2019, methodology): “Benchmarks: Table 2 lists 12 quantum programs derived from prior work on compilation and system benchmarking [2, 40, 64].”
Halving the cost of quantum addition (2017, methodology): “Existing constructions implement the Cuccaro adder’s Toffolis using 8n+O(1) T gates [3, 7, 1].”
A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery (2018, background): “There are a number of algorithms for the optimization of the T depth [27–29].”
Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer (2020, methodology): “As the distillation is resource intensive, several algorithms for the minimization of the number of non-Clifford operations can be used during compilation [141–147].”