dorsal/arxiv
View SchemaA random walk approach to quantum algorithms
| Authors | Viv Kendon |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0609035 |
| URL | https://arxiv.org/abs/quant-ph/0609035 |
| DOI | 10.1098/rsta.2006.1901 |
| Journal | Phil. Trans. R. Soc. A (2006) 364, 3407-3422 |
Abstract
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial: pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e., when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk, due to interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point on average than a classical walker, and this forms the basis of a quantum speed up that can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, with even a small quantum computer available, development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
{
"annotation_id": "d27b4d9b-d598-49fb-9116-e65552ff229b",
"date_created": "2026-03-02T18:02:31.194000Z",
"date_modified": "2026-03-02T18:02:31.194000Z",
"file_hash": "eb0d8088772442302bae65db23a9555ca8439003f28564108e453def4224a503",
"private": false,
"record": {
"abstract": "The development of quantum algorithms based on quantum versions of random\nwalks is placed in the context of the emerging field of quantum computing.\nConstructing a suitable quantum version of a random walk is not trivial: pure\nquantum dynamics is deterministic, so randomness only enters during the\nmeasurement phase, i.e., when converting the quantum information into classical\ninformation. The outcome of a quantum random walk is very different from the\ncorresponding classical random walk, due to interference between the different\npossible paths. The upshot is that quantum walkers find themselves further from\ntheir starting point on average than a classical walker, and this forms the\nbasis of a quantum speed up that can be exploited to solve problems faster.\nSurprisingly, the effect of making the walk slightly less than perfectly\nquantum can optimize the properties of the quantum walk for algorithmic\napplications. Looking to the future, with even a small quantum computer\navailable, development of quantum walk algorithms might proceed more rapidly\nthan it has, especially for solving real problems.",
"arxiv_id": "quant-ph/0609035",
"authors": [
"Viv Kendon"
],
"categories": [
"quant-ph"
],
"doi": "10.1098/rsta.2006.1901",
"journal_ref": "Phil. Trans. R. Soc. A (2006) 364, 3407-3422",
"title": "A random walk approach to quantum algorithms",
"url": "https://arxiv.org/abs/quant-ph/0609035"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d76c142d-becf-405b-82a3-fa51b428ad7c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}