1303.2042 (Matthew Amy et al.)

Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid
Partitioning    [PDF]

Matthew Amy, Dmitri Maslov, Michele Mosca

Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. We break this trend by presenting a polynomial-time algorithm for optimizing quantum circuits while taking the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of CNOT 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-depth and T-count. The tested benchmarks show up to 99% reduction in T-depth and up to 42% reduction in T-count.

View original: http://arxiv.org/abs/1303.2042