1212.0822 (Vadym Kliuchnikov et al.)

Asymptotically optimal approximation of the single qubit unitaries by
Clifford+T circuits using at most three ancillary qubits    [PDF]

Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca

We present an algorithm for building a circuit that approximates unitaries with precision $\varepsilon$ using $O(\log(1/\varepsilon))$ Clifford and T gates and employing up to three ancillary qubits. The algorithm for computing our approximating circuit requires an average of $O(\log^{2}(1/\varepsilon)\log\log(1/\varepsilon))$ operations. We prove that the number of gates in our circuit saturates the lower bound on the number of gates required in the scenario when a constant number of ancillae are supplied, and as such, our circuits are asymptotically optimal. This results in significant improvement over current state of the art for finding an approximation of a unitary that includes the Solovay-Kitaev algorithm that requires $O(\log^{3+\delta}(1/\varepsilon))$ gates and does not use ancillae and the phase kickback approach that requires $O(\log^{2}(1/\varepsilon)\log\log(1/\varepsilon))$ gates, but uses $O(\log^{2}(1/\varepsilon))$ ancillae.

View original: http://arxiv.org/abs/1212.0822