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 条
[1]   Adiabatic quantum computation is equivalent to standard quantum computation [J].
Aharonov, Dorit ;
Van Dam, Wim ;
Kempe, Julia ;
Landau, Zeph ;
Lloyd, Seth ;
Regev, Oded .
SIAM JOURNAL ON COMPUTING, 2007, 37 (01) :166-194
[2]   Anderson localization makes adiabatic quantum optimization fail [J].
Altshuler, Boris ;
Krovi, Hari ;
Roland, Jeremie .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2010, 107 (28) :12446-12450
[3]   Consistency of the Adiabatic Theorem [J].
Amin, M. H. S. .
PHYSICAL REVIEW LETTERS, 2009, 102 (22)
[4]   On the adiabatic quantum evolution of a single qubit [J].
Andrecut, M ;
Ali, MK .
INTERNATIONAL JOURNAL OF QUANTUM INFORMATION, 2004, 2 (04) :447-452
[5]  
[Anonymous], ARXIVQUANTPH10101220
[6]  
[Anonymous], ARXIVQUANTPH0208135
[7]  
[Anonymous], LIMITS QUANTUM ADIAB
[8]   General conditions for quantum adiabatic evolution [J].
Comparat, Daniel .
PHYSICAL REVIEW A, 2009, 80 (01)
[9]   Energy and efficiency of adiabatic quantum search algorithms [J].
Das, S ;
Kobes, R ;
Kunstatter, G .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2003, 36 (11) :2839-2845
[10]   A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem [J].
Farhi, E ;
Goldstone, J ;
Gutmann, S ;
Lapan, J ;
Lundgren, A ;
Preda, D .
SCIENCE, 2001, 292 (5516) :472-476