论文标题
空间搜索中的阴影和差距
Of Shadows and Gaps in Spatial Search
论文作者
论文摘要
如果在图形的邻接矩阵上进行连续的时间量子步行，则进行空间搜索发生在相关图中，并适当地缩放，以及任何顶点引起的排名对一个扰动，将单位映射该图的主要特征向量到Verterex的特征向量。这种现象是Grover搜索的自然连续时间类似物。如果空间搜索以恒定的保真度发生并且与主要特征向量上的目标顶点的阴影成反比，则据说它是最佳的。扩展了Chakraborty等人的结果。 （物理评论A，102：032214，2020），我们证明了最佳空间搜索的更简单表征。基于此特征，我们观察到一些距离规则图的家族（例如锤锤和Grassmann图）具有最佳的空间搜索。我们还显示了与恒定保真度的空间搜索的匹配下限，这延伸了Farhi和Gutmann，以获得完美的保真度。我们的基本证明采用标准工具，例如Weyl不平等和库奇决定因素公式。
Spatial search occurs in a connected graph if a continuous-time quantum walk on the adjacency matrix of the graph, suitably scaled, plus a rank-one perturbation induced by any vertex will unitarily map the principal eigenvector of the graph to the characteristic vector of the vertex. This phenomenon is a natural continuous-time analogue of Grover search. The spatial search is said to be optimal if it occurs with constant fidelity and in time inversely proportional to the shadow of the target vertex on the principal eigenvector. Extending a result of Chakraborty et al. (Physical Review A, 102:032214, 2020), we prove a simpler characterization of optimal spatial search. Based on this characterization, we observe that some families of distance-regular graphs, such as Hamming and Grassmann graphs, have optimal spatial search. We also show a matching lower bound on time for spatial search with constant fidelity, which extends a bound due to Farhi and Gutmann for perfect fidelity. Our elementary proofs employ standard tools, such as Weyl inequalities and Cauchy determinant formula.
