Two models of quantum random walk

• Authors: Jozef Košík
• Languages of publication: EN

Abstracts

EN

We present an overview of two models of quantum random walk. In the first model, the discrete quantum random walk, we present the explicit solution for the recurring amplitude of the quantum random walk on a one-dimensional lattice. We also introduce a new method of solving the problem of random walk in the most general case and use it to derive the hitting amplitude for quantum random walk on the hypercube. The second is a special model based on a local interaction between neighboring spin-1/2 particles on a one-dimensional lattice. We present explicit results for the relevant quantities and obtain an upper bound on the speed of convergence to limiting probability distribution.

Keywords

EN

quantum information; random walk; hypercube; 03.67.-a ; 05.40.-a

• Publisher: De Gruyter Open
• Journal: Open Physics
• Year: 2003
• Volume: 1
• Issue: 4
• Pages: 556-573

Dates

published

1 - 12 - 2003

online

1 - 12 - 2003

Contributors

author

Jozef Košík

• Research Centre for Quantum Information, Slovak Academy of Sciences, Dúbravská cesta 9, 845 11, Bratislava, Slovakia

References

• [1] Milton Abramowitz and Irene A. Stegun: Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tools, U.S. Department of Commerce, National Bureau of Standards, Applied Mathematical Series, 1964–1972.
• [2] D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani: Quantum Walks On Graphs, quant-ph/0012090 v1.
• [3] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous: “One-dimensional quantum walks”, In: Proc. of 33 rd Ann. ACM Symp. on Theory of Computing, pp. 37–49.
• [4] P.W. Shor: In Proc. of the 35th Annual Symposium on Foundations of Computer Science IEEE Computer Society Press, Los Alamitos CA, 1994, pp. 124. http://dx.doi.org/10.1109/SFCS.1994.365700[Crossref]
• [5] J. Kempe: Quantum random walk hit exponentially faster, quant-ph/0205083 v1.
• [6] Norio Konno: A new type of limit theorems for the one-dimensional quantum random walk, quant-ph/0206103.
• [7] C. Moore and A. Russel: Quantum walks on the hypercube, quant-ph0104137.
• [8] David A. Meyer: From quantum Cellular Automata to Quantum Lattice Gases, quant-ph/9604003v2.
• [9] A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, D.A. Spielman: Exponential algorithmic speedup by quantum walk, quant-ph/0209131.
• [10] N. Shenvi, J. Kempe, K.B. Whaley: A quantum random walk search algorithm, quant-ph/0210064.
• [11] A. Nayak and A. Vishwanath: Quantum Walk on the Line, quant-ph/0010117 v1.
• [12] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000, ISBN 0-52163503-9.
• [13] A.M. Childs, E. Farhi, S. Gutman: An example of the difference between quantum and classical random walks, quant-ph/0103020.

Identifiers

DOI

10.2478/BF02475903