Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

We prove that any <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -qubit unitary can be implemented (i) approximately in time <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>O</mml:mi> <mml:mo stretchy="false">&amp;#x007E;</mml:mo> </mml:mover> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:math> with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>O</mml:mi> <mml:mo stretchy="false">&amp;#x007E;</mml:mo> </mml:mover> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:math> with one- and two-qubit gates and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi mathvariant="normal">&amp;#x03A9;</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:math> lower bound for (i) and (ii) for a certain class of implementations.