dorsal/arxiv
View SchemaQuantum Walk on the Line
| Authors | Ashwin Nayak, Ashvin Vishwanath |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0010117 |
| URL | https://arxiv.org/abs/quant-ph/0010117 |
Abstract
Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.
{
"annotation_id": "bcdd0835-f55a-487c-b4cf-fbe484e847b7",
"date_created": "2026-03-02T18:01:42.592000Z",
"date_modified": "2026-03-02T18:01:42.592000Z",
"file_hash": "c29401a78517379c10491f709899795d55c84ec65cbce4988aa69d023ab170ee",
"private": false,
"record": {
"abstract": "Motivated by the immense success of random walk and Markov chain methods in\nthe design of classical algorithms, we consider_quantum_ walks on graphs. We\nanalyse in detail the behaviour of unbiased quantum walk on the line, with the\nexample of a typical walk, the ``Hadamard walk\u0027\u0027. We show that after t time\nsteps, the probability distribution on the line induced by the Hadamard walk is\nalmost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This\nimplies that the same walk defined on the circle mixes in_linear_ time. This is\nin direct contrast with the quadratic mixing time for the corresponding\nclassical walk. We conclude by indicating how our techniques may be applied to\nmore general graphs.",
"arxiv_id": "quant-ph/0010117",
"authors": [
"Ashwin Nayak",
"Ashvin Vishwanath"
],
"categories": [
"quant-ph"
],
"title": "Quantum Walk on the Line",
"url": "https://arxiv.org/abs/quant-ph/0010117"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "26c1e6db-e69a-40f2-a046-900953d2c3fa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}