Dorit Aharonov
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.
- {1} D. Aharonov, A. Kitaev, and N. Nisan. Quantum circuits with mixed states. Proceedings of STOC'98, pp. 20-30. Google Scholar
Digital Library
- {2} A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous, One-dimensional quantum walks. Proceedings of STOC'01. Google ScholarDigital Library
- {3} F. Chen, L. Lovasz and I. Pak, Lifting Markov chains to speed up mixing, Proceedings of STOC'99, pp. 275-281. Google ScholarDigital Library
- {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. Google ScholarDigital Library
- {5} E. Farhi, S. Gutmann, Quantum computation and decision trees, Physical Review A, 58: 915-928, 1998.Google ScholarCross Ref
- {6} L. Grover, A fast quantum mechanical algorithm for database search Proceedings of STOC'96, pp. 212-219. Google ScholarDigital Library
- {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.Google Scholar
- {8} M. Nielsen, I. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google ScholarDigital Library
- {9} P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comp., 26 : 1484-1509, 1997. Google ScholarDigital Library
- {10} A. Sinclair, Algorithms for Random Generation and Counting, a Markov Chain Approach, Birkhauser, 1993. Google ScholarDigital Library
- {11} A. Sinclair and M. Jerrum, Approximate counting, generation, and rapidly mixing Markov chains, Information and Computation, 82 : 93-133, 1989. Google ScholarDigital Library
Index Terms
- Quantum walks on graphs
Recommendations
Quantum walks: a comprehensive review
Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of ...
Generalized teleportation by quantum walks
We develop a generalized teleportation scheme based on quantum walks with two coins. For an unknown qubit state, we use two-step quantum walks on the line and quantum walks on the cycle with four vertices for teleportation. For any d-dimensional states, ...
Experimental realization of quantum teleportation using coined quantum walks
AbstractThe goal of teleportation is to transfer the state of one particle to another particle. In coined quantum walks, conditional shift operators can introduce entanglement between position space and coin space. This entanglement resource can be used ...
Comments