The complexity of implementing NxN black-box unitaries is O(N^{3/4}) - Dominic Berry

Standard methods for implementing arbitrary $N\times N$ unitaries require $\Omega(N2)$ gates. We consider a black box that outputs the matrix elements of the unitary, and show that the unitary may be performed with fidelity $1-\xi$ using $O(N^{3/4}/\xi^{1/2})$ black-box calls. This may be achieved by using a quantum walk, where each step of the quantum walk is performed using amplitude amplification. Except for pathological cases, higher-order integrators may be used to improve the scaling to $O((N/\xi)^{1/2+\epsilon})$ black-box calls, for any $\epsilon>0$. In comparison, state preparation via amplitude amplification can be performed with $O(N^{1/2})$ black-box calls; almost the same scaling in $N$.