Sampling random circuits vs Solovay-Kitaev compiler

The Solovay-Kitaev algorithm is not practical. It is very useful theoretically because it proves that once you have a "dense" set of quantum gates (i.e. a set with which you can approximate any other quantum gate) you can approximate up to an arbitrary precision and quickly any quantum gate.

In practice, the Solovay-Kitaev works as follow:

1. Fill the space of implementable quantum gates as much as possible. This is performed by creating quantum circuits with the gate-set considered and storing them in memory alongside the unitary evolution they implement. The goal of this step is to fill the space of implementable quantum gates such as, for any unitary matrix, there is a entry in the set at distance at most $epsilon_0$.
2. Recurse as explained in this article and when reaching the end of the recursion, find a circuit (pre-computed in step 1) that approximates sufficiently well the current unitary.

Some obervations:

• Point 1 only need to be done once for each circuit arity. Once you finished point 1 for $k$-qubit gates, you can just save the result on a hard-drive and reload it for the next approximation.
• Point 1 is VERY GREEDY in computational resources. A quantum gate on $n$ qubits can be represented as a matrix in $SU(2^n)$, which is a space of dimension $2^{2n} - 1$. Filling uniformly a space with such a dimension requires a HUGE number of points (i.e. a huge number of quantum circuits).

• In order to perform point 2, one of the most efficient method (asymptotically-speaking) is to use nearest-neighbour algorithms. There exist a lot of algorithms (the most used being probably the KD-tree approach), and some of them are designed for high-dimensional data (see this answer or this one).

  But still, your search space (the circuits generated in point 1) "suffer from the curse of dimensionality" in the sense that its size grows really fast when the dimension increase. Even if you can search for a nearest-neighbour in $O(nln(n))$, the $n$ is incredibly large here.

• During the recursion, a matrix decomposition needs to be performed. An efficient algorithm for the decomposition has been devised in this article for $1$-qubit gates (i.e. $SU(2)$ matrices), but no efficient implementation exist for gates on $2$ or more qubits: you end up diagonalising the unitary matrix you want to implement, which become quite costly when the unitary matrix becomes large.

To sum up:

1. The Solovay-Kitaev algorithm has only a very little practical application for $1$-qubit gates, nearly no practical application for $2$-qubit gates and clearly no practical application for $3$-qubit gates and above.
2. Randomised approach can work way better and have a better scaling with respect to the number of qubits. You can also have a look at the Group Leader Optimisation Algorithm -- GLOA if you want to dig in this direction.
3. The theoretical scaling of SK is very good with respect to precision, but exponential with respect to the size of the gate.
4. In the case of large number of qubit, SK will fail or take days whereas the randomised approach might give you a decomposition with a low precision in seconds or minutes. As a side note, the randomised approach is trivial to parallelise, SK is not so easy (nearest-neighbour algorithms are hard to parallelise efficiently).