Optimal ancilla-free Clifford+V approximation of z-rotations

Understand

We describe a new efficient algorithm to approximate z-rotations by ancilla-free Clifford+V circuits, up to a given precision epsilon.

• Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+V circuit solving the given problem instance.
• In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of V-count m + O(log(log(1/epsilon))), where m is the V-count of the third-to-optimal solution.
• A restricted version of the algorithm approximates z-rotations in the Pauli+V gate set.