Solovay Kitaev Compilation

Short answer: The Solovay-Kitaev theorem says that if a finite set of single-qubit gates generates a dense subset of SU(2), any single-qubit gate can be approximated to accuracy epsilon with a sequence whose length grows only polynomially in log(1/epsilon). A 2005 pedagogical review gives an algorithm that runs in time of order log^2.71(1/epsilon) and outputs a sequence of order log^3.97(1/epsilon) gates. It is a result about compiling gates, not about a specific machine.

The question

A 2001 paper on quantum compiling describes the problem as approximating an arbitrary quantum gate with a string of gates from a finite set. It says a set of base gates is computationally universal if it generates a dense subgroup, so any gate can be approximated to arbitrary precision. It says compiling is generically possible, so the vital question is how short the string must be for a given precision. It notes that an earlier construction by Lloyd needs a number of base gates exponential in log(1/epsilon), which it calls unreasonable for many applications.

What the theorem gives

The 2005 review calls the Solovay-Kitaev (SK) theorem one of the most important fundamental results in the theory of quantum computation. In its simplest form, it says, if a set of single-qubit gates generates a dense subset of SU(2), the set fills SU(2) quickly: good approximations to any gate come from surprisingly short sequences from the generating set. The 2001 paper says Solovay and Kitaev independently described an efficient algorithm, with running time polynomial in log(1/epsilon), producing strings of length O(log^c(1/epsilon)) with c between 3 and 4.

How the algorithm works

According to the 2001 paper, the algorithm works by constructing successively finer epsilon-nets: finite sets of gates that can approximate any element of SU(d) to accuracy epsilon. An essay on the theorem states a "shrinking" lemma: a net of one quality for a ball around the identity can be turned into a better net, at the cost of longer sequences of generators and a smaller covered neighbourhood. Applying it repeatedly gives the desired accuracy.

The 2005 review

The review says it presents the proof as a concrete classical algorithm for compiling an arbitrary single-qubit gate into a sequence from a fixed finite set. It says the algorithm can compile Shor's algorithm, which uses rotations by pi over 2^k, into a fault-tolerant form using only Hadamard, controlled-NOT and pi/8 gates. It reports a running time of O(log^2.71(1/epsilon)) and output length of O(log^3.97(1/epsilon)), guaranteed to approximate the desired gate to within epsilon. It adds that the algorithm can be generalized to multi-qubit gates and to gates from SU(d). The review stresses that it is a review, and that all the essential ideas come from earlier work.

A tighter length

The 2001 paper proves that, for certain base gate sets, quantum compiling needs a string length linear in log(1/epsilon), which it says matches the lower bound from counting volume up to a constant factor. So for those sets the polynomial exponent of the Solovay-Kitaev algorithm is not the last word.

What this does not tell you

These papers do not give gate counts for any real circuit, and they do not cover the optimized compilers used in practice. The exponents above are the papers' bounds for the algorithm as described.

FAQ

What does the Solovay-Kitaev theorem say?

A finite gate set that generates a dense subset of SU(2) can approximate any single-qubit gate with a short sequence, polynomial in log(1/epsilon).

How long are the sequences?

The 2005 review gives O(log^3.97(1/epsilon)) gates. The 2001 paper says the exponent is between 3 and 4.

Why does it matter for fault tolerance?

The review says it can compile rotations in Shor's algorithm into a form using only Hadamard, controlled-NOT and pi/8 gates.

Can sequences be shorter?

The 2001 paper proves that for certain base sets the length is linear in log(1/epsilon).

Does it work for more than one qubit?

The review says the algorithm can be generalized to multi-qubit gates and to SU(d).