Optimization of the Solovay-Kitaev algorithm

The Solovay-Kitaev algorithm is the standard method used for approximating arbitrary single-qubit gates for fault-tolerant quantum computation. In this paper we introduce a technique called search space expansion, which modifies the initial stage of the Solovay-Kitaev algorithm, increasing the length of the possible approximating sequences but without requiring an exhaustive search over all possible sequences. This technique is combined with an efficient space search method called geometric nearest-neighbor access trees, modified for the unitary matrix lookup problem, in order to reduce significantly the algorithm run time. We show that, with low time cost, our techniques output gate sequences that are almost an order of magnitude smaller for the same level of accuracy. This therefore reduces the error correction requirements for quantum algorithms on encoded fault-tolerant hardware.

Figure 1

Expanding the search space. Sequence $\zeta \left(0\right)$ (a good first approximation to gate $G$) is split into two halves, $\zeta \left(0\right)={\zeta }^{\left(1\right)}\left(0\right){\zeta }^{\left(2\right)}\left(0\right)$. Points in regions of distance ${\overline{\epsilon }}_0$ (shaded) away from ${\zeta }^{\left(1\right)}\left(0\right),{\zeta }^{\left(2\right)}\left(0\right)$ are recombined, and the one closest to $G$, $Z\left(0\right)$, is chosen. With high probability, $\left|\right|G-\zeta \left(0\right)\left|\right|>\left|\right|G-Z\left(0\right)\left|\right|$.

Figure 2

Schematic diagram of a simple GNAT with clusters (see text for explanation).

Figure 3

GNAT vs linear search time for stored sequence databases with $l_0=16,17,18,19$. The program is implemented in java and run on an ubuntu 11.10 32 byte type operating system (OS), Core i7-2670QM 2.20 GHz Intel processor, with 2.9 GB of memory. The apparent asymmetry in the error bars is due to the logarithmic vertical scale.

Figure 4

Approximation accuracy vs the length of the best approximating gate sequence found (number of $T$ gates).

Figure 5

Approximation accuracy vs classical compilation time to find the best approximating gate sequence. The program is implemented in java and run on an ubuntu 11.10 32 byte type OS, Core i7-2670QM 2.20 GHz Intel processor, with 2.9 GB of memory.