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:2406.04846

Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem

H. F. Chau

Published Jun 7, 2024• 0 citations
arXivHTMLPDF

Abstract

Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of $ε> 0$ requires $\text{O}(\log^c[1/ε])$ quantum gates with $c > 1.44042$. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using $Ω(\log[1/ε])$ gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using $\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)$ FT gates chosen from a finite set depending on the value of $ε$. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy $ε> 0$. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.

DOI
10.48550/arxiv.2406.04846

Related papers

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

The Solovay-Kitaev algorithm

Christopher M. Dawson, Michael A. Nielsen

This pedagogical review presents the proof of the Solovay-Kitaev theorem in the form of an efficient classical algorithm for compiling an arbitrary single-qubit gate into a sequence of gates from a fixed and finite set. The algorithm can be used, for example, to compile Shor's algorithm, which uses rotations of $\pi / 2^k$, into an efficient fault-tolerant form using only Hadamard, controlled-{\sc not}, and $\pi / 8$ gates. The algorithm runs in $O(\log^{2.71}(1/\epsilon))$ time, and produces as output a sequence of $O(\log^{3.97}(1/\epsilon))$ quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within $\epsilon > 0$. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from SU(d).

arXiv:quant-ph/0505030•Quantum Information and Computation•Jan 1, 2006•759 citations

Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm

Adam Bouland, Tudor Giurgică-Tiron

The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both $\text{SU}(d)$ and $\text{SL}(d, \mathbb{C})$. The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.

arXiv:2112.02040•Dec 3, 2021•33 citations

Numerical Evaluation of ZX Calculus Optimization for Solovay Kitaev Quantum Circuit Synthesis

Dulari De Silva, Anuradha Mahasinghe, Chon-Fai Kam +3 more

Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.

quant-pharXiv:2608.22810•Aug 25, 2026•0 citations

Optimal two-qubit circuits for universal fault-tolerant quantum computation

Andrew N. Glaudell, Neil J. Ross, Jacob M. Taylor

Abstract We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1, i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and outputs a Clifford+CS circuit for U, which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of $$5{{\rm{log}}}_{2}(\frac{1}{\epsilon })+O(1)$$ 5 log 2 ( 1 ϵ ) + O ( 1 ) on the number of CS gates required to ϵ-approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits.

arXiv:2001.05997•npj Quantum Information•Jun 22, 2021•27 citations

Qutrit-Based Orthogonal Approximations with Inverse-Free Quantum Gate Sets

Anuradha Mahasinghe, Dulmi Fernando, Kaushika De Silva

The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.

International Online Conference on Mathematics and Applications (IOCMA)•Jun 13, 2023•0 citations
Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate. Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg implies that to approximate any single-qubit gate to an accuracy of ε>0ε> 0ε>0 requires O(log⁡c[1/ε])\text{O}(\log^c[1/ε])O(logc[1/ε]) quantum gates with c>1.44042c > 1.44042c>1.44042. Can one do better? That was the question asked by Nielsen and Chuang in their quantum computation textbook. Specifically, they posted a challenge to efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using Ω(log⁡[1/ε])Ω(\log[1/ε])Ω(log[1/ε]) gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using O(log⁡[1/ε]log⁡log⁡[1/ε]log⁡log⁡log⁡[1/ε]⋯ )\text{O}(\log[1/ε] \log\log[1/ε] \log\log\log[1/ε] \cdots)O(log[1/ε]loglog[1/ε]logloglog[1/ε]⋯) FT gates chosen from a finite set depending on the value of εεε. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy ε>0ε> 0ε>0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.
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.
This pedagogical review presents the proof of the Solovay-Kitaev theorem in the form of an efficient classical algorithm for compiling an arbitrary single-qubit gate into a sequence of gates from a fixed and finite set. The algorithm can be used, for example, to compile Shor's algorithm, which uses rotations of π/2k\pi / 2^kπ/2k, into an efficient fault-tolerant form using only Hadamard, controlled-{\sc not}, and π/8\pi / 8π/8 gates. The algorithm runs in O(log⁡2.71(1/ϵ))O(\log^{2.71}(1/\epsilon))O(log2.71(1/ϵ)) time, and produces as output a sequence of O(log⁡3.97(1/ϵ))O(\log^{3.97}(1/\epsilon))O(log3.97(1/ϵ)) quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within ϵ>0\epsilon > 0ϵ>0. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from SU(d).
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both SU(d)\text{SU}(d)SU(d) and SL(d,C)\text{SL}(d, \mathbb{C})SL(d,C). The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors.
Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.
Abstract We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1, i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and outputs a Clifford+CS circuit for U, which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of 5log2(1ϵ)+O(1)5{{\rm{log}}}_{2}(\frac{1}{\epsilon })+O(1)5log2​(ϵ1​)+O(1) 5 log 2 ( 1 ϵ ) + O ( 1 ) on the number of CS gates required to ϵ-approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits.
The efficient compiling of arbitrary single-qubit gates into a sequence of gates from a finite gate set is of fundamental importance in quantum computation. The exact bounds of this compilation are given by the Solovay–Kitaev theorem, which serves as a powerful tool in compiling quantum algorithms that require many qubits. However, the inverse closure condition it imposes on the gate set adds a certain complexity to the experimental compilation, making the process less efficient. This was recently resolved by a version of the Solovay–Kitaev theorem for inverse-free gate sets, yielding a significant gain. Considering the recent progress in the field of three-level quantum systems, in which qubits are replaced by qutrits, it is possible to achieve the quantum speedup guaranteed by the Solovay–Kitaev theorem simply from orthogonal gates. Nevertheless, it has not been investigated previously whether the condition of inverse closure can be relaxed for these qutrit-based orthogonal compilations as well. In this work, we answer this positively, by obtaining improved Solovay–Kitaev approximations to an arbitrary orthogonal qutrit gate, with an accuracy ε from a sequence of O(log8.62(1/ε)) orthogonal gates taken from an inverse-free set.