arXiv:2610.03655
Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm
Adam Bouland, Victor Shyaka, Chenyi Zhang
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.
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.