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

TLDR

Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault‑tolerance. The authors propose a polynomial‑time algorithm that optimizes quantum circuits while accounting for fault‑tolerant logical gate implementations. The algorithm re‑synthesizes Clifford+T circuits, minimizing T‑count and T‑depth, and can add ancillae to further reduce T‑depth at negligible cost. Benchmarks demonstrate up to 65.7 % T‑count reduction and 87.6 % T‑depth reduction without ancillae, and 99.7 % T‑depth reduction when ancillae are used.

Abstract

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 re-synthesizes 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 re-synthesize circuits with additional ancillae to reduce T-depth at effectively no cost. 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.