  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. We show that our technique, combined with a GNAT
geometric tree search outputs gate sequences that are almost an order of
magnitude smaller for the same level of accuracy. This therefore significantly
reduces the error correction requirements for quantum algorithms on encoded
fault-tolerant hardware.
