2012/06/30 by M. Amy, Matthew Amy, D. Maslov +5 · 2 citations
Computer Science · Physics and Astronomy · #cs.ET #quant-ph
paper · pdf · doi:10.1109/tcad.2013.2244643
published as IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32(6): 818-830, 2013 · 23 pages, 15 figures, 1 table; To appear in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
arxiv created 2013/01/25 · crossref created 2013/05/15 · crossref issued 2013/06/01 · crossref published 2013/06/01 · crossref published-print 2013/06/01 · arxiv updated 2013/11/28 · crossref deposited 2021/11/29 · crossref indexed 2026/08/07
We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide a significant speed-up over simple brute force algorithms. As an illustration of our method we implemented this algorithm and found factorizations of the 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.