中国物理B ›› 2012, Vol. 21 ›› Issue (1): 10306-010306.doi: 10.1088/1674-1056/21/1/010306

• • 上一篇    下一篇

Partial evolution based local adiabatic quantum search

孙杰1, 路松峰1, 刘芳1, 杨莉萍2   

  1. (1)School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074, China; (2)School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074, China; Department of Computer Science, Huazhong Agricultural University, Wuhan 430074, China
  • 收稿日期:2011-05-30 修回日期:2011-07-05 出版日期:2012-01-15 发布日期:2012-01-20
  • 基金资助:
    Project supported by the National Natural Science Foundation of China(Grant No. 61173050).

Partial evolution based local adiabatic quantum search

Sun Jie(孙杰)a), Lu Song-Feng(路松峰) a)†, Liu Fang(刘芳)a), and Yang Li-Ping(杨莉萍) a)b)   

  1. a School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074, China; b Department of Computer Science, Huazhong Agricultural University, Wuhan 430074, China
  • Received:2011-05-30 Revised:2011-07-05 Online:2012-01-15 Published:2012-01-20
  • Supported by:
    Project supported by the National Natural Science Foundation of China(Grant No. 61173050).

PDF (PC)

603

赞

摘要： Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original “global” one, this “new” algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M=1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.

关键词: partial adiabatic evolution, local adiabatic evolution, quantum search

Abstract: Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original “global” one, this “new” algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M=1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.

Key words: partial adiabatic evolution, local adiabatic evolution, quantum search

中图分类号:  (Quantum computation architectures and implementations)

  • 03.67.Lx
03.67.Ac (Quantum algorithms, protocols, and simulations)