Quantum Walks On Graphs

Details Quantum Walks On Graphs Quantum Walks On Graphs

2000-12-18

arxiv.org/abs/quant-ph/0012090v2

Proceedings of ACM Symposium on Theory of Computation (STOC'01), July 2001, p. 50-59

Physics

Quantum Physics

10 pages, this version appeared

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Walks On Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Walks On Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Walks On Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181102