|
Efficient Clifford+T approximation of single-qubit operators
(pp0159-0180)
Peter
Selinger
doi:
https://doi.org/10.26421/QIC15.1-2-10
Abstracts:
We give an efficient randomized algorithm for
approximating an arbitrary element of SU(2) by a product of Clifford+T
operators, up to any given error threshold ε > 0. Under a mild
hypothesis on the distribution of primes, the algorithm�s expected
runtime is polynomial in log(1/ε). If the operator to be approximated is
a z-rotation, the resulting gate sequence has T-count K+4 log2 (1/ε),
where K is approximately equal to 10. We also prove a worst-case lower
bound of K + 4 log2 (1/ε), where K = −9, so that our algorithm is within
an additive constant of optimal for certain z-rotations. For an
arbitrary member of SU(2), we achieve approximations with T-count K + 12
log2 (1/ε). By contrast, the Solovay-Kitaev algorithm achieves T-count
O(logc (1/ε)), where c is approximately 3.97.
Key words:
circuit synthesis, Clifford+T, efficient approximation of unitary
operators |
