Optimizing Non-Clifford Gate Synthesis via Quasiprobability Methods for Early Fault-Tolerant Quantum Computing

The T gate is indispensable for universality but difficult to implement fault-tolerantly, leading to large overheads for a fault-tolerant quantum computer (FTQC). Considerable research has therefore focused on optimizing T-count decompositions, such as synthesis of Z rotations with minimum T counts. While these scalable approaches are effective for an arbitrary quantum circuit, alternative strategies may be more suitable in the early fault-tolerant quantum computing (early FTQC) regime, where number of non-Clifford operations are limited.

We propose a method to optimize the decomposition of non-Clifford gates using the quasiprobability approach originally developed for error mitigation. Since the number of non-Clifford gates constructible with up to k T gates grows exponentially with k, we identify those that most effectively reduce the L1 norm of the decomposition, which determines sampling cost. We show that nearly optimal L1 norms can be achieved with a drastically smaller subset of gates.

Numerical simulations confirm that our quasiprobability-based approach significantly reduces both T-count and circuit depth when the number of available Z-rotation gates is restricted. This method offers a promising path to lowering implementation costs in the early FTQC era, where T-gate overhead is a key bottleneck.