dorsal/arxiv
View SchemaQuantum Walks On Graphs
| Authors | Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0012090 |
| URL | https://arxiv.org/abs/quant-ph/0012090 |
| Journal | Proceedings of ACM Symposium on Theory of Computation (STOC'01), July 2001, p. 50-59 |
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.
{
"annotation_id": "c7c63b92-cebe-4a74-882b-78a0ebd3e8c9",
"date_created": "2026-03-02T18:01:42.010000Z",
"date_modified": "2026-03-02T18:01:42.010000Z",
"file_hash": "1fec198f82f590b3a9947eda7f9a5391cfa437a463a70ec003a3b4425629c10c",
"private": false,
"record": {
"abstract": "We set the ground for a theory of quantum walks on graphs- the generalization\nof random walks on finite graphs to the quantum world. Such quantum walks do\nnot converge to any stationary distribution, as they are unitary and\nreversible.\n However, by suitably relaxing the definition, we can obtain a measure of how\nfast the quantum walk spreads or how confined the quantum walk stays in a small\nneighborhood. We give definitions of mixing time, filling time, dispersion\ntime. We show that in all these measures, the quantum walk on the cycle is\nalmost quadratically faster then its classical correspondent. On the other\nhand, we give a lower bound on the possible speed up by quantum walks for\ngeneral graphs, showing that quantum walks can be at most polynomially faster\nthan their classical counterparts.",
"arxiv_id": "quant-ph/0012090",
"authors": [
"Dorit Aharonov",
"Andris Ambainis",
"Julia Kempe",
"Umesh Vazirani"
],
"categories": [
"quant-ph"
],
"journal_ref": "Proceedings of ACM Symposium on Theory of Computation (STOC\u002701),\n July 2001, p. 50-59",
"title": "Quantum Walks On Graphs",
"url": "https://arxiv.org/abs/quant-ph/0012090"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "731aa315-9a1c-4a52-b527-ed4a7b4c6c38",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}