Open AccessScattering quantum walk search algorithm on star graph
Author(s) -
Yanmei Liu,
Hanwu Chen,
Zhihao Liu,
Xiling Xue,
Wanning Zhu
Publication year - 2015
Publication title -
wuli xuebao
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.199
H-Index - 47
ISSN - 1000-3290
DOI - 10.7498/aps.64.010301
Subject(s) - quantum walk , quantum algorithm , algorithm , computer science , star (game theory) , quantum computer , a* search algorithm , quantum , graph , theoretical computer science , statistical physics , physics , quantum mechanics , astrophysics
Quantum walk is a typical quantum computing model which is receiving significant attention in recent years from theory researchers. In this paper, we prove that the two major formulations for discrete quantum walks, coined and scattering, are unitarily equivalent on star graph. We then propose a new quantum search algorithm on star graph based on the scattering quantum walk. It is shown that the temporal complexity of the algorithm is the same as that in Grover algorithm, but success probability is greater than that in Grover algorithm when the objects are more than one third of total items.