中国物理B ›› 2017, Vol. 26 ›› Issue (1): 10301-010301.doi: 10.1088/1674-1056/26/1/010301

• GENERAL •    下一篇

Search algorithm on strongly regular graphsbased on scattering quantum walks

Xi-Ling Xue(薛希玲), Zhi-Hao Liu(刘志昊), Han-Wu Chen(陈汉武)   

  1. School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
  • 收稿日期:2016-08-13 修回日期:2016-10-24 出版日期:2017-01-05 发布日期:2017-01-05
  • 通讯作者: Han-Wu Chen E-mail:hanwu_chen@163.com
  • 基金资助:

    Project supported by the National Natural Science Foundation of China (Grant Nos. 61502101 and 61170321), the Natural Science Foundation of Jiangsu Province, China (Grant No. BK20140651), and the Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110092110024).

Search algorithm on strongly regular graphsbased on scattering quantum walks

Xi-Ling Xue(薛希玲), Zhi-Hao Liu(刘志昊), Han-Wu Chen(陈汉武)   

  1. School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
  • Received:2016-08-13 Revised:2016-10-24 Online:2017-01-05 Published:2017-01-05
  • Contact: Han-Wu Chen E-mail:hanwu_chen@163.com
  • Supported by:

    Project supported by the National Natural Science Foundation of China (Grant Nos. 61502101 and 61170321), the Natural Science Foundation of Jiangsu Province, China (Grant No. BK20140651), and the Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110092110024).

摘要:

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs (SRGs) with parameters (N,k,λ,μ) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm's performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs. The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as √N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O(√N) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.

关键词: scattering quantum walk, quantum search, strongly regular graph

Abstract:

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs (SRGs) with parameters (N,k,λ,μ) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm's performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs. The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as √N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O(√N) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.

Key words: scattering quantum walk, quantum search, strongly regular graph

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations) 03.65.Aa (Quantum systems with finite Hilbert space)