1Center for Theoretical Physics, MIT, Cambridge, MA 02139, USA 2D. Lee Institute, Shanghai Jiao Tong University, Shanghai 200240, China 3Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China 4Department of Physics, Stockholm University, Stockholm, SE-106 91, Sweden 5Department of Physics, Arizona State University, Tempe, AZ 25287, USA 6Department of Physics, University of Californian, San Diego, CA 92093, USA 7International Center for Quantum Materials, School of Physics, Peking University, Beijing 100871, China 8Collaborative Innovation Center of Quantum Matter, Beijing 100871, China
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.
2020, Vol. 37 
