Speedup in adiabatic evolution based quantum algorithms

被引:20
作者
Sun Jie [1 ]
Lu SongFeng [1 ]
Liu Fang [1 ]
机构
[1] Huazhong Univ Sci & Technol, Sch Comp Sci & Technol, Wuhan 430074, Peoples R China
来源
SCIENCE CHINA-PHYSICS MECHANICS & ASTRONOMY | 2012年 / 55卷 / 09期
基金
中国国家自然科学基金;
关键词
adiabatic evolution; evolution paths; quantum computing;
D O I
10.1007/s11433-012-4854-y
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
In this context, we study three different strategies to improve the time complexity of the widely used adiabatic evolution algorithms when solving a particular class of quantum search problems where both the initial and final Hamiltonians are one-dimensional projector Hamiltonians on the corresponding ground state. After some simple analysis, we find the time complexity improvement is always accompanied by the increase of some other "complexities" that should be considered. But this just gives the implication that more feasibilities can be achieved in adiabatic evolution based quantum algorithms over the circuit model, even though the equivalence between the two has been shown. In addition, we also give a rough comparison between these different models for the speedup of the problem.
引用
收藏
页码:1630 / 1634
页数:5
相关论文
共 23 条
[11]   Quantum mechanics helps in searching for a needle in a haystack [J].
Grover, LK .
PHYSICAL REVIEW LETTERS, 1997, 79 (02) :325-328
[12]   Bounds for the adiabatic approximation with applications to quantum computation [J].
Jansen, Sabine ;
Ruskai, Mary-Beth ;
Seiler, Ruedi .
JOURNAL OF MATHEMATICAL PHYSICS, 2007, 48 (10)
[13]   Adiabatic approximation with exponential accuracy for many-body systems and quantum computation [J].
Lidar, Daniel A. ;
Rezakhani, Ali T. ;
Hamma, Alioscia .
JOURNAL OF MATHEMATICAL PHYSICS, 2009, 50 (10)
[14]   Validity of the adiabatic approximation in quantum mechanics [J].
MacKenzie, R. ;
Morin-Duchesne, A. ;
Paquette, H. ;
Pinel, J. .
PHYSICAL REVIEW A, 2007, 76 (04)
[15]  
Messiah A., 1999, Quantum Mechanics
[16]   Simple proof of equivalence between adiabatic quantum computation and the circuit model [J].
Mizel, Ari ;
Lidar, Daniel A. ;
Mitchell, Morgan .
PHYSICAL REVIEW LETTERS, 2007, 99 (07)
[17]   Quantum search by local adiabatic evolution [J].
Roland, J ;
Cerf, NJ .
PHYSICAL REVIEW A, 2002, 65 (04) :6
[18]   Sufficiency criterion for the validity of the adiabatic approximation [J].
Tong, D. M. ;
Singh, K. ;
Kwek, L. C. ;
Oh, C. H. .
PHYSICAL REVIEW LETTERS, 2007, 98 (15)
[19]   Adiabatic quantum computation with a one-dimensional projector Hamiltonian [J].
Tulsi, Avatar .
PHYSICAL REVIEW A, 2009, 80 (05)
[20]   How powerful is adiabatic quantum computation? [J].
van Dam, W ;
Mosca, M ;
Vazirani, U .
42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, :279-287