One-dimensional quantum walks

ABSTRACT

We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard walk. Several striking differences between the quantum and classical cases are observed. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/\sqrt 2, t/\sqrt 2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(\sqrt t) from the origin with high probability. With an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/&pgr, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/\sqrt 2 in the limit. In the classical case both values are 1.

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: R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, and C. Racko. Random walks, universal traversal sequences, and the time complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, pages 218-223, 1979.
• 4: C. Bender and S. Orszag. Advanced Mathematical Methods for Scientists and Engineers. International Series in Pure and Applied Mathematics. McGraw-Hill, Inc., New York, 1978.
• 5: N. Bleistein and R. Handelsman. Asymptotic Expansions of Integrals. Holt, Rinehart and Winston, New York, 1975.
• 6: A. Childs, E. Farhi, S. Gutmann. An example of the difference between quantum and classical random walks. LANL preprint archive, quant-ph/0103020.
• 7: Li-Chen Chen , Mourad E. H. Ismail, On asymptotics of Jacobi polynomials, SIAM Journal on Mathematical Analysis, v.22 n.5, p.1442-1449, Sept. 1991 [doi>10.1137/0522092]
• 8: E. Coffman and G. Lueker. Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley, 1991.
• 9: P. Diaconis. Group Representations in Probability and Statistics, volume 11 of Lecture Notes-Monograph Series. Institute of Mathematical Statistics, Hayward, California, 1988.
• 10: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 11: H. Dym and H. P. McKean. Fourier Series and Integrals, volume 14 of Probability and Mathematical Statistics. Academic Press, New York, 1972.
• 12: E. Farhi and S. Gutmann. Quantum computation and decision trees. Physical Review A, 58:915-928, 1998.
• 13: R. Feynman and A. Hibbs. Quantum Mechanics and Path Integrals. McGraw-Hill, 1965.
• 14: W. Gosper. Decision procedure for indefinite hypergeometric summation. In Proceedings of the National Academy of Sciences of U.S.A., volume 75, pages 40-42, 1978.
• 15: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 16: 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]
• 17: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 18: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
• 20: Richard M. Karp , Michael Luby , A. Marchetti-Spaccamela, A probabilistic analysis of multidimensional bin packing problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.289-298, December 1984 [doi>10.1145/800057.808693]
• 21: J. Kemeny and J. Snell. Finite Markov Chains. Springer-Verlag, 1983.
• 22: G. Louchard. The brownian motion: a neglected tool for the complexity analysis of sorted tables manipulation. RAIRO Inform. Th., 17(4), 1983.
• 23: László Lovász , Ravi Kannan, Faster mixing via average conductance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.282-287, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301317]
• 24: D. Meyer. From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85:551-574, 1996. Also available from the Los Alamos Preprint Archive, quant-ph/9604003.
• 25: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 26: A. Nayak and A. Vishwanath. Quantum walk on the line. In preparation. Preliminary version available from the Los Alamos Preprint Archive, quant-ph/0010117.
• 27: Christos H. Papadimitriou, On selecting a satisfying truth assignment (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.163-169, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185365]
• 28: T. L. Saaty, Modern Nonlinear Equations. Dover Publications, 1981.
• 29: Uwe Schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.410, October 17-18, 1999
• 30: G. Szego, Orthogonal Polynomials, AMS, 4th edition, 1975.
• 31: E. C. Titchmarsh. The Theory of Functions. Oxford University Press, 2nd edition, 1979.
• 32: 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]
• 33: Doron Zeilberger, The method of creative telescoping, Journal of Symbolic Computation, v.11 n.3, p.195-204, March 1991 [doi>10.1016/S0747-7171(08)80044-2]

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:
Measurement, Performance, Theory, Verification