Laplacian versus adjacency matrix in quantum walk search

详细信息    查看全文

• 作者：Thomas G. Wong ; Luís Tarrataca ; Nikolay Nahimov
• 关键词：Quantum walk ; Continuous time ; Spatial search ; Laplacian ; Adjacency matrix
• 刊名：Quantum Information Processing
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：15
• 期：10
• 页码：4029-4048
• 全文大小：711 KB
• 刊物类别：Physics and Astronomy
• 刊物主题：Physics
  Physics
  Mathematics
  Engineering, general
  Computer Science, general
  Characterization and Evaluation Materials
  
• 出版者：Springer Netherlands
• ISSN：1573-1332
• 卷排序：15

文摘

A quantum particle evolving by Schrödinger’s equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace’s operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.