Greg Kuperberg @ Tel Aviv University

zigzagolf

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

The Solovay-Kitaev 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 shown 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 mathematicians’ labor unions frown upon 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}.

Solovay-Kitaev’s theorem and its extensions are related to questions about 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 has developed is referred to as zigzag Golf (see the picture above) and another technique that Greg applies is related to higher commutators and the Elkasapy-Thom theory.

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

This entry was posted in Algebra, Combinatorics, Computer Science and Optimization, Quantum and tagged . Bookmark the permalink.

Leave a comment