The Solovay-Kitaev algorithm
New paper: “The Solovay-Kitaev algorithm”, jointly with Chris Dawson, submitted as a tutorial / review article to the journal “Quantum Information and Computation”. I expect the paper to appear at the preprint arxiv this coming Monday, as I write.
The Solovay-Kitaev theorem is an important result in quantum computing. In a classical computer, it’s well-known that the same computation can be built up out of many different basic gate sets. For example, you can build up a circuit to add two numbers either using OR and NOT gates, or out of NAND gates alone. Furthermore, you can use OR and NOT gates to simulate NAND gates (or vice versa), so, roughly speaking, these two different circuits can have the same size, up to some constant of proportionality.
In the case of quantum computers, things are more complicated. The set of possible quantum gates forms a continuum, and it’s not necessarily possible to use one gate set to simulate another exactly. Instead, some approximation may be necessary.
The Solovay-Kitaev theorem guarantees that different universal gate sets can simulate one another exceedingly quickly, to a very good approximation. From a practical point of view, this is important in compiling quantum algorithms (like Shor’s) into a form that can be implemented fault-tolerantly. From a more mathematical point of view, the Solovay-Kitaev theorem is a remarkable general statement about how quickly the group SU(d) is “filled in” by a universal set of gates.
This paper aims to provide a simple exposition of the Solovay-Kitaev theorem, which we hope is accessible to people who’ve just started working on quantum computing. We explain the proof in the form of an algorithm (just nine simple lines of pseudocode!) which, given a goal unitary operation U, builds up a good approximation to U using some prespecified set of universal gates. Chris has also prepared an online implementation of the algorithm.