Chin. Phys. Lett.  2020, Vol. 37 Issue (5): 050304    DOI: 10.1088/0256-307X/37/5/050304
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
Download: PDF(582KB)   PDF(mobile)(598KB)   HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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).
URL:       OR
E-mail this article
E-mail Alert
Articles by authors
Frank Wilczek
Hong-Ye Hu
Biao Wu
[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
Related articles from Frontiers Journals
[1] Hao Cao, Wenping Ma, Ge Liu, Liangdong Lü, Zheng-Yuan Xue. Quantum Secure Multiparty Computation with Symmetric Boolean Functions[J]. Chin. Phys. Lett., 2020, 37(5): 050304
[2] Li-Hua Lu, You-Quan Li. Quantum Approach to Fast Protein-Folding Time[J]. Chin. Phys. Lett., 2019, 36(8): 050304
[3] Hongye Yu, Yuliang Huang, Biao Wu. Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm[J]. Chin. Phys. Lett., 2018, 35(11): 050304
[4] E. Rezaei Fard, K. Aghayar. Quantum Adiabatic Evolution for Pattern Recognition Problem[J]. Chin. Phys. Lett., 2017, 34(12): 050304
[5] Bo-Wen Ma, Wan-Su Bao, Tan Li, Feng-Guang Li, Shuo Zhang, Xiang-Qun Fu. A Four-Phase Improvement of Grover's Algorithm[J]. Chin. Phys. Lett., 2017, 34(7): 050304
[6] Chuan-Qi Liu, Chang-Hua Zhu, Lian-Hui Wang, Lin-Xi Zhang, Chang-Xing Pei. Polarization-Encoding-Based Measurement-Device-Independent Quantum Key Distribution with a Single Untrusted Source[J]. Chin. Phys. Lett., 2016, 33(10): 050304
[7] Xing Chen, Zhen-Wei Zhang, Huan Zhao, Nuan-Rang Wang, Ren-Fu Yang, Ke-Ming Feng. Exact Solution to Spin Squeezing of the Arbitrary-Range Spin Interaction and Transverse Field Model[J]. Chin. Phys. Lett., 2016, 33(10): 050304
[8] SONG Xiao-Tian, LI Hong-Wei, YIN Zhen-Qiang, LIANG Wen-Ye, ZHANG Chun-Mei, HAN Yun-Guang, CHEN Wei, HAN Zheng-Fu. Phase-Coding Self-Testing Quantum Random Number Generator[J]. Chin. Phys. Lett., 2015, 32(08): 050304
[9] ZHAO Shun-Cai, ZHANG Shuang-Ying, WU Qi-Xuan, JIA Jing. Left-Handedness with Three Zero-Absorption Windows Tuned by the Incoherent Pumping Field and Inter-Dot Tunnelings in a GaAs/AlGaAs Triple Quantum Dots System[J]. Chin. Phys. Lett., 2015, 32(5): 050304
[10] CHEN Xiao-Yu. Determining Separability with Entanglement of Formation and Entanglement Sudden Death[J]. Chin. Phys. Lett., 2015, 32(01): 050304
[11] CAO Xin, SHANG Yun. Fermionic One-Way Quantum Computation[J]. Chin. Phys. Lett., 2014, 31(11): 050304
[12] SUN Jie, LU Song-Feng, LIU Fang, ZHOU Qing, ZHANG Zhi-Gang. Adiabatic Deutsch–Jozsa Problem Solved by Modifying the Initial Hamiltonian[J]. Chin. Phys. Lett., 2014, 31(07): 050304
[13] LI Tan, BAO Wan-Su, LIN Wen-Qian, ZHANG Hou, FU Xiang-Qun. Quantum Search Algorithm Based on Multi-Phase[J]. Chin. Phys. Lett., 2014, 31(05): 050304
[14] SHANG Ru-Nan, LI Hai-Ou, CAO Gang, YU Guo-Dong, XIAO Ming, TU Tao, GUO Guo-Ping. Probing Energy Spectrum of Quadruple Quantum Dots with Microwave Field[J]. Chin. Phys. Lett., 2014, 31(05): 050304
[15] ZHONG Zhi-Rong. Coherent Operation of the Collective Atomic Modes in the Coupled Cavity System[J]. Chin. Phys. Lett., 2013, 30(8): 050304
Full text