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.