标题： 量子与随机游走的首次通过时间 显示英文标题

标题： On the hitting times of quantum versus random walks

摘要： 在本文中，我们定义了新的蒙特卡洛类型的经典和量子命中时间，并证明了这些时间与已有的拉斯维加斯类型定义之间的几种关系。 特别是，我们表明对于某些标记状态，两种类型的命中时间在经典和量子情况下具有相同的阶数。 此外，我们证明对于任何可逆遍历马尔可夫链$P$，量子链$P$的量子命中时间的阶数与$P$的经典命中时间的平方根相同。 我们还研究了使用替代量子行走实现超过二次差距的可能性。 最后，我们提出了用于检测和查找问题的新量子算法。 这两个算法的复杂度与新的、可能更小的量子命中时间有关。 检测算法基于相位估计，特别简单。 查找算法结合了类似的基于相位估计的过程以及Tulsi在他最近关于二维网格的定理中的想法。 扩展他的结果，我们表明对于具有唯一标记状态的状态传递马尔可夫链，检测和查找问题的量子命中时间具有相同的阶数。 显示英文摘要

摘要： In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Further, we prove that for any reversible ergodic Markov chain $P$, the quantum hitting time of the quantum analogue of $P$ has the same order as the square root of the classical hitting time of $P$. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem for the 2D grid. Extending his result, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.