Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1212.6253 · Quantum Information and Computation

Efficient Clifford+T approximation of single-qubit operators

Peter Selinger

Published Jan 1, 2015• 185 citations
arXivHTMLPDF

Abstract

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 $\epsilon>0$. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in $\log(1/\epsilon)$. If the operator to be approximated is a $z$-rotation, the resulting gate sequence has $T$-count $K+4\log_2(1/\epsilon)$, where $K$ is approximately equal to $10$. We also prove a worst-case lower bound of $K+4\log_2(1/\epsilon)$, 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+12\log_2(1/\epsilon)$. By contrast, the Solovay-Kitaev algorithm achieves $T$-count $O(\log^c(1/\epsilon))$, where $c$ is approximately $3.97$.

DOI
10.26421/qic15.1-2-10

Related papers

Asymptotically Optimal Approximation of Single Qubit Unitaries by Clifford and T Circuits Using a Constant Number of Ancillary Qubits

Vadym Kliuchnikov, Dmitri A Maslov, Michele Mosca

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.

arXiv:1212.0822•Physical Review Letters•May 8, 2013•146 citations

Optimal ancilla-free Clifford+T approximation of z-rotations

Neil J. Ross, Peter Selinger

We consider the problem of approximating arbitrary single-qubit z-rotations by ancillafree Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal under a mild number-theoretic hypothesis. In this case, the algorithm finds a solution of T-count m + O(log(log(1/ε))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit approximations of Tcount 3 log2 (1/ε) + O(log(log(1/ε))). Our algorithm is efficient in practice, and provably efficient under the above-mentioned number-theoretic hypothesis, in the sense that its expected runtime is O(polylog(1/ε)).

arXiv:1403.2975•Quantum Information and Computation•Sep 1, 2016•337 citations

Efficient quantum approximation : examining the efficiency of select universal gate sets in approximating 1-qubit quantum gates.

Brent A Mode

Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.

•Jan 1, 2018•1 citation

Multi-qubit controlled gate synthesis without T-count overhead in the small-error limit

Soichiro Yamazaki, Seiseki Akibue, Kaoru Sano

We study the Clifford+T synthesis of quantum multiplexers $U=\bigoplus_{i=1}^{2^n}U_i$: an $n$-qubit control register selects which single-qubit gate $U_i\in\mathrm{SU}(2)$ acts on the target qubit. For each block $U_i$, consider the minimum even T-count needed to approximate it within diamond distance $\varepsilon$ 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(\sqrt{2^n(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-δ)\log_2(1/\varepsilon)$ and $(3+δ)\log_2(1/\varepsilon)$ for every fixed $δ>0$, except with probability $O(\varepsilon^{c_{n,δ}})$ as $\varepsilon\rightarrow0$. The optimal leading coefficient is therefore the same as for a single Haar-random $\mathrm{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 $\varepsilon^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 $\mathrm{SU}(4)$ gates within diamond distance $\varepsilon$, using at most $(9+δ)\log_2(1/\varepsilon)$ $T$ gates for every fixed $δ>0$, except with probability $O(\varepsilon^{c_δ})$ with $c_δ>0$.

quant-pharXiv:2603.14202•Mar 17, 2026•1 citation

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

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 $\sqrt{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+$\sqrt{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 $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation

Diyi Liu, Shuchen Zhu, Wibe Albert de Jong +3 more

We construct Clifford+$T$ circuits implementing arbitrary $n$-qubit unitaries with worst-case $T$-count $\widetilde{O}(N^{8/7})$ at constant operator-norm error, where $N=2^n$, improving the previous exponent $5/4$. The construction uses $\widetilde{O}(N^{6/7})$ clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error $ε\in(0,1/2)$, let $L=\log_2(N/ε)$, the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using $\widetilde{O}(N^{8/7}L^{3/7}+NL)$ $T$ gates and $\widetilde{O}(N)$ clean ancillas whenever $L\le N$. We also prove that, at constant precision, the exponent $8/7$ is optimal within a sequential block-SELECT model.

quant-pharXiv:2610.18589•Oct 14, 2026•0 citations
We give an efficient randomized algorithm for approximating an arbitrary element of \SU(2)\SU(2)\SU(2) by a product of Clifford+TTT operators, up to any given error threshold ϵ>0\epsilon>0ϵ>0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log⁡(1/ϵ)\log(1/\epsilon)log(1/ϵ). If the operator to be approximated is a zzz-rotation, the resulting gate sequence has TTT-count K+4log⁡2(1/ϵ)K+4\log_2(1/\epsilon)K+4log2​(1/ϵ), where KKK is approximately equal to 101010. We also prove a worst-case lower bound of K+4log⁡2(1/ϵ)K+4\log_2(1/\epsilon)K+4log2​(1/ϵ), where K=−9K=-9K=−9, so that our algorithm is within an additive constant of optimal for certain zzz-rotations. For an arbitrary member of \SU(2)\SU(2)\SU(2), we achieve approximations with TTT-count K+12log⁡2(1/ϵ)K+12\log_2(1/\epsilon)K+12log2​(1/ϵ). By contrast, the Solovay-Kitaev algorithm achieves TTT-count O(log⁡c(1/ϵ))O(\log^c(1/\epsilon))O(logc(1/ϵ)), where ccc is approximately 3.973.973.97.
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 TTT 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.
We consider the problem of approximating arbitrary single-qubit z-rotations by ancillafree Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal under a mild number-theoretic hypothesis. In this case, the algorithm finds a solution of T-count m + O(log(log(1/ε))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit approximations of Tcount 3 log2 (1/ε) + O(log(log(1/ε))). Our algorithm is efficient in practice, and provably efficient under the above-mentioned number-theoretic hypothesis, in the sense that its expected runtime is O(polylog(1/ε)).
Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUiU=\bigoplus_{i=1}^{2^n}U_iU=⨁i=12n​Ui​: an nnn-qubit control register selects which single-qubit gate Ui∈SU(2)U_i\in\mathrm{SU}(2)Ui​∈SU(2) acts on the target qubit. For each block UiU_iUi​, consider the minimum even T-count needed to approximate it within diamond distance ε\varepsilonε without ancillae, and let mmm be the largest of these costs. For an arbitrary multiplexer UUU, we construct an approximation of UUU within the same distance using at most m+O(2n(m+1))m+O(\sqrt{2^n(m+1)})m+O(2n(m+1)​) TTT gates. With one control qubit, the cost is m+O(1)m+O(1)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 nnn and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log⁡2(1/ε)(3-δ)\log_2(1/\varepsilon)(3−δ)log2​(1/ε) and (3+δ)log⁡2(1/ε)(3+δ)\log_2(1/\varepsilon)(3+δ)log2​(1/ε) for every fixed δ>0δ>0δ>0, except with probability O(εcn,δ)O(\varepsilon^{c_{n,δ}})O(εcn,δ​) as ε→0\varepsilon\rightarrow0ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2)\mathrm{SU}(2)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\varepsilon^2ε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)\mathrm{SU}(4)SU(4) gates within diamond distance ε\varepsilonε, using at most (9+δ)log⁡2(1/ε)(9+δ)\log_2(1/\varepsilon)(9+δ)log2​(1/ε) TTT gates for every fixed δ>0δ>0δ>0, except with probability O(εcδ)O(\varepsilon^{c_δ})O(εcδ​) with cδ>0c_δ>0cδ​>0.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, 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\sqrt{T}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\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
TTT-efficient unitary synthesis via block-sparse Hamiltonian simulation
We construct Clifford+TTT circuits implementing arbitrary nnn-qubit unitaries with worst-case TTT-count O~(N8/7)\widetilde{O}(N^{8/7})O(N8/7) at constant operator-norm error, where N=2nN=2^nN=2n, improving the previous exponent 5/45/45/4. The construction uses O~(N6/7)\widetilde{O}(N^{6/7})O(N6/7) clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error ε∈(0,1/2)ε\in(0,1/2)ε∈(0,1/2), let L=log⁡2(N/ε)L=\log_2(N/ε)L=log2​(N/ε), the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using O~(N8/7L3/7+NL)\widetilde{O}(N^{8/7}L^{3/7}+NL)O(N8/7L3/7+NL) TTT gates and O~(N)\widetilde{O}(N)O(N) clean ancillas whenever L≤NL\le NL≤N. We also prove that, at constant precision, the exponent 8/78/78/7 is optimal within a sequential block-SELECT model.