On the Hitting Times of Quantum Versus Random Walks
On the Hitting Times of Quantum Versus Random Walks
复制标题
论量子游走与随机游走的命中时间
DOI：
10.1007/s00453-011-9521-6
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
M. Santha
中科院分区：
文献类型：
--
作者：
F. Magniez;A. Nayak;Peter C. Richter;M. Santha
经典的随机游走（马尔可夫链）的命中时间是检测或等价地发现标记状态的存在所需的时间。量子漫步的命中时间定义起来更微妙;特别是，我们不知道检测和寻找问题是否具有相同的时间复杂度。本文定义了新的Monte Carlo型经典击中时和量子击中时，并证明了它们与已有的拉斯维加斯型定义之间的关系。特别地，我们证明了对于某些标记态，这两种类型的击中时间在经典和量子情况下是相同的顺序。然后，我们提出了新的量子算法的检测和发现问题。这两种算法的复杂性都与新的、可能更小的量子命中时间有关。该检测算法基于相位估计，并且特别简单。该发现算法将类似的基于相位估计的过程与Tulsi最近的定理（Tulsi A.：A 78：012310 2008）用于2D网格。扩展他的结果，我们表明，我们可以找到一个独特的标记元素具有恒定的概率和检测的一个大类的量子行走的状态传递可逆遍历马尔可夫链的量子模拟具有相同的复杂性。此外，我们证明了，对于任何可逆遍历马尔可夫链P，量子击中时间的量子模拟P具有相同的顺序作为平方根的经典击中时间的P.我们还调查（IM）的可能性，实现一个间隙大于二次使用替代量子行走。在这样做的时候，我们定义了一个概念的可逆性广泛的类的量子行走，并显示如何从任何这样的量子行走的经典模拟。对于建立在反射上的量子行走的特殊情况，我们证明了经典模拟的命中时间正好是量子行走的平方。
The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of—or equivalently, to find—a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. 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. Then, 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 (Tulsi A.: Phys. Rev. A 78:012310 2008) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. 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. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.