Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Establishes fundamental upper and lower bounds for quantum unitary implementation, relevant to quantum algorithm design and circuit complexity.
The paper proves that any n-qubit unitary can be implemented approximately in time O~(2^{n/2}) with query access to a classical oracle, and exactly by a circuit of depth O~(2^{n/2}) using one- and two-qubit gates and 2^{O(n)} ancillae, with matching lower bounds for a class of implementations.
We prove that any $n$-qubit unitary can be implemented (i) approximately in time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$ 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 $Ω\big(2^{n/2}\big)$ lower bound for (i) and (ii) for a certain class of implementations.