Abstract
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.
Similar content being viewed by others
References
Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory Comput. 1(4), 47–79 (2005)
Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, pp. 50–59 (2001)
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 37–49 (2001)
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1099–1108 (2005)
Ambainis, A.: Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 1, 507–518 (2003)
Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007)
Buhrman, H., Špalek, R.: Quantum verification of matrix products. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 880–889 (2006)
Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. Lond. Ser. A, Math. Phys. Sci. 454, 339–354 (1998)
Childs, A., Goldstone, J.: Spatial search and the Dirac equation. Phys. Rev. A 70, 042312 (2004)
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM Symposium on the Theory of Computing, pp. 212–219 (1996)
Kitaev, A.: Quantum measurements and the Abelian stabilizer problem. ECCC technical report 96-003 and arXiv:quant-ph/9511026 (1995)
Krovi, H., Magniez, F., Ozols, M., Roland, J.: Finding is as easy as detecting for quantum walks. In: Proceedings of 37st International Colloquium on Automata, Languages and Programming, LNCS (2010)
Kitaev, A.Yu., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. Graduate Studies in Mathematics, vol. 47. Am. Math. Soc., Providence (2002)
Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica 48(3), 221–232 (2007)
Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proceedings of the 39th ACM Symposium on Theory of Computing, pp. 575–584 (2007)
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 611–629 (2007)
Nayak, A., Vishwanath, A.: Quantum walk on the line. Technical report. arXiv:quant-ph/0010117 (2000)
Santha, M.: Quantum walk based search algorithms. In: Proceedings of the 5th Conference on Theory and Applications of Models of Computation, LNCS, vol. 4978, pp. 31–46 (2008)
Shenvi, N., Kempe, J., Whaley, K.: A quantum random walk search algorithm. Phys. Rev. A 67, 052307 (2003)
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Symposium on Foundations of Computer Science, pp. 32–41 (2004)
Tulsi, A.: Faster quantum walk algorithm for the two dimensional spatial search. Phys. Rev. A 78, 012310 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this article appeared in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 86–95, 2009.
Rights and permissions
About this article
Cite this article
Magniez, F., Nayak, A., Richter, P.C. et al. On the Hitting Times of Quantum Versus Random Walks. Algorithmica 63, 91–116 (2012). https://doi.org/10.1007/s00453-011-9521-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9521-6