Quantum adiabatic algorithms using unitary interpolation

doi:10.1088/1674-1056/ab5f02

Abstract We present two efficient quantum adiabatic algorithms for Bernstein-Vazirani problem and Simon's problem. We show that the time complexities of the algorithms for Bernstein-Vazirani problem and Simon's problem are O(1) and O(n), respectively, which are the same complexities as the corresponding algorithms in quantum circuit model. In these two algorithms, the adiabatic Hamiltonians are realized by unitary interpolation instead of standard linear interpolation. Comparing with the adiabatic algorithms using linear interpolation, the energy gaps of our algorithms keep constant. Therefore, the complexities are much easier to analyze using this method.

Keywords: adiabatic quantum computation quantum adiabatic algorithms

Received: 30 June 2019
Revised: 19 November 2019
Accepted manuscript online:

PACS:	03.67.Lx	(Quantum computation architectures and implementations)
	03.67.Ac	(Quantum algorithms, protocols, and simulations)

Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 11504430, 11805279, 61501514, and 61502526).

Corresponding Authors: Wan-Su Bao
E-mail: bws@qiclab.cn

Cite this article:

Shuo Zhang(张硕), Qian-Heng Duan(段乾恒), Tan Li(李坦), Xiang-Qun Fu(付向群), He-Liang Huang(黄合良), Xiang Wang(汪翔), Wan-Su Bao(鲍皖苏) Quantum adiabatic algorithms using unitary interpolation 2020 Chin. Phys. B 29 010308

[1]	Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A and Preda D 2001 Science 292 472
[2]	Mizel A, Lidar D A and Mitchell M 2007 Phys. Rev. Lett. 99 070502
[3]	Yu H, Huang Y and Wu B 2018 Chin. Phys. Lett. 35 110303
[4]	Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S and Regev O 2007 SIAM J. Comput. 37 166
[5]	Childs A M and Farhi E 2001 Phys. Rev. A 65 012322
[6]	Roland J and Nicolas J C 2005 Phys. Rev. A 71 032330
[7]	Roland J and Cerf N J 2002 Phys. Rev. A 65 042308
[8]	Das S, Kobes R and Kunstatter G 2002 Phys. Rev. A 65 062310
[9]	Wei Z and Ying M 2006 Phys. Lett. A 354 271
[10]	Sarandy M S and Lidar D A 2005 Phys. Rev. Lett. 95 250503
[11]	Sun J, Lu S, Liu F and Gao C 2014 Quantum Inf. Process. 13 731
[12]	Sun J, Lu S, Liu F, Gao C, Zhou Q and Zhang Z 2014 Chin. Phys. Lett. 31 070304
[13]	Hen I 2014 Europhys. Lett. 105 50005
[14]	Rao M V P 2003 Phys. Rev. A 67 052306
[15]	Long Y, Feng G, Tang Y, Qin W and Long G 2013 Phys. Rev. A 88 012306
[16]	Du J, Xu N, Peng X, Wang P, Wu S and Lu D 2010 Phys. Rev. Lett. 104 030502
[17]	Li Z, Dattani N S, Chen X, Liu X, Wang H, Tanburn R, Chen H, Peng X and Du J 2017 rXiv: 1706.08061
[18]	Kieu T D 2018 arXiv: 1808.02781.
[19]	Messiah A 1962 Quantum Mechanics, Vol. II (Amsterdam: North Holland Publishing Company)
[20]	Siu M S 2005 Phys. Rev. A 71 062314
[21]	Bernsterin E and Vazirani U 1997 SIAM J. Comput. 26 1411
[22]	Simon D R 1997 SIAM J. Comput. 26 1474
[23]	Kaye P, Laflamme R and Mosca M 2007 An Introduction to Quantum Computing (New York: Oxford University Press Inc.)
[24]	Li F, Bao W, Zhang S, Huang H, Li T, Wang X and Fu X 2018 Phys. Lett. A 382 2709
[25]	Wild D S, Gopalakrishnan S, Knap M, Yao N Y and Lukin M D 2016 Phys. Rev. Lett. 117 150501

[1]	Quantum algorithm for a set of quantum 2SAT problems Yanglin Hu(胡杨林), Zhelun Zhang(张哲伦), and Biao Wu(吴飙). Chin. Phys. B, 2021, 30(2): 020308.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Quantum adiabatic algorithms using unitary interpolation

Cite this article:

Online attention