Greg Kuperberg @ Tel Aviv University

Combinatorics and more 2023-03-07

zigzagolf

Greg Kuperberg is having a short visit in Israel and yesterday he gave a fantastic lecture on an improved bound for the Kitaev-Solovay theorem. Here is a videotaped lecture of Greg on the same topic in QIP2023.

Kitaev-Solovay theorem from 1995 (in a stronger version by Kitaev-Shen-Viyalyi) asserts that

Theorem: If $A$ is a finite subset of $G=SU(d)$ that densely generates $G$ with the property that $A=A^{-1}$ , then there is an efficient algorithm to $\epsilon$ -approximate every element $g \in G$ by a word $w_A$ of length

$O(\log \frac{1}{\epsilon})^{\gamma},$

where we can take $\gamma = 3+\delta$ , for every $\delta >0$ .

Greg mentioned several improvements and related results over the years and he addressed the question of improving $\gamma$ . His result which gave the first known improvement (using two separate ideas) takes $\gamma$ down from $3+\delta$ to 1.44042…

(I told Greg that the mathematician’s labor unions frown on such drastic advances in a single paper.)

You can test your intuition for what 1.44042… stands for.

1.44042 stands for $\log _\phi 2$ where golden $\phi=\frac {1+\sqrt 5}{2}.$

Kitaev-Solovay’s theorem and its extensions are related to questions regarding expansion and other properties of Cayley graphs of Lie groups, questions in additive number theory, and questions in group theory. One of the techniques that Greg had developed is referred to as zigzag Golf (see the picture above) and another technique that Greg applies is related to higher commutators and Elkasapy-Thom theory.

After the lecture, a few of us had a very nice chat with Greg over lunch on various things. Just before I left Greg told me about three experimental advances regarding quantum error correcting that he found exciting (and thought are potentially relevant to a decade-and-more long and intensive email discussion/debate that Greg and I had on the topic since 2005.) I will mention these examples and some related information in a comment to this post. After a decade of a continuous intensive debate and few later bursts of further debates (also on blogs and FB) Greg and I decided on a truce with friendly exchange of ideas from time to time.