Controlled Quantum Search

Quantum searching for one of $N$ marked items in an unsorted database of $n$ items is solved in $\mathcal{O}(\sqrt{n\mathrm{/}N})$ steps using Grover’s algorithm. Using nonlinear quantum dynamics with a Gross-Pitaevskii type quadratic nonlinearity, Childs and Young discovered an unstructured quantum search algorithm with a complexity $$\mathcal{O}$( \min { 1/g , \log (g n), \sqrt{n} } ) $,whichcanbeusedtofindamarkeditemafter$o(\log(n))$ repetitions, where $g$ is the nonlinearity strength [PhysRevA.93.022314]. In this work we develop a structured search on a complete graph using a time dependent nonlinearity which obtains one of the $N$ marked items with certainty. The protocol has runtime $$\mathcal{O}$((N^{\perp} - N) / (G \sqrt{N N^{\perp}}) ) if N^{\perp} > N$,where$N^{\perp}$denotesthenumberofunmarkeditemsand$G$isrelatedtothetimedependentnonlinearity\mathrm{.}If$N^{\perp} \leq N$, we obtain a runtime $\mathcal{O}(1)$. We also extend the analysis to a quantum search on general symmetric graphs and can greatly simplify the resulting equations when the graph diameter is less than 5.