Source-linked AI summary
Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
Matthew Amy, Dmitri Maslov, Michele Mosca
TL;DR
Quantum circuit optimization has often been separated from fault-tolerant implementation costs, despite T gates being expensive and runtime-sensitive. The paper introduces a polynomial-time Clifford+T re-synthesis algorithm using matroid partitioning and optional ancillae, achieving substantial reductions in T-count and T-depth on benchmarks. Its method does not necessarily find globally optimal T-count or T-depth, and linear reversible re-synthesis can increase CNOT count or depth.
Problem
Prior circuit-optimization work was largely isolated from fault-tolerance, even though T gates are much more costly than Clifford gates and T-depth determines runtime.
Method
The algorithm represents Clifford+T circuits with linear Boolean functions and phase polynomials, then combines and parallelizes T gates through matroid partitioning, with optional ancillae.
Results
Benchmarks report up to 65.7% T-count reduction, up to 87.6% T-depth reduction without ancillae, and up to 99.7% T-depth reduction with ancillae.
Takeaways & Limitations
The approach provides a scalable tool for exploring the trade-off between ancilla usage and T-depth in fault-tolerant circuit design.
Takeaways & Limitations
Matroid-based parallelization does not necessarily find optimal T-count, and Gaussian-elimination synthesis may increase CNOT count or depth.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets quantum circuit optimization that accounts for fault-tolerant gate costs, especially the high cost and limited parallelism of T gates. It presents a scalable polynomial-time optimizer for Clifford+T circuits, with optional ancillae for further T-depth reduction.
- Fault-tolerant quantum computing motivates automated circuit-design tools because scalable computation requires error correction and sufficiently reliable physical operations.
- Clifford gates are comparatively inexpensive in common CSS-code models, whereas fault-tolerant T gates can cost 100 times more or more.
- T-count measures the number of T gates, while T-depth measures the number of sequential T-gate layers and directly determines runtime.
- Previous T-depth work focused on small two- and three-qubit circuits or specific ancilla-assisted classes, rather than general scalable optimization.
- The paper presents a polynomial-time algorithm that optimizes both T-count and T-depth, with automatic ancilla use for T-depth optimization.
2 Preliminaries
The preliminaries represent reversible and quantum computations using binary linear functions, reversible maps, ancillae, and phase-based circuit descriptions. They establish rank-based conditions for simultaneous computability and reversible synthesis.
- Binary strings form vectors over F2, where addition is exclusive-OR and multiplication is Boolean AND.
- Quantum states use computational-basis vectors in a 2^n-dimensional complex space, and quantum gates are unitary operators.
- Ancillae are temporary bits or qubits initialized to 0 or |0⟩; with n total bits and m data bits, n−m are ancillae.
- Linear reversible functions are exactly those computable using CNOT gates, while the Clifford+T set {H, CNOT, T} is universal for quantum computation.
- Computable sets of linear Boolean functions: A set of n linear Boolean functions defines a reversible function exactly when its rank equals the input-space dimension.
- Computable sets of linear Boolean functions: When fewer than n functions are specified, a linear reversible circuit computes them exactly when they can be extended to a computable superset of n functions.
3 {CNOT, T} circuits
The paper characterizes {CNOT, T} circuits by linear reversible functions and phase polynomials, then optimizes T-depth through computable partitions while accounting for equivalent phase representations and ancillae.
- Circuit representation: {CNOT, T} circuits implement linear reversible functions with phases represented by weighted linear Boolean functions over eighth roots of unity.The representation uses coefficients in Z8 and an associated linear reversible output function.
- Circuit representation: S and g can be computed in time linear in the number of qubits and gates, revealing T gates that combine into Clifford phase gates or cancel.Physically separated T gates acting on the same value can be replaced by a phase gate or removed.
- T-depth optimization: Naive re-synthesis implements the characterized unitary constructively but can increase T-depth despite reducing T-count.The optimization therefore partitions phase terms into reversibly computable subsets whose phase factors can be applied in parallel.
- T-depth optimization: The minimum number of computable subsets partitioning the odd-coefficient phase terms equals the minimum T-depth for a fixed phase representation.Terms with even coefficients require no T gates, and each computable partition has T-depth at most 1.
- T-count optimization: Equivalent phase representations can reduce T-count beyond maximal parallelization, including removal of all 15 T gates from a trivial-phase representation.For n < 4, brute force shows distinct T-counts do not define equivalent computations; the doubly controlled-Z gate requires 7 T gates with any number of ancillae.
- Ancilla-assisted parallelization: One ancilla enables computing x1 ⊕x2 ⊕x3 and applying four T gates simultaneously, producing a T-depth 2 implementation of the doubly controlled-Z gate.The ancilla-assisted construction satisfies the reversibility condition used for computable partitions.
4 Matroids
The paper formulates partitioning linear Boolean phase factors as matroid partitioning, exploiting independence to optimize T-gate parallelization in polynomial time. An Edmonds-based augmenting-path algorithm incrementally maintains minimal partitions.
- Matroid formulation: Matroid partitioning groups phase factors into the fewest independent, computable subsets.The independence relation for linear Boolean functions forms a finite matroid, making minimal partitioning a matroid problem.
- Algorithmic tractability: Polynomial-time optimization follows because matroid partitioning uses an independence oracle implemented by Gaussian elimination.The independence test takes O(n^3) time under the paper’s simple bound.
- Matroid partitioning algorithm: An augmenting path from the new element to an existing partition updates memberships while preserving independence.If no such path exists, the element forms a new subset; breadth-first search finds the path without explicitly constructing the graph.
- Complexity: The full partitioning algorithm runs in O(|S|^3 · n^3) time under the stated independence-test bound.A breadth-first search iteration requires O(|S′|^2 · n^3 + |S′|) time.
5 Extending to a universal gate set
Because {CNOT, T} circuits cannot create superpositions or interference, the paper extends phase-polynomial re-synthesis to {H, CNOT, T}. The extension tracks changing state spaces and uses a heuristic partitioning procedure that remains minimal for currently computable functions.
- Universal gate-set extension: The {CNOT, T} optimizer is extended to the universal gate set {H, CNOT, T}.The restricted core does not create superpositions or interference between basis states.
- Circuit representation: Hadamard gates replace qubit values with path variables, allowing {H, CNOT, T} circuits to be represented by phase polynomials and linear Boolean outputs.Each Hadamard contributes a path variable to the representation.
- State-space management: Re-synthesis must place phase terms between Hadamard gates while preserving suitable state spaces for later outputs.Hadamards destroy values and create new ones, changing the relevant subspace.
- Heuristic extension: The universal-gate extension is heuristic, but its partition is minimal for the functions computable in the current state space.When the state-space dimension increases, dependent elements can be removed to restore independence while maintaining minimality.
6 The Tpar algorithm
Tpar represents Clifford + T circuits symbolically, partitions computable phase functions across Hadamard-separated regions, and synthesizes equivalent circuits with parallelized T gates. Its partitioning core uses matroid independence and Gaussian elimination, while the full procedure extends the approach heuristically to universal circuits.
- Circuit representation: Tpar represents a Clifford + T circuit as phase factors, qubit states, and Hadamard input-output states, updating this triple gate by gate.The phase factors are stored as linear Boolean functions with coefficients in Z8, while Q tracks qubit states and H records Hadamard boundaries.
- Partitioning: Tpar iterates through Hadamard gates while maintaining a partition of phase functions computable in the current subcircuit.For each Hadamard boundary, functions are tested for membership in the span of the input-state basis and added to the current partition when computable.
- Synthesis: Each partition is synthesized by computing a reversible superset with CNOT and X gates, applying corresponding Z, P, and T phases, and reversing the basis transformation.When input and output states differ, Hadamard-related transformations complete the synthesized circuit around these phase stages.
- Partitioning: Matroid partitioning yields a minimal partition in polynomial time because independence is checked through Gaussian-elimination rank computations.The independence condition can be evaluated in O(n^3) time, and matroid partitioning is polynomial-time given an independence oracle.
- Synthesis: The synthesized partition circuits have T-depth 1, while the full algorithm extends the {CNOT, T} core to Clifford + T circuits using a heuristic around Hadamard gates.The paper presents Tpar as the concrete algorithm after describing the heuristic extension and includes Pauli gates in the supported gate set.
- Practical considerations: Gaussian-elimination synthesis can increase CNOT count or depth, so the authors identify linear-reversible and Clifford-subcircuit optimization as a practical second-order improvement.They recommend using more advanced linear-reversible synthesis algorithms in practical implementations but do not pursue that optimization here.
7 Results
Experiments on arithmetic and reversible benchmarks show substantial T-count and T-depth reductions, including stronger depth improvements when ancillae are available. The implementation scales to circuits with hundreds of qubits and reproduces several earlier low-depth constructions.
- Experimental setup: The evaluation uses arithmetic and reversible circuits over a fault-tolerant universal gate set, with baseline T-depths formed by hand-parallelizing T and Toffoli gates.Table 2 compares optimization with 0, n, or unlimited ancillae, where n is the original qubit count.
- No-ancilla results: 39.9% average T-count reduction and 54.3% average T-depth reduction are obtained across all tested benchmarks without extra ancillae.The largest reductions occur for circuits whose adjacent Toffoli gates share controls or targets, enabling phase cancellations.
- Ancilla-assisted results: Any GF(2^m) multiplication circuit can be parallelized to T-depth 2 with sufficiently many ancillae under Tpar.The result follows from two Toffoli stages that become one {CNOT, T} stage each after re-synthesis.
- Benchmark variation: Hadamard gates limit T parallelization in circuits that mix controls and targets between adjacent Toffoli gates, making those benchmarks less affected.The Hadamard gates act as barriers between phase-parallelization opportunities.
- Scalability: The largest tested circuit contains 192 qubits, 28,672 T gates, and 8,192 Hadamard gates, demonstrating scaling beyond small circuits.The reported runtimes are described as scaling well to large circuits compared with previous optimization efforts.
- Ancilla trade-offs: Adding ancillae generally decreases runtime through fewer partitions and faster matroid partitioning, exposing a space-time trade-off.The experiments compare n-ancilla and minimum-achievable-depth settings to illustrate this flexibility.
- Related constructions: Tpar reproduces a T-depth 1 Toffoli, reduces controlled-T depth from 5 to 3 with one ancilla, and re-synthesizes a Λ3(X) implementation without ancillae.These constructions are presented as reproductions or extensions of earlier low-depth results.
8 Conclusion
The paper presents a re-synthesis algorithm that reduces T-count and T-depth in Clifford + T circuits by combining phase terms and parallelizing T gates through matroid partitioning. Benchmarks demonstrate substantial reductions, with further T-depth savings available through ancillae, while efficient linear reversible synthesis remains future work.
- Algorithm and scope: The algorithm represents circuits with linear Boolean functions, combines T gates, and parallelizes them using matroid partitioning.Its worst-case runtime is cubic in the number of T gates, qubits, and Hadamard gates, yet experiments indicate practical circuit sizes are tractable.
- Benchmark results: 65.7% maximum T-count reduction and 87.6% maximum T-depth reduction were achieved without ancillae in the benchmarks.These reductions are reported across the benchmark circuits summarized in Tables 1 and 2.
- Benchmark results: Unbounded ancillae reduced GF(2^m)-Mult T-depth from 12(m −1) to a constant of 2.The benchmarks also show that ancillae can further parallelize T gates and support trade-offs between ancilla usage and T-depth.
- Implications and future work: The approach directly links reducing terms in mixed arithmetic phase polynomials with reducing circuit T-complexity, including T-count minimization for {CNOT, T} circuits.The paper identifies optimization over more general phases, gate sets, and cost metrics as future research directions.
- Implications and future work: Efficient practical synthesis of linear reversible circuits remains an important open direction because Gaussian-elimination synthesis can increase CNOT counts after re-synthesis.Existing algorithms are cited as producing more efficient gate counts or depth for linear reversible functions.
- Illustrative example: The worked example reduces T-count from 14 to 12 and T-depth from 6 to 4.The displayed circuit uses minimal illustrative partitions, although they are not the partitions produced by Algorithm 1.