Discrete Time Multi-particle Grover Search
Christopher Um · 2021
Grover's algorithm is a quantum search algorithm that produces a quadratic speedup compared to its classical analog, a brute-force algorithm, and has a complexity of$\mathcal{O}(\sqrt{N})$. Past works have shown that Grover's algorithm can asymptotically be improved by generalizing the number of marked sites. I examine Grover's algorithm when the number of searching particles is generalized in discrete time setting, which allows to understand the search algorithm in terms of “interactions” between particles. I provide a novel design of Grover with appended interaction terms to analyze$\mathcal{O}$as$N\rightarrow\infty$. I utilize the eigenvalue perturbation theory to deduce the optimal interaction condition and show that the condition results in an asymptotic improvement denendent upon the number of particles.