Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

We prove that any n -qubit unitary can be implemented (i) approximately in time O ~ ( 2 n / 2 ) with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth O ~ ( 2 n / 2 ) with one- and two-qubit gates and 2 O ( n ) ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching Ω ( 2 n / 2 ) lower bound for (i) and (ii) for a certain class of implementations.