论文标题
连续量子步行在顶点和边缘行走
Walking on Vertices and Edges by Continuous-Time Quantum Walk
论文作者
论文摘要
量子步行动力学遵守量子力学的定律具有额外的位置约束，这要求进化操作员是本地的，因为沃克必须在努力到远处的地方之前访问邻近的位置。通常，汉密尔顿人是从图形的邻接或拉普拉斯矩阵获得的，从顶点到相邻顶点获得了沃克啤酒花。在这项工作中，我们定义了连续时间量子步行的版本，该版本使步行者可以从顶点跳到边缘，反之亦然。作为一个应用程序，我们通过修改汉密尔顿的新版本的额外术语，取决于标记的顶点或标记的边缘的位置，类似于标准持续时间量子量子步行模型中所做的操作，从而分析了完整两部分图上的空间搜索算法。我们表明，找到顶点或边缘的最佳运行时间是$ o（\ sqrt {n_e}）$，成功概率$ 1-o（1）$，其中$ n_e $是完整的双位图形的边缘数。
The quantum walk dynamics obey the laws of quantum mechanics with an extra locality constraint, which demands that the evolution operator is local in the sense that the walker must visit the neighboring locations before endeavoring to distant places. Usually, the Hamiltonian is obtained from either the adjacency or the laplacian matrix of the graph and the walker hops from vertices to neighboring vertices. In this work, we define a version of the continuous-time quantum walk that allows the walker to hop from vertices to edges and vice versa. As an application, we analyze the spatial search algorithm on the complete bipartite graph by modifying the new version of the Hamiltonian with an extra term that depends on the location of the marked vertex or marked edge, similar to what is done in the standard continuous-time quantum walk model. We show that the optimal running time to find either a vertex or an edge is $O(\sqrt{N_e})$ with success probability $1-o(1)$, where $N_e$ is the number of edges of the complete bipartite graph.
