论文标题
量子步行时间的上限改进了上限
Improved Upper Bounds for the Hitting Times of Quantum Walks
论文作者
论文摘要
事实证明，连续时间量子步行是设计多种量子算法的非常有用的框架。通常，该框架中量子算法的运行时间的特征是量子打击时间：量子步行所需的时间以寻找感兴趣的顶点，并具有很高的概率。在本文中，我们为量子打击时间提供了改进的上限，可以应用于几种基于CTQW的量子算法。特别是，我们将技术应用于粘合树问题，改善了其受多项式因子的击球时间上限：从$ o（n^5）$到$ o（n^2 \ log n）$。此外，我们的方法还有助于指数地改善对基于连续的量子步行算法精确度的依赖性，以在Chakraborty等人的任何奇异，可逆的Markov链上找到明显的节点。 [PRA 102，022227（2020）]。
Continuous-time quantum walks have proven to be an extremely useful framework for the design of several quantum algorithms. Often, the running time of quantum algorithms in this framework is characterized by the quantum hitting time: the time required by the quantum walk to find a vertex of interest with a high probability. In this article, we provide improved upper bounds for the quantum hitting time that can be applied to several CTQW-based quantum algorithms. In particular, we apply our techniques to the glued-trees problem, improving their hitting time upper bound by a polynomial factor: from $O(n^5)$ to $O(n^2\log n)$. Furthermore, our methods also help to exponentially improve the dependence on precision of the continuous-time quantum walk based algorithm to find a marked node on any ergodic, reversible Markov chain by Chakraborty et al. [PRA 102, 022227 (2020)].
