Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm
Abstract
The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy ε in 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 ≈ 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.
Related
- A physical and universal model of bosonic computations with Solovay-Kitaev theorem
- Resonance Breaking in Noisy Shor's Algorithm
- Lowest-known Energy Configuration of N=100 000 Coulomb Charges in a Disk: Breaking the 105 Barrier
- Leptogenesis and dark matter in an inverse Seesaw from gauged B − L breaking
- Inverse design of large-scale freeform meta-optics by breaking the memory wall of full-wave simulation
BibTeX
@misc{bouland2026breaking,
title = {{Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm}},
author = {Adam Bouland and Victor Shyaka and Chenyi Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03655},
eprint = {2610.03655},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03655},
}
RIS
TY - UNPB
TI - Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm
AU - Adam Bouland
AU - Victor Shyaka
AU - Chenyi Zhang
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03655
UR - https://arxiv.org/abs/2610.03655
AB - The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy ε in 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 ≈ 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.
ER -