论文标题
通过连续时间量子步行进行空间搜索的最佳性
On the optimality of spatial search by continuous-time quantum walk
论文作者
论文摘要
量子步道最重要的算法应用之一是解决空间搜索问题。由Childs和Goldstone引入的一种广泛使用的量子算法[Phys。 Rev. A 70，022314（2004）]通过连续的量子步行在$ n $节点的图上找到一个明显的节点。如果可以在$ o（\ sqrt {n}）$时间中找到任何节点，则该算法是最佳的。但是，鉴于图形，没有知道算法的最优性的一般条件，并且先前的作品证明了对某些图的最佳量子搜索需要特定于实例的分析。实际上，量子搜索必须满足必要和充分条件的证明是最佳的，这是一个长期的开放问题。 在这项工作中，我们在解决这个问题方面取得了重大进展。我们得出一般的表达式，具体取决于哈密顿式行走的光谱特性，该特性预测了该量子搜索算法的性能，只要满足了某些光谱条件。我们的预测是有效的，例如，对于（归一化的）汉密尔顿人的频谱差距大于$ n^{ - 1/2} $。这使我们能够在此制度中得出必要和足够的条件，以实现最佳的量子搜索，并提供量子搜索是亚最佳的新示例。此外，通过扩展此分析，我们还能够显示出具有很小光谱间隙的某些图的量子搜索的最佳性，例如可以有效地将其分配到簇中的图。我们的结果表明，据我们所知，所有先前的结果在分析上都可以从我们的一般结果中恢复该算法对特定图的最佳性。
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of necessary and sufficient conditions a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work, we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than $n^{-1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide new examples of graphs where quantum search is sub-optimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
