2017/10/25 by K. de Lacy, de Lacy, K., Lyle Noakes +1 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography
paper · pdf · doi:10.48550/arxiv.1710.09053
Quantum searching for one of N marked items in an unsorted database of n items is solved in O(√(n/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 O( min \ 1/g log (g n), √(n) \ ) , which can be used to find a marked item after 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 O((N⊥ - N) / (G √N N⊥) ) if N⊥ > N, where N⊥ denotes the number of unmarked items and G is related to the time dependent nonlinearity. If N⊥ ≤ N, we obtain a runtime 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.