dorsal/arxiv
View SchemaQuantum Walks on the Hypercube
| Authors | Cristopher Moore, Alexander Russell |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0104137 |
| URL | https://arxiv.org/abs/quant-ph/0104137 |
Abstract
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (\pi/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.
{
"annotation_id": "b9a59692-4361-4ebf-bdb0-bd3e9f0427b3",
"date_created": "2026-03-02T18:01:42.593000Z",
"date_modified": "2026-03-02T18:01:42.593000Z",
"file_hash": "ecba47e9c0b1bd6e8dda266b886b168a6463a2754511b91e515ab966322ff952",
"private": false,
"record": {
"abstract": "Recently, it has been shown that one-dimensional quantum walks can mix more\nquickly than classical random walks, suggesting that quantum Monte Carlo\nalgorithms can outperform their classical counterparts. We study two quantum\nwalks on the n-dimensional hypercube, one in discrete time and one in\ncontinuous time. In both cases we show that the quantum walk mixes in (\\pi/4)n\nsteps, faster than the O(n log n) steps required by the classical walk. In the\ncontinuous-time case, the probability distribution is {\\em exactly} uniform at\nthis time. More importantly, these walks expose several subtleties in the\ndefinition of mixing time for quantum walks. Even though the continuous-time\nwalk has an O(n) instantaneous mixing time at which it is precisely uniform, it\nnever approaches the uniform distribution when the stopping time is chosen\nrandomly as in [AharonovAKV2001]. Our analysis treats interference between\nterms of different phase more carefully than is necessary for the walk on the\ncycle; previous general bounds predict an exponential, rather than linear,\nmixing time for the hypercube.",
"arxiv_id": "quant-ph/0104137",
"authors": [
"Cristopher Moore",
"Alexander Russell"
],
"categories": [
"quant-ph"
],
"title": "Quantum Walks on the Hypercube",
"url": "https://arxiv.org/abs/quant-ph/0104137"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "da17bd94-224e-4000-b7b6-204cc9a0122d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}