Resonant Quantum Search with Monitor Qubits

Abstract

We present an algorithm for the generalized search problem (searching $k$ marked items among $N$ items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity $O(\sqrt{N/k})$ as the Grover algorithm. A natural extension of the algorithm, incorporating auxiliary "monitor" qubits, can determine $k$ precisely, if it is unknown. The time complexity of our counting algorithm is $O(\sqrt{N})$, similar to the best quantum approximate counting algorithm, or better, given appropriate physical resources.

12 pages, 1 figure

References in corpus (1)

• How Powerful is Adiabatic Quantum Computation?

Cited by in corpus (5)

• Geometric aspects of analog quantum search evolutions
• Quantum Computing by Cooling
• Quantum algorithm of a set of quantum 2-sat problem
• Lorentz Quantum Computer
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics