| GENERAL |
|
|
|
|
Resonant Quantum Search with Monitor Qubits |
| Frank Wilczek1,2,3,4,5, Hong-Ye Hu6, Biao Wu7,3,8 |
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
|
|
| Cite this article: |
|
Frank Wilczek, Hong-Ye Hu, Biao Wu 2020 Chin. Phys. Lett. 37 050304 |
|
|
|
|
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.
|
|
Received: 24 April 2020
Published: 27 April 2020
|
|
| PACS: |
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
89.70.Eg
|
(Computational complexity)
|
|
|
| Fund: B.W. is supported by the National Key R&D Program of China (Grant Nos. 2017YFA0303302 and 2018YFA0305602), the National Natural Science Foundation of China (Grant No. 11921005), and Shanghai Municipal Science and Technology Major Project (Grant No. 2019SHZDZX01). F.W. is supported by the Swedish Research Council (Contract No. 335–2014-7424), U.S. Department of Energy (Contract No. de-sc0012567), and the European Research Council (Grant No. 742104). |
|
|
|
| [1] | Shor P W 1997 SIAM J. Comput. 26 1484 |
| [2] | Grover L K 1997 Phys. Rev. Lett. 79 325 |
| [3] | Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000) |
| [4] | Farhi E and Gutmann S 1998 Phys. Rev. A 57 2403 |
| [5] | Farhi E, Goldstone J, Gutmann S and Sipser M 2000 arXiv:quant-ph/0001106v1 |
| [6] | Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S and Regev O 2007 SIAM J. Comput. 37 166 |
| [7] | Yu H Y, Huang Y L and Wu B 2018 Chin. Phys. Lett. 35 110303 |
| [8] | Wu B, Yu H Y and Wilczek F 2020 Phys. Rev. A 101 012318 |
| [9] | van Dam Wim, Mosca M and Vazirani U 2002 Proceedings of the 42nd Annual Symposium on Foundations of Computer Science p. 279 |
| [10] | Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 |
| [11] | Wie C R 2019 Quantum Inf. Comput. 19 0967 |
| [12] | Aaronson S and Rall P 2019 arXiv:1908.10846v2 |
| [13] | Scully M O and Zubairy M S 1997 Quantum Optics (Cambridge University Press, Cambridge, 1997) |
| [14] | Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A and Preda D 2001 Science 292 472 |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
