We study ancilla-free approximation of single-qubit unitaries $U\in {\rm SU}(2)$ by gate sequences over Clifford+$G$, where $G\in\{T,V\}$ or their generalization. Let $p$ denote the characteristic factor of the gate set (e.g., $p=2$ for $G=T$ and $p=5$ for $G=V$). We prove three asymptotic bounds on the minimum $G$-count required to achieve approximation error at most $\varepsilon$. First, for Haar-almost every $U$, we show that $3\log_{p}(1/\varepsilon)$ $G$-count is both necessary and sufficient; moreover, probabilistic synthesis improves the leading constant to $3/2$. Second, for unitaries whose ratio of matrix elements lies in a specified number field, $4\log_p(1/\varepsilon)$ $G$-count is necessary. Again, the leading constant can be improved to $2$ by probabilistic synthesis. Third, there exist unitaries for which the $G$-count per $\log_{p}(1/\varepsilon)$ fails to converge as $\varepsilon\to 0^+$. These results partially resolve a generalized form of the Ross--Selinger conjecture.
We study ancilla-free approximation of single-qubit unitaries U∈SU(2) by gate sequences over Clifford+G, where G∈{T,V} or their generalization. Let p denote the characteristic factor of the gate set (e.g., p=2 for G=T and p=5 for G=V). We prove three asymptotic bounds on the minimum G-count required to achieve approximation error at most ε. First, for Haar-almost every U, we show that 3logp(1/ε)G-count is both necessary and sufficient; moreover, probabilistic synthesis improves the leading constant to 3/2. Second, for unitaries whose ratio of matrix elements lies in a specified number field, 4logp(1/ε)G-count is necessary. Again, the leading constant can be improved to 2 by probabilistic synthesis. Third, there exist unitaries for which the G-count per logp(1/ε) fails to converge as ε→0+. These results partially resolve a generalized form of the Ross--Selinger conjecture.
We propose two Clifford+T synthesis algorithms that are optimal with respect to T-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+T circuit with the minimum T-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+T circuits with the minimum T-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are ε−1/2−o(1) and ε−1/4−o(1), respectively, for an approximation error ε. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at ε≈10−15 and ε≈10−22, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most 3log2(1/ε)+o(log2(1/ε))T-gates, and the probabilistic synthesis algorithm requires at most 1.5log2(1/ε)+o(log2(1/ε))T-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUi: an n-qubit control register selects which single-qubit gate Ui∈SU(2) acts on the target qubit. For each block Ui, consider the minimum even T-count needed to approximate it within diamond distance ε without ancillae, and let m be the largest of these costs. For an arbitrary multiplexer U, we construct an approximation of U within the same distance using at most m+O(2n(m+1))T gates. With one control qubit, the cost is m+O(1) and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed n and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log2(1/ε) and (3+δ)log2(1/ε) for every fixed δ>0, except with probability O(εcn,δ) as ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2) gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ε2. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random SU(4) gates within diamond distance ε, using at most (9+δ)log2(1/ε)T gates for every fixed δ>0, except with probability O(εcδ) with cδ>0.
Approximate synthesis of general single-qubit unitaries over the Clifford+T gate set
For the standard Clifford+T gate set, deterministic, ancilla-free synthesis now attains the minimal T-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T gate rotates by half the angle of T, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3 to 10−8, the cost of Clifford+T circuits scales as 2.4log2(1/ε) compared to 3.0log2(1/ε) for T-count-optimal Clifford+T circuits. Once a one-time catalyst state is amortized, the Clifford+T circuits are never costlier than their Clifford+T counterparts.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0, it ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae, Hadamard and T single-qubit gates, O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(loglog(1/ε)), and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-d QAC circuit can be simulated in depth O(d) using only Hadamard, X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∈/QAC0 to proving a Parity lower bound against circuits consisting only of Hadamard, X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T gate (a T unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between n-qubit matchgate circuits and the standard representation of SO(2n), which reduces the compilation from 2n×2n unitaries to 2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n) incurred in this smaller-dimensional representation translates at most into an O(nεSO(2n)) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries U such that U⊗U∗ has entries in the ring Z[1/2,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XX Hamiltonian on n=4,8 qubits.
This paper focuses on exact synthesis of two-qubit unitaries using Clifford and T gates. We propose an ancilla-free synthesis algorithm (i) which uses T gates no more than ten times the minimum possible number of T gates, also known as the T count, and (ii) whose time complexity is linear with the T count and thus instance optimal. Our synthesis algorithm relies on a characterization of the T count of two-qubit unitaries based on Lie group homomorphism, which may be interest of its own. Precisely, we show that for any two-qubit unitary generated by Clifford and T gates, its T count is equivalent to the least denominator exponent of its SO(6) representation up to a factor of at most 10.