Depth scaling of unstructured search via quantum approximate optimization

Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms—the quantum approximate optimization algorithm (QAOA)—was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search, which consists of finding a particular bit string or, equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such a problem we build on its known solution in a continuous time quantum walk (CTQW). We Trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state that approaches perfect overlap with the target state. The obtained complexity exceeds Grover's algorithm complexity $O\left(N^{\frac{1}{2}}\right)$, but remains smaller than $O\left(N^{\frac{1}{2}+c}\right)$ for any $c>0$, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits.