|
Abstract |
If a finite set S densely generates a compact, semisimple Lie group G, then how well does the set of words of length ℓ in S (and S-1) approximate G? We could ask for them words to be an ε-net of G; or, beyond an ε-net, we could ask for the words to be evenly distributed down to a scale of ε; or we could ask for an efficient algorithm to produce a word that lies within ε of any given g in G. An optimal statistical result, with ℓ = O(log 1/ε), was first established by Lubotzky, Phillips, and Sarnak when G = SU(2) for special choices of S; and later generalized by others, but still with some restrictions on S. Not long afterwards, in the context of quantum computing, Solovay and Kitaev independently established an algorithm to find a word with ℓ = O((log 1/ε)a) for any S and (initially) also G = SU(2). I will discuss the current status of different versions of this question, including versions when G might not be compact or S-1 might not be used. I will also discuss my own result, in which I improve the exponent in the (algorithmic) Solovay-Kitaev theorem from the previous best value of a = 3+δ to a = (logφ 2) + 1 + δ < 2.4405. |
