Unitary Synthesis with Near-Optimal T-Count for Near-Clifford Unitaries

Unitary synthesis—the process of decomposing an arbitrary quantum unitary operator into a sequence of elementary gates—is a cornerstone of quantum computing. While the Solovay-Kitaev theorem provides a general path for synthesis, the specific cost of implementing T gates (which are essential for fault-tolerant quantum computation) remains a bottleneck. This paper addresses the question: how many T gates are required to implement an arbitrary n-qubit unitary operator, particularly those that are close to the Clifford group?

Unlike previous methods that focus on direct decomposition of the unitary operator, the authors propose a Hamiltonian-based framework. They introduce a "Low T-Count Decomposition" for any Hamiltonian H, which allows the unitary U = exp(-iH) to be implemented via Hamiltonian simulation techniques, specifically the Linear-Combination-of-Unitaries (LCU) algorithm. A key technical innovation is the use of the hypercontractivity of Boolean functions to prove that any operator can be approximated as a linear combination of unitaries with a low T-count. This allows the authors to synthesize the unitary by approximating it as a series of diagonal unitaries interleaved with Hadamard gates.

The authors demonstrate that any n-qubit unitary U can be implemented to precision epsilon with a T-count of O(2^n * d_F(U) * polylog(1/epsilon)), where d_F(U) is the Frobenius norm distance to the Clifford group. This result is near-optimal for unitaries that are constantly close to the Clifford group (d_F(U) = O(1)). Furthermore, for any unitary where d_F(U) is significantly less than 2^(n/3), this method improves upon the previous best known upper bound of O(2^(4n/3)).

This work provides a significant theoretical improvement in the cost of quantum circuit synthesis. By linking the T-count directly to the distance of a unitary from the Clifford group, the authors provide a more granular understanding of circuit complexity. This is particularly relevant for fault-tolerant quantum computing, where T gates are the most expensive resource. The Hamiltonian-based approach also offers a new, flexible paradigm for circuit construction that may be applicable to other areas of quantum algorithm design.