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

Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm

Adam Bouland, Victor Shyaka, Chenyi Zhang

quant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations
arXivHTMLPDF

Abstract

The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy $ε$ in $\text{polylog}(1/ε)$ time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over $8.62$, while information theoretically it is known that an inverse-free exponent of $3$ is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments? To answer this question, we first show that a special case of the inverse-free compiling problem -- namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most $\approx 2.138$. Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient ``Pauli golf'' compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most $2.988$. This result uses a novel form of approximate ``aiming'' of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.

AI Summary

The paper asks how efficiently arbitrary single-qubit unitaries can be compiled over a finite universal gate set without assuming access to gate inverses. Previous constructive inverse-free Solovay–Kitaev bounds had a qubit exponent above $8.62$, whereas a nonconstructive result guaranteed sequences of length $O(\log^3(1/\epsilon))$. Two compilation algorithms give subcubic sequence-length bounds. If exact Pauli gates are available, the output length is $O(\log^{2.138}(1/\epsilon))$. The construction combines “Pauli golf,” which uses Pauli conjugations to orient small corrections and reduce error by a constant factor, with recursive self-correcting words. Their cancellation orders grow as Tribonacci numbers while their lengths grow as $2^n$, giving a stick-generation exponent $\log 2/\log\rho\approx1.13747$, where $\rho^3=\rho^2+\rho+1$. For an arbitrary finite universal subset of $\mathrm{SU}(2)$, the output length is $O(\log^{2.988}(1/\epsilon))$. A fixed cancellation sequence constructs small rotations approximately aligned with prescribed directions using much coarser recursive approximations. A second sequence, whose local surjectivity is established through derivative bounds and a contraction argument, converts these rotations into arbitrary local corrections. The resulting length recurrence yields the stated exponent. Both algorithms have classical runtime $\operatorname{polylog}(1/\epsilon)$. The results concern single-qubit compilation; the stronger bound requires exact Paulis. They improve the known cubic existence guarantee in this setting, but do not establish optimality or improve spectral-gap bounds. Further improvements to the information-theoretic qubit bounds are left open.

Little sign of AI-generated textAI use disclosed
The general inverse-free compilation algorithm for a qubit was developed using GPT 5.6 Sol and GPT 6 Astra, with many rounds of interaction and simplification required to bring the exponent below 3.

Error found: The Pauli-assisted theorems impose impossible literal hypotheses by requiring standard Pauli matrices to belong to SU(2); an explicit phase-consistent reformulation is needed, but it preserves the claimed exponents.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

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

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

Breaking the cubic barrier in the Solovay-Kitaev algorithm

Greg Kuperberg

We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length $O(n^{3+δ})$ to approximate an arbitrary target gate to $n$ bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is $O(n^{1.44042\ldots+δ})$. Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the noncompact case to reach group elements far away from the identity.

arXiv:2306.13158•Jun 22, 2023•38 citations

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

Sub-Cubic Quantum Gate Synthesis via Stochastic Commutator Decomposition

Yevgen Kotukh

We present Stochastic Commutator Synthesis, a hybrid quantum gate compilation framework that integrates Kuperberg's sub-cubic Solovay-Kitaev exponent c near 1.44042 with the error-tailoring machinery of randomized compilation. Classical Solovay-Kitaev implementations produce known word lengths and accumulate coherent approximation errors that degrade fault-tolerant threshold estimates. Kuperberg's 2023-2025 result reduces this via doubly exponential convergence and higher-order commutator decompositions. SCS augments this geometric backbone with a Gibbs-sampled stochastic choice of commutator factors at each recursion level, converting coherent synthesis residuals into incoherent, Pauli-twirl-compatible noise -- a property exploited by RC. Combined with RL-guided pre-synthesis, SCS achieves consistent T-count reductions of 10-25 percent and demonstrates fidelity gains of up to 35 percent on multi-fold Forrelation circuits on trapped-ion hardware such as Sandia QSCOUT. We situate SCS within the complexity-theoretic landscape established by the Raz-Tal oracle separation, arguing that low-error, noise-robust compilation of Forrelation-type circuits constitutes a practical pathway toward demonstrating this separation on physical hardware.

quant-pharXiv:2605.02051•May 5, 2026•1 citation
The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy εεε in polylog(1/ε)\text{polylog}(1/ε)polylog(1/ε) time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over 8.628.628.62, while information theoretically it is known that an inverse-free exponent of 333 is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments?
To answer this question, we first show that a special case of the inverse-free compiling problem -- namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most ≈2.138\approx 2.138≈2.138.
Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient Pauli golf'' compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most $2.988$. This result uses a novel form of approximate aiming'' of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.
The paper asks how efficiently arbitrary single-qubit unitaries can be compiled over a finite universal gate set without assuming access to gate inverses. Previous constructive inverse-free Solovay–Kitaev bounds had a qubit exponent above 8.628.628.62, whereas a nonconstructive result guaranteed sequences of length O(log⁡3(1/ϵ))O(\log^3(1/\epsilon))O(log3(1/ϵ)).
Two compilation algorithms give subcubic sequence-length bounds. If exact Pauli gates are available, the output length is O(log⁡2.138(1/ϵ))O(\log^{2.138}(1/\epsilon))O(log2.138(1/ϵ)). The construction combines “Pauli golf,” which uses Pauli conjugations to orient small corrections and reduce error by a constant factor, with recursive self-correcting words. Their cancellation orders grow as Tribonacci numbers while their lengths grow as 2n2^n2n, giving a stick-generation exponent log⁡2/log⁡ρ≈1.13747\log 2/\log\rho\approx1.13747log2/logρ≈1.13747, where ρ3=ρ2+ρ+1\rho^3=\rho^2+\rho+1ρ3=ρ2+ρ+1.
For an arbitrary finite universal subset of SU(2)\mathrm{SU}(2)SU(2), the output length is O(log⁡2.988(1/ϵ))O(\log^{2.988}(1/\epsilon))O(log2.988(1/ϵ)). A fixed cancellation sequence constructs small rotations approximately aligned with prescribed directions using much coarser recursive approximations. A second sequence, whose local surjectivity is established through derivative bounds and a contraction argument, converts these rotations into arbitrary local corrections. The resulting length recurrence yields the stated exponent. Both algorithms have classical runtime polylog⁡(1/ϵ)\operatorname{polylog}(1/\epsilon)polylog(1/ϵ).
The results concern single-qubit compilation; the stronger bound requires exact Paulis. They improve the known cubic existence guarantee in this setting, but do not establish optimality or improve spectral-gap bounds. Further improvements to the information-theoretic qubit bounds are left open.
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.
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.
We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length O(n3+δ)O(n^{3+δ})O(n3+δ) to approximate an arbitrary target gate to nnn bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is O(n1.44042…+δ)O(n^{1.44042\ldots+δ})O(n1.44042…+δ). Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the noncompact case to reach group elements far away from the identity.
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).
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 present Stochastic Commutator Synthesis, a hybrid quantum gate compilation framework that integrates Kuperberg's sub-cubic Solovay-Kitaev exponent c near 1.44042 with the error-tailoring machinery of randomized compilation. Classical Solovay-Kitaev implementations produce known word lengths and accumulate coherent approximation errors that degrade fault-tolerant threshold estimates. Kuperberg's 2023-2025 result reduces this via doubly exponential convergence and higher-order commutator decompositions. SCS augments this geometric backbone with a Gibbs-sampled stochastic choice of commutator factors at each recursion level, converting coherent synthesis residuals into incoherent, Pauli-twirl-compatible noise -- a property exploited by RC. Combined with RL-guided pre-synthesis, SCS achieves consistent T-count reductions of 10-25 percent and demonstrates fidelity gains of up to 35 percent on multi-fold Forrelation circuits on trapped-ion hardware such as Sandia QSCOUT. We situate SCS within the complexity-theoretic landscape established by the Raz-Tal oracle separation, arguing that low-error, noise-robust compilation of Forrelation-type circuits constitutes a practical pathway toward demonstrating this separation on physical hardware.