Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth

Abstract

We propose a direct (non-recursive) algorithm for applying a rotation $R_{\hat{I}{¸}^{\ast }}$, $\hat{I}\mu$-close to a desired rotation $R_{\hat{I}}¸$, to a single qubit using the Clifford+Toffoli gate set. Our algorithm does not rely on repeatedly applying a fixed rotation, but immediately applies $R_{\hat{I}{¸}^{\ast }}$. It succeeds with probability strictly greater than $1/2$, has an expected number of repetitions strictly less than 2, expected Toffoli count logarithmic in $\frac{1}{\hat{I}}\mu$, and expected gate depth also logarithmic in $\frac{1}{\hat{I}}\mu$.

6 pages, 3 figures, v4: close to published version