Sampling random circuits vs Solovay-Kitaev compiler

Question

Suppose I want to obtain a gate sequence representing a particular 1 qubit unitary matrix. The gate set is represented by a discrete universal set, e.g. Clifford+T gates or $\{T,H\}$ gates. A well known approach to solve the problem is to use Solovay-Kitaev (SK) algorithm. I tried this implementation for SK algorithm. The resulting circuits are incredibly long ($l\sim 100-1000$ gates for the Fowler distance $\epsilon \sim 0.01$, tolerance error for the basic approximation $\epsilon\sim 0.03$). Moreover the basic approximation (building a KD-tree) can take quite long time (although this might be due to somewhat slow Python code).

On the other hand I wrote a very simple script that generates random sequences of gates and selects the best performing circuits. It works very fast and results in much shorter circuits with Fowler distances $\epsilon< 10^{-4}-10^{-5}$. This should be more than sufficient for any realistic applications.

So, at this point I don't quite understand, what is practical significance of Solovay-Kitaev algorithm in this case (for 1 qubit operations)?

Of course, the theoretical scaling of SK algorithm looks pretty good. The number of gates generated by SK algorithm to approximate any 1 qubit unitary grows as $l\sim\log^c(1/\delta)$, where $\delta$ is L2 approximation error. For random sampling there are no such guarantees. However on practice I'm not convinced that SK is very useful for 1 qubit case. No doubts that in the case of large number of qubits random sampling will fail because of the curse of dimensionality. But it seems that SK algorithm also quickly becomes computationally unfeasible ($\#$ of qubits $\geq 4$?).

Answer 1

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(n\ln(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).