01100nas a2200133 4500008004100000245006500041210006200106300001200168490000700180520070300187100001900890700002000909856003700929 2016 eng d00aOptimal ancilla-free Clifford+T approximation of z-rotations0 aOptimal ancillafree CliffordT approximation of zrotations a901-9530 v163 a
We consider the problem of decomposing arbitrary single-qubit z-rotations into ancilla-free Clifford+T circuits, up to given epsilon. We present a new efficient algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal: In this case, it finds a solution of T-count m + O(log(log(1/epsilon))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit decompositions of T-count 3log_2(1/epsilon) + O(log(log(1/epsilon))).
1 aRoss, Neil, J.1 aSelinger, Peter uhttp://arxiv.org/abs/1403.2975v2