Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision $\ensuremath{\epsilon}$ requires $\ensuremath{\Omega}\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires $O\mathbf{(}{log}^{3+\ensuremath{\delta}}(1/\ensuremath{\epsilon})\mathbf{)}$ gates and does not use ancillae and the phase kickback approach that requires $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates but uses $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathbf{)}$ ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision $\ensuremath{\epsilon}$ using $O\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ Clifford and $T$ gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of $O\mathbf{(}{log}^{2}(1/\ensuremath{\epsilon})\mathrm{log}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ operations with integers.
Decomposing unitaries into a sequence of elementary operations is at the core of quantum computing. Information theoretic arguments show that approximating a random unitary with precision \ensuremathϵ requires \ensuremathΩ(log(1/\ensuremathϵ)) gates. Prior to our work, the state of the art in approximating a single qubit unitary included the Solovay-Kitaev algorithm that requires O(log3+\ensuremathδ(1/\ensuremathϵ)) gates and does not use ancillae and the phase kickback approach that requires O(log2(1/\ensuremathϵ)loglog(1/\ensuremathϵ)) gates but uses O(log2(1/\ensuremathϵ)) ancillae. Both algorithms feature upper bounds that are far from the information theoretic lower bound. In this Letter, we report an algorithm that saturates the lower bound, and as such it guarantees asymptotic optimality. In particular, we present an algorithm for building a circuit that approximates single qubit unitaries with precision \ensuremathϵ using O(log(1/\ensuremathϵ)) Clifford and T gates and employing up to two ancillary qubits. We connect the unitary approximation problem to the problem of constructing solutions corresponding to Lagrange's four-square theorem, and thereby develop an algorithm for computing an approximating circuit using an average of O(log2(1/\ensuremathϵ)loglog(1/\ensuremathϵ)) operations with integers.
We give an efficient randomized algorithm for approximating an arbitrary element of $\SU(2)$ by a product of Clifford+T operators, up to any given error threshold ϵ>0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/ϵ). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4log2(1/ϵ), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log2(1/ϵ), where K=−9, so that our algorithm is within an additive constant of optimal for certain z-rotations. For an arbitrary member of $\SU(2)$, we achieve approximations with T-count K+12log2(1/ϵ). By contrast, the Solovay-Kitaev algorithm achieves T-count O(logc(1/ϵ)), where c is approximately 3.97.
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.
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 describe a new method for approximating an arbitrary n qubit unitary with precision ε using a Clifford and T circuit with O(4nn(log(1/ε)+n)) gates. The method is based on rounding off a unitary to a unitary over the ring Z[i,1/2] and employing exact synthesis. We also show that any n qubit unitary over the ring Z[i,1/2] with entries of the form (a+b2+ic+id2)/2k can be exactly synthesized using O(4nnk) Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring O(32nnk) elementary gates.
We give an efficient randomized algorithm for approximating an arbitrary element of SU(2) by a product of Clifford+T operators, up to any given error threshold ε>0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/ε). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4log2(1/ε), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log2(1/ε), where K=−9, so that our algorithm is within an additive constant of optimal for certain z-rotations. For an arbitrary member of SU(2), we achieve approximations with T-count K+12log2(1/ε). By contrast, the Solovay-Kitaev algorithm achieves T-count O(logc(1/ε)), where c is approximately 3.97.
We determine the non-Clifford T-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an n-qubit operator with a clean ancillas and at most sT gates can be compressed to use at most min{a,n+2s} ancillas, without increasing the absolute error or T-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error ε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log(n4/ε)), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on n spins, we obtain independent lower bounds Ω(n) from stabilizer nullity and Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log(1/ε)). As an application, we evaluate the T-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation T-count scales as the query count times the optimal T-count per query.