Exponential algorithmic speedup by a quantum walk

ABSTRACT

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Dorit Aharonov , Andris Ambainis , Julia Kempe , Umesh Vazirani, Quantum walks on graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.50-59, July 2001, Hersonissos, Greece [doi>10.1145/380752.380758]
• 3: Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780546]
• 4: Andris Ambainis , Eric Bach , Ashwin Nayak , Ashvin Vishwanath , John Watrous, One-dimensional quantum walks, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.37-49, July 2001, Hersonissos, Greece [doi>10.1145/380752.380757]
• 5: J. N. de Beaudrap, R. Cleve, and J. Watrous. Sharp quantum vs. classical query complexity separations. Algorithmica, 34:449--461, 2002.
• 6: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 7: Andrew M. Childs , Edward Farhi , Sam Gutmann, An Example of the Difference Between Quantum and Classical Random Walks, Quantum Information Processing, v.1 n.1-2, p.35-43, April 2002 [doi>10.1023/A:1019609420309]
• 8: W. van Dam and S. Hallgren. Efficient quantum algorithms for shifted quadratic character problems. quant-ph/0011067.
• 9: W. van Dam and G. Seroussi. Efficient quantum algorithms for estimating Gauss sums. Unpublished.
• 10: D. Deutsch. Quantum theory, the Church-Turing principle, and the universal quantum computer. Proc. Roy. Soc. London A, 400:96--117, 1985.
• 11: D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc. Roy. Soc. London A, 439:553--558, 1992.
• 12: E. Farhi and S. Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58:915--928, 1998.
• 13: J. Goldstone. Personal communication, Sept. 2002.
• 14: Michelangelo Grigni , Leonard Schulman , Monica Vazirani , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece [doi>10.1145/380752.380769]
• 15: Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510001]
• 16: Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335392]
• 17: G. Ivanos, F. Magniez, and M. Santha. Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. quant-ph/0102014.
• 18: J. Kempe. Quantum random walks hit exponentially faster. quant-ph/0205083.
• 19: A. Kitaev. Quantum measurements and the abelian stabilizer problem. quant-ph/9511026.
• 20: S. Lloyd. Universal quantum simulators, Science 273:1073--1078, 1996.
• 21: D. A. Meyer. From quantum cellular automata to quantum lattice gasses. J. Stat. Phys., 85:551--574, 1996.
• 22: Cristopher Moore , Alexander Russell, Quantum Walks on the Hypercube, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.164-178, September 13-15, 2002
• 23: Michele Mosca , Artur Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.174-188, February 17-20, 1998
• 24: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 25: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 26: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 27: V. G. Vizing. On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., 3:25--30, 1964.
• 28: John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece [doi>10.1145/380752.380759]
• 29: John Watrous, Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences, v.62 n.2, p.376-391, March 2001 [doi>10.1006/jcss.2000.1732]
• 30: Avi Wigderson, The Complexity of Graph Connectivity, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.112-132, August 24-28, 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory

Keywords:
quantum algorithms, quantum walks