Quantum walks on graphs

ABSTRACT

We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

REFERENCES

• 1: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 2: 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]
• 3: Fang Chen , László Lovász , Igor Pak, Lifting Markov chains to speed up mixing, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.275-281, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301315]
• 4: [4] A. Childs, E. Farhi, S. Gutmann, An example of a difference between quantum and classical random walks. LANL preprint http://www.arxiv.org/abs/quant-ph/0103020.
• 5: [5] E. Farhi, S. Gutmann, Quantum computation and decision trees, Physical Review A, 58: 915-928, 1998.
• 6: 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]
• 7: [7] L. Lovasz and P. Winkler, Mixing times, in Microsurveys in Discrete Probability, Dimacs Series in Discrete Mathematics and Theoretical Computer Science, 41, eds. D. Aldous and J. Propp.
• 8: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 9: 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]
• 10: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 11: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing

General Terms:
Performance, Theory, Verification