Quantum Search Algorithm for Exceptional Vertexes in Regular Graphs and its Circuit Implementation

作     者：Dong, Yumin Liu, Zhixin Zhang, Jinlei 

作者机构：Chongqing Normal Univ Coll Comp & Informat Sci Chongqing 401331 Peoples R China 

出 版 物：《INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS》 (国际理论物理学杂志)

年 卷 期：2021年第60卷第8期

页      面：2723-2732页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 

基　　金：National Natural Science Foundation of China [61772295, 61572270, 61173056] PHD foundation of Chongqing Normal University [19XLB003] Science and Technology Research Program of Chongqing Municipal Education Commission [KJZD-M202000501] Chongqing Technology Innovation and application development special general project [cstc2020jscx-lyjsAX0002] 

主　　题：Quantum algorithm Quantum circuit Regular graph Graph theory 

摘      要：There are some interesting properties in quantum mechanics, such as quantum superposition and entanglement. We can use these features to solve some specific problems. Quantum computer has more advantages than classical computer in many problems. In this paper, we are interested in regular graph. A special case of graph structure destroyed is given. We present a search algorithm to find exceptional vertexes in the graph in this case. The algorithm uses the trick of amplitude amplification in quantum search algorithm. In the corresponding classical algorithm, the adjacency matrix may be used to store the information of vertex and edge of graph. It takes one time for the best and N times for the worst to find the target. Which means that N/2 times on average need to be conducted. In our quantum algorithm, nodes and vertexes are stored in quantum states, using quantum search to design algorithm. The search process can be accelerated in our quantum algorithm.