Solovay–Kitaev theorem. In quantum information and computation, the Solovay–Kitaev theorem says that if a set of single-qubit quantum gates generates a dense subgroup of SU(2), then that set can be used to approximate any desired quantum gate with a short sequence of gates that can also be found efficiently. This theorem is considered one of the most significant results in the field of quantum computation and was first announced by Robert M. Solovay in 1995 and independently proven by Alexei Kitaev in 1997. Michael Nielsen and Christopher M. Dawson have noted its importance in the field.

A consequence of this theorem is that a quantum circuit of  constant-qubit gates can be approximated to  error (in operator norm) by a quantum circuit of  gates from a desired finite universal gate set (where c is a constant). By comparison, just knowing that a gate set is universal only implies that constant-qubit gates can be approximated by a finite circuit from the gate set, with no bound on its length. So, the Solovay–Kitaev theorem shows that this approximation can be made surprisingly efficient, thereby justifying that quantum computers need only implement a finite number of gates to gain the full power of quantum computation.

Statement 
Let  be a finite set of elements in SU(2) containing its own inverses (so  implies ) and such that the group  they generate is dense in  SU(2). Consider some . Then there is a constant  such that for any , there is a sequence  of gates from  of length  such that . That is,  approximates  to operator norm error. Furthermore, there is an efficient algorithm to find such a sequence.  More generally, the theorem also holds in SU(d) for any fixed d.

This theorem also holds without the assumption that  contains its own inverses, although presently with a larger value of  that also increases with the dimension .

Quantitative bounds 
The constant  can be made to be  for any fixed . However, there exist particular gate sets for which we can take , which makes the length of the gate sequence optimal up to a constant factor.

Proof idea 

Every known proof of the fully general Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to . Suppose we have an approximation  such that . Our goal is to find a sequence of gates approximating  to  error, for . By concatenating this sequence of gates with , we get a sequence of gates  such that .

The main idea in the original argument of Solovay and Kitaev is that commutators of elements close to the identity can be approximated "better-than-expected". Specifically, for  satisfying  and  and approximations  satisfying  and , then

where the big O notation hides higher-order terms. One can naively bound the above expression to be , but the group commutator structure creates substantial error cancellation.

We can use this observation to approximate  as a group commutator . This can be done such that both  and  are close to the identity (since ). So, if we recursively compute gate sequences approximating  and  to  error, we get a gate sequence approximating  to the desired better precision  with  . We can get a base case approximation with constant  with an exhaustive search of bounded-length gate sequences.

Proof of Solovay-Kitaev Theorem 

Let us choose the initial value  so that   to be able to apply the iterated “shrinking” lemma. In addition we want  to make sure that  decreases as we increase . Moreover, we also make sure that  is small enough so that .

Since  is dense in , we can choose  large enough so that  is an -net for  (and hence for , as well), no matter how small  is. Thus, given any , we can choose  such that . Let  be the “difference” of  and . Then

Hence, . By invoking the iterated "shrinking" lemma with , there
exists  such that

Similarly let . Then 

Thus,  and we can invoke the iterated "shrinking" lemma (with
 this time) to get  such that 

If we continue in this way, after k steps we get  such that

Thus, we have obtained a sequence of

gates that approximates  to accuracy . To determine the value of , we set 
and solve for k:

Now we can always choose  slightly smaller so that the obtained value
of  is an integer. Let  so that. Then

Hence for any  there is a sequence of  gates that
approximates  to accuracy .

Solovay-Kitaev algorithm for qubits 

Here the main ideas that are used in the SK algorithm have been presented. The SK algorithm may be expressed in nine lines of pseudocode. Each of these
lines are explained in detail below, but present it here in its entirety both for the reader's reference, and to stress the conceptual simplicity of the algorithm:

 function Solovay-Kitaev(Gate , depth ) is
 
     if ( == 0)
 
         return Basic Approximation to 
 
     else
 
         set  = Solovay-Kitaev(,)
 
         set  = GC-Decompose()
 
         set  = Solovay-Kitaev()
 
         set  = Solovay-Kitaev()
 
         return ;
         
 end function

Let us examine each of these lines in detail. The first line:

 function Solovay-Kitaev(Gate , depth ) is

indicates that the algorithm is a function with two inputs: an arbitrary single-qubit quantum
gate, , which we desire to approximate, and a non-negative integer, , which controls
the accuracy of the approximation. The function returns a sequence of instructions which
approximates  to an accuracy , where  is a decreasing function of , so that as  gets
larger, the accuracy gets better, with  as .  is described in detail below.

The Solovay-Kitaev function is recursive, so that to obtain an -approximation to ,
it will call itself to obtain -approximations to certain unitaries. The recursion terminates
at , beyond which no further recursive calls are made:

 if ( == 0)
  
     return Basic Approximation to 

In order to implement this step it is assumed that a preprocessing stage has been completed
which allows one to find a basic -approximation to arbitrary . Since  is a constant, in principle this preprocessing stage may be accomplished simply by enumerating
and storing a large number of instruction sequences from , say up to some sufficiently large
(but fixed) length , and then providing a lookup routine which, given , returns the closest sequence.

At higher levels of recursion, to find an -approximation to , one begins by finding an
-approximation to :

 else
 
     set  = Solovay-Kitaev(,)

 is used as a step towards finding an improved approximation to . Defining ≡ , the next three steps of the algorithm aim to find an -approximation to , where  is some improved level of accuracy, i.e., . Finding such an approximation
also enables us to obtain an -approximation to , simply by concatenating exact
sequence of instructions for  with -approximating sequence for .

How do we find such an approximation to? First, observe that  is within a distance  of the identity. This follows from the definition of  and the fact that  is within a distance  of .

Second, decompose  as a group commutator  of unitary gates  and . For any  it turns out that this is not obvious and that there is always an infinite set of
choices for  and  such that . For our purposes it is important that we
find  and  such that  for some constant . We call such a decomposition a balanced group commutator.

 set  = GC-Decompose()

For practical implementations we will see below that it is useful to have  as small as
possible.

The next step is to find instruction sequences which are -approximations to  and :

 set  = Solovay-Kitaev() 
 
 set  = Solovay-Kitaev()

The group commutator of  and  turns out to be an  ≡ -approximation to , for some small constant . Provided , we see that , and this procedure therefore provides an improved
approximation to , and thus to .

The constant  is important as it determines the precision  required of the initial approximations. In particular, we see that for this construction to guarantee that  we must have .

The algorithm concludes by returning the sequences approximating the group commutator, as well as :

 return '';

Summing up, the function Solovay-Kitaev(U, n) returns a sequence which provides an -approximation to the desired unitary  . The five constituents in this sequence
are all obtained by calling the function at the th level of recursion.

References 

Mathematical theorems
Quantum computing
Quantum information theory