论文标题
搜索vertex传递图的lactadisical量子步行
Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
论文作者
论文摘要
Lactaisical量子步行是一个离散的时间，在每个顶点的加权自循环的图表上都有一个离散的量子行走。它使用了广义的Grover硬币和触发器移位，这使其与Szegedy的量子马尔可夫链相等。已经表明，缺乏的量子步行可以改善完整图，离散的圆环，循环和常规完整的两分图上的空间搜索。在本文中，我们观察到这些都是顶点传递图，当有一个唯一标记的顶点时，自循环的最佳权重等于无环形图的程度除以顶点的总数。我们建议，对于所有带有唯一标记的顶点的顶点传输图，这都可以。我们提供了支持这一假设的许多数值模拟，包括对任意维度，强烈规则图，约翰逊图和HyperCube的定期立方晶格进行搜索。
The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph with a weighted self-loop at each vertex. It uses a generalized Grover coin and the flip-flop shift, which makes it equivalent to Szegedy's quantum Markov chain. It has been shown that a lackadaisical quantum walk can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. In this paper, we observe that these are all vertex-transitive graphs, and when there is a unique marked vertex, the optimal weight of the self-loop equals the degree of the loopless graph divided by the total number of vertices. We propose that this holds for all vertex-transitive graphs with a unique marked vertex. We present a number of numerical simulations supporting this hypothesis, including search on periodic cubic lattices of arbitrary dimension, strongly regular graphs, Johnson graphs, and the hypercube.
