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. Our method is based on previous work by

the author and Selinger on the optimal ancilla-free approximation of

z-rotations using Clifford+T gates and on previous work by Bocharov, Gurevich,

and Svore on the asymptotically optimal ancilla-free approximation of

z-rotations using Clifford+V gates.