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:1403.2975 · Quantum Information and Computation

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

Neil J. Ross, Peter Selinger

Published Sep 1, 2016• 337 citations
arXivHTMLPDF

Abstract

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/ε)).

DOI
10.26421/qic16.11-12-1

Related papers

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

Neil J. Ross

We describe a new efficient algorithm to approximate $z$-rotations by ancilla-free Clifford+$V$ circuits, up to a given precision $\epsilon$. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+$V$ circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of $V$\!-count $m + O(\log(\log(1/\epsilon)))$, where $m$ is the $V$\!-count of the third-to-optimal solution. A restricted version of the algorithm approximates $z$-rotations in the Pauli+$V$ gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of $z$-rotations using Clifford+$T$ gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of $z$-rotations using Clifford+$V$ gates.

arXiv:1409.4355•Quantum Information and Computation•Sep 1, 2015•102 citations

Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries

Hayata Morisaki, Sano, Kaoru, Seiseki Akibue

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 $\varepsilon^{-1/2 - o(1)}$ and $\varepsilon^{-1/4 - o(1)}$, respectively, for an approximation error $\varepsilon$. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at $\varepsilon \approx 10^{-15}$ and $\varepsilon \approx 10^{-22}$, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most $3\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))$ $T$-gates, and the probabilistic synthesis algorithm requires at most $1.5\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))$ $T$-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.

arXiv:2510.05816•Oct 7, 2025•11 citations

pygridsynth: A fast numerical tool for ancilla-free Clifford+T synthesis

Shuntaro Yamamoto, Nobuyuki Yoshioka

We present pygridsynth, an open-source Python library for ancilla-free approximate Clifford+$T$ synthesis that runs in $O(\log(1/ε))$ for precision $ε$. For $n=1, 2$ qubits, the library builds upon established efficient and high-precision synthesis routines, such as nearly optimal $Z$-rotation synthesis and magnitude approximation. For $n\ge 3$ qubits, we introduce a partial-decomposition technique that generalizes the magnitude approximation, reducing constant factors in the $T$-count as $(\frac{21}{8}\cdot 4^n - \frac{9}{2}\cdot 2^n + 9)\log_2(1/ε) + o(\log(1/ε))$. The package also exposes a mixed-synthesis workflow that approximates target unitary channels by probabilistic mixtures of Clifford+$T$ circuits, for which we empirically find that the synthesis error is reduced from $ε$ to $ε^2/(2n)$. Taken together, these features make pygridsynth a Python-native platform for high-precision Clifford$+T$ synthesis and for benchmarking unitary and mixed synthesis strategies on multi-qubit instances.

quant-pharXiv:2604.21333•Apr 24, 2026•4 citations

Efficient Clifford+T approximation of single-qubit operators

Peter Selinger

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$.

arXiv:1212.6253•Quantum Information and Computation•Jan 1, 2015•185 citations

Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth

Christoffer Hindlycke, Jan-Åke Larsson

Building generic gates from a restricted gate set is a difficult but important problem, especially in the noisy regime where only a limited set of noise-resistant gates are available, e.g., fault-tolerant Clifford gates (generated by Hadamard, phase, and gates) and fault-tolerant Toffoli gates. The Toffoli is also often used as a building block of many algorithms and will need to be constructed if not directly available. This makes Clifford + Toffoli an attractive gate set for building generic gates. In this Letter we give a simple and efficient algorithm for building an approximate single-qubit rotation using only Clifford + Toffoli , which in turn enables any generic single-qubit unitary. An important difference compared to earlier attempts is that the use of the Toffoli allows us to use simple rounding as opposed to a complicated approximation algorithm. The resulting gate array does not rely on repeatedly applying a fixed rotation, but immediately applies a rotation R θ * that is ε -close to the desired rotation R θ , with a success probability strictly greater than 1 / 2 . It can be rerun upon failure, giving an expected number of repetitions strictly less than 2, an expected Toffoli count strictly less than 4 ⌈ log 1 ε ⌉ , an expected gate depth strictly less than 4 ⌈ log 1 ε ⌉ + 6 , and uses 2 ⌈ log 1 ε ⌉ ancillas. The small circuit depth of our construction enables low-noise gates on existing quantum computational devices, and allows for arbitrary precision using a very modest number of ancillas. Published by the American Physical Society 2024

arXiv:2404.05618•Physical Review Research•Oct 28, 2024•4 citations

Optimal Approximation of Single Qubit Rotations within a Quantum Circuit

Gilad Kishony, Avi Elazari, Ron Cohen +1 more

Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T. As a baseline, Diagonal approximation can be used for synthesizing single-qubit Pauli rotations, yielding an approximating sequence with $T$-count that equals $3 \log_2(1/ε)$ for a target precision $ε$. Magnitude Approximation can reduce the $T$-count to only $1 \log_2(1/ε)$ by allowing large residual errors, which are rotations about orthogonal axes. Within a complete quantum circuit, these residual errors can then be absorbed into neighboring gates before they are approximated themselves. Determining the optimal allocation of approximation strategies within a large, multi-qubit circuit presents a significant combinatorial challenge. In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem. We demonstrate that the issue of delegating Magnitude versus Diagonal approximation across a circuit maps formally to a classical 1D Ising model with a spatially varying field. By minimizing the energy of this Hamiltonian, we identify the optimal approximation configuration for each rotation without exponential overhead. Benchmarking our method against standard diagonal approximation on random quantum circuits, we observe an average reduction of 26\% in the total approximating circuit gate count, offering a significant efficiency gain for the implementation of quantum algorithms on near-term and fault-tolerant architectures.

quant-pharXiv:2605.09671•May 12, 2026•0 citations
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/ε)).
We describe a new efficient algorithm to approximate zzz-rotations by ancilla-free Clifford+VVV circuits, up to a given precision ϵ\epsilonϵ. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+VVV circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of VVV\!-count m+O(log⁡(log⁡(1/ϵ)))m + O(\log(\log(1/\epsilon)))m+O(log(log(1/ϵ))), where mmm is the VVV\!-count of the third-to-optimal solution. A restricted version of the algorithm approximates zzz-rotations in the Pauli+VVV gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of zzz-rotations using Clifford+TTT gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of zzz-rotations using Clifford+VVV gates.
We propose two Clifford+TTT synthesis algorithms that are optimal with respect to TTT-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+TTT circuit with the minimum TTT-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+TTT circuits with the minimum TTT-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are ε−1/2−o(1)\varepsilon^{-1/2 - o(1)}ε−1/2−o(1) and ε−1/4−o(1)\varepsilon^{-1/4 - o(1)}ε−1/4−o(1), respectively, for an approximation error ε\varepsilonε. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at ε≈10−15\varepsilon \approx 10^{-15}ε≈10−15 and ε≈10−22\varepsilon \approx 10^{-22}ε≈10−22, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most 3log⁡2(1/ε)+o(log⁡2(1/ε))3\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))3log2​(1/ε)+o(log2​(1/ε)) TTT-gates, and the probabilistic synthesis algorithm requires at most 1.5log⁡2(1/ε)+o(log⁡2(1/ε))1.5\log_2(1/\varepsilon) + o(\log_2(1/\varepsilon))1.5log2​(1/ε)+o(log2​(1/ε)) TTT-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.
We present pygridsynth, an open-source Python library for ancilla-free approximate Clifford+TTT synthesis that runs in O(log⁡(1/ε))O(\log(1/ε))O(log(1/ε)) for precision εεε. For n=1,2n=1, 2n=1,2 qubits, the library builds upon established efficient and high-precision synthesis routines, such as nearly optimal ZZZ-rotation synthesis and magnitude approximation. For n≥3n\ge 3n≥3 qubits, we introduce a partial-decomposition technique that generalizes the magnitude approximation, reducing constant factors in the TTT-count as (218⋅4n−92⋅2n+9)log⁡2(1/ε)+o(log⁡(1/ε))(\frac{21}{8}\cdot 4^n - \frac{9}{2}\cdot 2^n + 9)\log_2(1/ε) + o(\log(1/ε))(821​⋅4n−29​⋅2n+9)log2​(1/ε)+o(log(1/ε)). The package also exposes a mixed-synthesis workflow that approximates target unitary channels by probabilistic mixtures of Clifford+TTT circuits, for which we empirically find that the synthesis error is reduced from εεε to ε2/(2n)ε^2/(2n)ε2/(2n). Taken together, these features make pygridsynth a Python-native platform for high-precision Clifford+T+T+T synthesis and for benchmarking unitary and mixed synthesis strategies on multi-qubit instances.
We give an efficient randomized algorithm for approximating an arbitrary element of $\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)$, 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.
Building generic gates from a restricted gate set is a difficult but important problem, especially in the noisy regime where only a limited set of noise-resistant gates are available, e.g., fault-tolerant Clifford gates (generated by Hadamard, phase, and gates) and fault-tolerant Toffoli gates. The Toffoli is also often used as a building block of many algorithms and will need to be constructed if not directly available. This makes Clifford + Toffoli an attractive gate set for building generic gates. In this Letter we give a simple and efficient algorithm for building an approximate single-qubit rotation using only Clifford + Toffoli , which in turn enables any generic single-qubit unitary. An important difference compared to earlier attempts is that the use of the Toffoli allows us to use simple rounding as opposed to a complicated approximation algorithm. The resulting gate array does not rely on repeatedly applying a fixed rotation, but immediately applies a rotation R θ * that is ε -close to the desired rotation R θ , with a success probability strictly greater than 1 / 2 . It can be rerun upon failure, giving an expected number of repetitions strictly less than 2, an expected Toffoli count strictly less than 4 ⌈ log 1 ε ⌉ , an expected gate depth strictly less than 4 ⌈ log 1 ε ⌉ + 6 , and uses 2 ⌈ log 1 ε ⌉ ancillas. The small circuit depth of our construction enables low-noise gates on existing quantum computational devices, and allows for arbitrary precision using a very modest number of ancillas. Published by the American Physical Society 2024
Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T. As a baseline, Diagonal approximation can be used for synthesizing single-qubit Pauli rotations, yielding an approximating sequence with TTT-count that equals 3log⁡2(1/ε)3 \log_2(1/ε)3log2​(1/ε) for a target precision εεε. Magnitude Approximation can reduce the TTT-count to only 1log⁡2(1/ε)1 \log_2(1/ε)1log2​(1/ε) by allowing large residual errors, which are rotations about orthogonal axes. Within a complete quantum circuit, these residual errors can then be absorbed into neighboring gates before they are approximated themselves. Determining the optimal allocation of approximation strategies within a large, multi-qubit circuit presents a significant combinatorial challenge. In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem. We demonstrate that the issue of delegating Magnitude versus Diagonal approximation across a circuit maps formally to a classical 1D Ising model with a spatially varying field. By minimizing the energy of this Hamiltonian, we identify the optimal approximation configuration for each rotation without exponential overhead. Benchmarking our method against standard diagonal approximation on random quantum circuits, we observe an average reduction of 26\% in the total approximating circuit gate count, offering a significant efficiency gain for the implementation of quantum algorithms on near-term and fault-tolerant architectures.