Abstract.
This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of 33rd ACM STOC, ACM, New York, NY, pp. 50–59, 2001
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of 33rd ACM STOC, ACM, New York, NY, pp. 60–69, 2001
Aldous, D., Fill, J.: Reversible markov chains and random walks on graphs. Unpublished, preprint available at http://stat-www.berkeley.edu/users/aldous/book.html.
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. Siam J. Comput. 26, 1510–1523, (1997)
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D. A.: Exponential algorithmic speedup by a quantum walk. In: Proceedings of 35th ACM STOC, pp. 59–68, 2003
Childs, A., Farhi, E., Gutmann, S.: An example of the difference between quantum and classical random walks. Quantum Information Processing 1, 35 (2002)
Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38 (1), 1–17 January (1991)
Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915–928 (1998)
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM STOC, pages 212–219, Philadelphia, Pennsylvania, ACM Press, 1996
Grigni, M., Schulman, L., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In: Proceedings of the 33rd ACM STOC, pp. 68–74, 2001
Hallgren, S., Russell, A., Ta-Shma, A.: Normal subgroup reconstruction and quantum computation using group representations. In: Proceedings of the 32nd ACM STOC, pp. 627–635, 2000
Hofmeister, T., Schöning, U., Watanabe, O.: A probabilistic 3-SAT algorithm further improved. In: Helmut Alt and Afonso Ferreira, (eds.), STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14–16, 2002, Proceedings, volume 2285 of Lecture Notes in Computer Science pp. 192–202. Springer, 2002
Jerrum, M., Sinclair, A.: Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82 (1) 93–133 (1989)
Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In: Proceedings of the 33rd ACM STOC, ACM, New York, NY, pp. 712–721, 2001
Kempe, J.: Quantum random walks - an introductory overview. Contemporary Physics 44 (4), 302–327 (2003)
Kempe, J.: Quantum walks hit exponentially faster. In: RANDOM-APPROX 2003, Lecture Notes in Computer Science, Heidelberg, Springer, pp. 354–369, 2003
Meyer, D.: From quantum cellular automata to quantum lattice gases. J. Stat. Phys. 85, 551–574 (1996)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, 1995
Moore, C., Russell, A.: Quantum walks on the hypercube. In: Proc. RANDOM 2002, Lecture Notes in Computer Science, Cambridge, MA, Springer, pp. 164–178, 2002
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK, 2000
Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading, Massachusetts, 1994
Schöning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: 40th Annual Symposium on Foundations of Computer Science, IEEE, pp. 410–414, 1999
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comp. 26 (5), 1484–1509 (1997)
Simon, D.: On the power of quantum computation. SIAM J. Comp. 26 (5), 1474–1483 (1997)
Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67 (5), 052307 (2003)
Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comp. Sys. Sci. 62 (2), 376–391 (2001)
Yamasaki, T.: private communication.
Yamasaki, T., Kobayashi, H., Imai, H.: An analysis of absorbing times of quantum walks. In: C. Calude, M.J. Dinneen, and F. Peper, editors, Unconventional Models of Computation, Third International Conference, UMC 2002, Kobe, Japan, October 15–19, 2002, Proceedings, volume 2509 of Lecture Notes in Computer Science, Springer, pp. 315–330, 2002
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kempe, J. Discrete Quantum Walks Hit Exponentially Faster. Probab. Theory Relat. Fields 133, 215–235 (2005). https://doi.org/10.1007/s00440-004-0423-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-004-0423-2