Improved Almost laws for $SO(3)$
Computational Complexity
Summary
The authors find special sequences of operations (called words) for the 3D rotation group SO(3) that get very close to doing nothing (the identity operation) at a rate faster than previously known. They improve on an earlier result by showing a better exponent in the rate at which these words approach the identity. This has practical implications for making certain quantum computing algorithms, like Kuperberg's Solovay-Kitaev algorithm for single-qubit gates, more efficient by reducing the complexity required. Essentially, their work sharpens how quickly complex rotations can approximate the simplest rotation.
Authors
Gal Yehuda
Abstract
We construct quantitative almost laws for $SO(3)$. More precisely, there exist a constant $c>0$ and non-trivial words $W_n\in F_2$ such that, for every $A,B\in SO(3)$, \[ \|W_n(A,B)-I\| \le \exp\!\left(-c |W_n|^δ\right), \] where $δ=\log_2(x_0)=0.879146\ldots$ and $x_0>1$ is the real root of $x^3=x^2+x+1$. This improves the exponent $\log_2\varphi$ obtained from Elkasapy's lower-central-series construction. As an application, we show how this result improves the word-length threshold in Kuperberg's Solovay--Kitaev algorithm for single-qubit gates.