论文标题
通过连续量子步行进行多标记的空间搜索
Multimarked Spatial Search by Continuous-Time Quantum Walk
论文作者
论文摘要
基于量子 - 步行的空间搜索问题旨在使用带有标记顶点的量子步行来找到标记的顶点。我们通过在任意图上连续量子步行来描述一个框架，以确定空间搜索的计算复杂性，以找到最佳的运行时间和算法的成功概率。量子步行是由源自图形的邻接矩阵衍生的哈密顿式驱动的，该图被标记的顶点的存在。我们框架的成功取决于邻接矩阵的特征值和特征向量的知识。随后，从真实对称矩阵$ m $的决定因素的根部获得了哈密顿量的光谱，其尺寸取决于标记的顶点的数量。特征向量由$ m $的内核的基础确定。我们通过用固定直径和两个标记的顶点求解约翰逊图上的空间搜索问题，以显示框架的每个步骤。我们的计算表明，最佳运行时间为$ o（\ sqrt {n}）$，渐近概率为$ 1+o（1）$，其中$ n $是顶点的数量。
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix $M$, the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of $M$. We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is $O(\sqrt{N})$ with an asymptotic probability of $1+o(1)$, where $N$ is the number of vertices.
