Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits

Understand

We present an algorithm for building a circuit that approximates single qubit unitaries with precision {\epsilon} using O(log(1/{\epsilon})) Clifford and T gates and employing up to two ancillary qubits.

• The algorithm for computing our approximating circuit requires an average of O(log^2(1/{\epsilon})log log(1/{\epsilon})) 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 the current state of the art for finding an approximation of a unitary, including the Solovay-Kitaev algorithm that requires O(log^{3+{\delta}}(1/{\epsilon})) gates and does not use ancillae and the phase kickback approach that requires O(log^2(1/{\epsilon})log log(1/{\epsilon})) gates, but uses O(log^2(1/{\epsilon})) ancillae.