Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning

By Matthew Amy, Dmitri Maslov, Michele Mosca. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013

296 citations recorded by the source corpus.

Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to resynthesize circuits with ancillae at effectively no additional cost, allowing space-time trade-offs to be easily explored. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/91c90eca57fbfb022d22c83b7a349149cfbe6512

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

t|ket⟩: a retargetable compiler for NISQ devices (2020, background): “Future versions of t | ket i will expand on this area of optimisations to cover other useful intermediate representations, including phase polynomials [38, 72], zx - diagrams [73, 65, 74], Cliﬀord tableaus [63, 75], and linear-reversible functions [76].”
Quantum computing with Qiskit (2024, background): “Particularly structured sub-circuits may also be temporarily converted to specialized data structures to facilitate reasoning about the circuit at a more abstract level, for example Boolean linear functions [71], Clif-fords [14], or phase polynomials [20] .”
Automated optimization of large quantum circuits with continuous parameters (2017, methodology): “Our algorithms are based on a carefully chosen sequence of basic optimizations, yet they achieve substantial reductions in the gate counts, improving over more mathematically sophisticated approaches such as T-par optimization.(19) The simplicity of our approach is reflected in very fast runtimes, e”