T-Count Optimal Clifford+T Rotation Synthesis

Short answer: Clifford+T synthesis turns an arbitrary single-qubit rotation into a sequence of Clifford gates and T gates, and the T gate count is the main cost in many fault-tolerant schemes. A 2012 preprint gave an exact optimal synthesis algorithm for a class of unitaries, and a 2025 preprint reports T-count-optimal approximation algorithms with stated runtimes. Both are theoretical algorithm papers.

What is the problem?

A quantum compiler for a fault-tolerant machine must express each rotation using a small fixed gate set. The 2025 arXiv preprint states the task precisely: approximate any single-qubit unitary by a single-qubit Clifford+T circuit, ideally with the minimum T-count for a given approximation error.

What did the 2012 paper show?

The 2012 arXiv preprint, listed with a Quantum Information and Computation 2013 journal reference, shows an equivalence in the single-qubit case between the set of unitaries computable by circuits over the Clifford and T library and the set of unitaries over a specific ring, Z[1/sqrt(2), i]. The authors report an efficient synthesis algorithm with an exact optimality guarantee on the number of Hadamard and T gates used. They conjecture that the same equivalence holds for n qubits, so the multi-qubit case is stated as a conjecture and not a result.

What did the 2025 preprint add?

The authors propose two Clifford+T synthesis algorithms that are optimal with respect to T-count. Deterministic synthesis approximates any single-qubit unitary by a Clifford+T circuit with the minimum T-count. Probabilistic synthesis approximates it by a probabilistic mixture of Clifford+T circuits with the minimum T-count. For most single-qubit unitaries they give runtimes scaling as epsilon to the power of minus one half minus o(1) for deterministic synthesis and epsilon to the power of minus one quarter minus o(1) for probabilistic synthesis, where epsilon is the approximation error. They note this is exponential in the input size, but say the algorithms run in practical time at epsilon about 10^-15 and 10^-22 respectively. They also show that for most unitaries deterministic synthesis needs at most 3 log2(1/epsilon) plus lower-order T gates, and probabilistic synthesis at most 1.5 log2(1/epsilon) plus lower-order T gates. They state that their complexity analyses do not rely on numerical or number-theoretic conjectures.

How to read this

The two papers are 13 years apart and describe different settings, exact synthesis in the first and approximate synthesis in the second, so their results should not be compared as a single series. Both are arXiv preprints at the version read here, and the abstracts are their authors' claims. A third listed source, an arXiv paper from 2012, returned no readable text, so nothing is claimed from it. This post is based on abstracts and visible summary text only, and it makes no claim about built quantum computers.

FAQ

What is T-count and why does it matter?

The number of T gates in a circuit. The 2025 preprint optimizes it, which signals that it is the quantity being minimized in these synthesis problems.

Is the 2012 result exact?

For single-qubit unitaries over the stated ring, the authors give an exact optimality guarantee on Hadamard and T gate counts.

What does probabilistic synthesis give?

A mixture of circuits, with the 2025 preprint reporting a bound of 1.5 log2(1/epsilon) T gates for most unitaries.

Does it extend to many qubits?

The 2012 authors conjecture the equivalence holds for n qubits. The abstract does not prove it.