



01270nas a2200133   4500008004100000245006500041210006200106260001500168300001200183490000700195520087800202100001901080856003701099       2015                        eng d00aOptimal ancilla-free Clifford+V approximation of z-rotations0 aOptimal ancillafree CliffordV approximation of zrotations  c2015/03/06  a932-9500 v153 a  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.
1 aRoss, Neil, J.  uhttp://arxiv.org/abs/1409.4355v2