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:2404.05618 · Physical Review Research

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

Christoffer Hindlycke, Jan-Åke Larsson

Published Oct 28, 2024• 4 citations
arXivHTMLPDF

Abstract

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

DOI
10.1103/physrevresearch.6.l042027

Related papers

Any Clifford+T circuit can be controlled with constant T-depth overhead

Isaac H. Kim, Tuomas Laakkonen

Since an n-qubit circuit consisting of CNOT gates can have up to $Ω(n^2/\log{n})$ CNOT gates, it is natural to expect that $Ω(n^2/\log{n})$ Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision $ε$ in T-depth exactly 1 using a universal $\lceil\log_2(8/ε)\rceil$-qubit catalyst state.

quant-pharXiv:2512.24982•Jan 1, 2026•6 citations

Practical implementation of Toffoli-based qubit rotation

Christoffer Hindlycke, Jakov Krnic, Jan-Åke Larsson

The Toffoli gate is an important universal quantum gate, and will alongside the Clifford gates be available in future fault-tolerant quantum computing hardware. Many quantum algorithms rely on performing arbitrarily small single-qubit rotations for their function, and these rotations may also be used to construct any unitary from a limited (but universal) gate set. How to carry out such rotations is then of significant interest. In this work, we evaluate the performance of a recently proposed single-qubit rotation algorithm using the Clifford plus Toffoli gate set by implementation of a one-shot version on both a real and a simulated quantum computer. We test the algorithm under various simulated noise levels using a per-qubit depolarizing error noise model and examine how the probabilities and process fidelities are affected. We then conduct live runs and find that the results reasonably match the simulated results. We also attempt to model the hardware noise by combining a number of noise models, matching the results to results of the live runs to approximate the hardware noise. Our results suggest that the algorithm will perform well for up to 1 % noise under the noise models we chose. We further posit the use of our algorithm as a benchmark for quantum processing units, given that it has a low complexity that is easy to fine-tune in small steps. We provide details for how to do this.

arXiv:2410.18746•Physical Review Applied•Dec 10, 2025•0 citations

Approximate quantum Fourier transform with O(n log(n)) T gates

Yunseong Nam, Yuan Su, Dmitri A Maslov

Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of $$O(n\,{\mathrm{log}}^{2}\,(n))$$ O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of $$O(n\,{\mathrm{log}}\,(n))$$ O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

arXiv:1803.04933•npj Quantum Information•Mar 13, 2020•122 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

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 $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-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(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-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$\notin$QAC$^0$ 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.

quant-pharXiv:2609.34659•Sep 29, 2026•1 citation

Shorter quantum circuits via single-qubit gate approximation

Vadym Kliuchnikov, Kristin Lauter, Romy Minko +2 more

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ⁡ ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ⁡ ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ T gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.

arXiv:2203.10064•Quantum•Dec 18, 2023•61 citations

Pseudorandom circuits from Clifford-plus- T gates

Yaakov S. Weinstein

We explore the implementation of pseudorandom single-qubit rotations and multiqubit pseudorandom circuits constructed only from Clifford gates and the $T$ gate, a phase rotation of $\ensuremath{\pi}/4$. Such a gate set would be appropriate for computations performed in a fault tolerant setting. For single-qubit rotations the distribution of parameters found for unitaries constructed from Clifford plus $T$ quickly approaches that of random rotations and requires significantly fewer gates than the construction of arbitrary single-qubit rotations. For Clifford-plus-$T$ pseudorandom circuits we find an exponential convergence to a random matrix element distribution and a Gaussian convergence to the higher-order moments of the matrix element distribution. In addition, the nearest-neighbor eigenangle statistics distribution almost immediately converges to that of random unitary matrices. All of these convergence rates are found to be insensitive to the number of qubits.

arXiv:1309.3943•Physical Review A•Dec 2, 2013•4 citations
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
Since an n-qubit circuit consisting of CNOT gates can have up to Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) CNOT gates, it is natural to expect that Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision εεε in T-depth exactly 1 using a universal ⌈log⁡2(8/ε)⌉\lceil\log_2(8/ε)\rceil⌈log2​(8/ε)⌉-qubit catalyst state.
The Toffoli gate is an important universal quantum gate, and will alongside the Clifford gates be available in future fault-tolerant quantum computing hardware. Many quantum algorithms rely on performing arbitrarily small single-qubit rotations for their function, and these rotations may also be used to construct any unitary from a limited (but universal) gate set. How to carry out such rotations is then of significant interest. In this work, we evaluate the performance of a recently proposed single-qubit rotation algorithm using the Clifford plus Toffoli gate set by implementation of a one-shot version on both a real and a simulated quantum computer. We test the algorithm under various simulated noise levels using a per-qubit depolarizing error noise model and examine how the probabilities and process fidelities are affected. We then conduct live runs and find that the results reasonably match the simulated results. We also attempt to model the hardware noise by combining a number of noise models, matching the results to results of the live runs to approximate the hardware noise. Our results suggest that the algorithm will perform well for up to 1 % noise under the noise models we chose. We further posit the use of our algorithm as a benchmark for quantum processing units, given that it has a low complexity that is easy to fine-tune in small steps. We provide details for how to do this.
Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of O(n log2 (n))O(n\,{\mathrm{log}}^{2}\,(n))O(nlog2(n)) O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of O(n log (n))O(n\,{\mathrm{log}}\,(n))O(nlog(n)) O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.
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δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(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-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, 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∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, 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.
We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ⁡ ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ⁡ ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ T gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.
We explore the implementation of pseudorandom single-qubit rotations and multiqubit pseudorandom circuits constructed only from Clifford gates and the TTT gate, a phase rotation of $\ensuremath{\pi}/4$. Such a gate set would be appropriate for computations performed in a fault tolerant setting. For single-qubit rotations the distribution of parameters found for unitaries constructed from Clifford plus TTT quickly approaches that of random rotations and requires significantly fewer gates than the construction of arbitrary single-qubit rotations. For Clifford-plus-TTT pseudorandom circuits we find an exponential convergence to a random matrix element distribution and a Gaussian convergence to the higher-order moments of the matrix element distribution. In addition, the nearest-neighbor eigenangle statistics distribution almost immediately converges to that of random unitary matrices. All of these convergence rates are found to be insensitive to the number of qubits.