Coins make quantum walks faster

ABSTRACT

We show how to search N items arranged on a √N × √N grid in time O(√N log N), using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom. since it has been shown recently that such a continuous time walk needs time Ω(N) to perform the same task. Our result improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of O(√N) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Ω(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(√N log N).

REFERENCES

• 1: Scott Aaronson , Andris Ambainis, Quantum Search of Spatial Regions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.200, October 11-14, 2003
• 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: 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]
• 4: Andris Ambainis, Quantum Walk Algorithm for Element Distinctness, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.22-31, October 17-19, 2004 [doi>10.1109/FOCS.2004.54]
• 5: {AKR04} A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster. Technical report, lanl-arXive quant-ph/0402107, 2004.
• 6: {Ben02} Paul Benioff. Space searches with a quantum robot. In Quantum computation and information (Washington, DC, 2000), volume 305 of Contemp. Math., pages 1--12. Amer. Math. Soc., Providence. RI, 2002.
• 7: {BHMT02} G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum computation and information (Washington, DC, 2000), volume 305 of Contemp. Math., pages 53--74. Amer. Math. Soc., Providence, RI, 2002.
• 8: Andrew M. Childs , Richard Cleve , Enrico Deotto , Edward Farhi , Sam Gutmann , Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780552]
• 9: {CE03} A. M. Childs and J. M. Eisenberg. Quantum algorithms for subset finding. Technical report, lanl-arXive quant-ph/0311038, 2003.
• 10: 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]
• 11: {CG03} A. M. Childs and J. Goldstone. Spatial search by quantum walk. Phys. Rev. A, 70:022314, 2004. Also lanl-report quant-ph/0306054, 2003.
• 12: {CG04} A. M. Childs and J. Goldstone. Spatial search and the Dirac equation. Technical report, lanl-arXive quant-ph/0405120, 2004.
• 13: {FG98} E. Farhi and S. Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58:915--928, 1998.
• 14: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 15: {Kem03a} J. Kempe. Quantum random walks - an introductory overview. Contemporary Physics, 44(4):302--327, 2003. lanl-arXive quant-ph/0303081.
• 16: {Kem03b} J. Kempe. Quantum walks hit exponentially faster. In RANDOM-APPROX 2003, Lecture Notes in Computer Science, pages 354--369, Heidelberg, 2003. Springer. lanl-arXiv quant-ph/0205083.
• 17: {Mey96} D. Meyer. From quantum cellular automata to quantum lattice gases. J. Stat. Phys., 85:551--574, 1996.
• 18: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 19: 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
• 20: Frédéric Magniez , Miklos Santha , Mario Szegedy, Quantum algorithms for the triangle problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 21: {SKW03} N. Shenvi, J. Kempe, and K. B. Whaley. A quantum random walk search algorithm. Phys. Rev. A, 67(5):052307, 2003. lanl-arXive quant-ph/0210064.
• 22: {She03} Neil Shenvi. Random Walk Simulations. unpublished.
• 23: {Sze04} M. Szegedy. Spectra of quantized walks and a √Δε rule, quant-ph/0401053.
• 24: Mario Szegedy, Quantum Speed-Up of Markov Chain Based Algorithms, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.32-41, October 17-19, 2004 [doi>10.1109/FOCS.2004.53]