# Breaking the cubic barrier in the Solovay-Kitaev algorithm

arXiv: https://arxiv.org/abs/2306.13158 · HTML: https://mlsanity.com/paper/2306.13158/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2023.

## Built on by (most cited first, 2 of 2)

- [Diagonal Adaptive Non-local Observables on Quantum Neural Networks](https://mlsanity.com/paper/2605.15410/) (2026)
- [Harmonic analysis and circuit approximation of Sobolev functions on quantum input spaces](https://mlsanity.com/paper/2610.13477/) (2026)

## Abstract (arXiv)

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+δ) 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(n1.44042ldots+δ). 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.