publication . Preprint . Conference object . Other literature type . 2000

Quantum Walks On Graphs

Aharonov, Dorit; Ambainis, Andris; Kempe, Julia; Vazirani, Umesh;
Open Access English
  • Published: 17 Dec 2000
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...
Subjects
arXiv: Mathematics::Probability
free text keywords: Quantum Physics, Continuous-time quantum walk, Mathematics, Quantum algorithm, Quantum process, Quantum t-design, Quantum capacity, Quantum operation, Combinatorics, Quantum walk, Discrete mathematics, Classical capacity
Funded by
NSF| A Proposal for Research on Quantum Computation and Clustering Algorithms
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 9800024
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations

[1] D. Aharonov, A. Kitaev, and N. Nisan. Quantum circuits with mixed states. Proceedings of STOC'98, pp. 20-30.

[2] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous, One-dimensional quantum walks. Proceedings of STOC'01.

[3] F. Chen, L. Lovasz and I. Pak, Lifting Markov chains to speed up mixing, Proceedings of STOC'99, pp. 275-281.

[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] E. Farhi, S. Gutmann, Quantum computation and decision trees, Physical Review A, 58 : 915-928, 1998.

[6] L. Grover, A fast quantum mechanical algorithm for database search Proceedings of STOC'96, pp. 212-219.

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue