Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Given a finite set $S$ that densely generates a Lie group $G$, is there a word $w$ in $S$ of some economical length $\ell$ that lies within $\epsilon$ of a target group element $g \in G$? Beyond whether $w$ always exists, we could ask for all words of length $\ell$ to be statistically well-distributed down to a length scale of $\epsilon$. Or we could ask for an efficient algorithm to produce a $w$ that lies within $\epsilon$ of any given $g$. When $G$ is compact and semisimple, statistical equidistribution is conjectured with an optimal length $\ell = O(\log 1/\epsilon)$ for any $S$; this has now been proven when $S$ is algebraic. At the other end, the Solovay-Kitaev theorem from quantum computing yields an efficient (classical) algorithm to find a word of length $\ell = O((\log 1/\epsilon)^\alpha)$ when $G = SU(d)$, for any $\alpha > 3$.

In this talk I will describe my new algorithm that improves the exponent $\alpha$ in the Solovay-Kitaev theorem to any number greater than $\log_\phi 2 = 1.44042...$, where $\phi$ is the golden ratio. The bound holds for any semisimple $G$, with an extra long-distance length term when $G$ is non-compact.

Reference: arXiv:2306.13158