dorsal/arxiv
View SchemaAlmost uniform sampling via quantum walks
| Authors | Peter C. Richter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606202 |
| URL | https://arxiv.org/abs/quant-ph/0606202 |
| DOI | 10.1088/1367-2630/9/3/072 |
| Journal | New J. Phys. 9 (2007) 72 |
Abstract
Many classical randomized algorithms (e.g., approximation algorithms for #P-complete problems) utilize the following random walk algorithm for {\em almost uniform sampling} from a state space $S$ of cardinality $N$: run a symmetric ergodic Markov chain $P$ on $S$ for long enough to obtain a random state from within $\epsilon$ total variation distance of the uniform distribution over $S$. The running time of this algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} (\log N + \log \epsilon^{-1}))$, where $\delta$ is the spectral gap of $P$. We present a natural quantum version of this algorithm based on repeated measurements of the {\em quantum walk} $U_t = e^{-iPt}$. We show that it samples almost uniformly from $S$ with logarithmic dependence on $\epsilon^{-1}$ just as the classical walk $P$ does; previously, no such quantum walk algorithm was known. We then outline a framework for analyzing its running time and formulate two plausible conjectures which together would imply that it runs in time $O(\delta^{-1/2} \log N \log \epsilon^{-1})$ when $P$ is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
{
"annotation_id": "fa22436e-1db1-40a5-8884-51842044c2ac",
"date_created": "2026-03-02T18:02:27.169000Z",
"date_modified": "2026-03-02T18:02:27.169000Z",
"file_hash": "62201b3e42ac1e3b09671b633e3b750920c2cada5328e251b4f4ce3a6601b8f9",
"private": false,
"record": {
"abstract": "Many classical randomized algorithms (e.g., approximation algorithms for\n#P-complete problems) utilize the following random walk algorithm for {\\em\nalmost uniform sampling} from a state space $S$ of cardinality $N$: run a\nsymmetric ergodic Markov chain $P$ on $S$ for long enough to obtain a random\nstate from within $\\epsilon$ total variation distance of the uniform\ndistribution over $S$. The running time of this algorithm, the so-called {\\em\nmixing time} of $P$, is $O(\\delta^{-1} (\\log N + \\log \\epsilon^{-1}))$, where\n$\\delta$ is the spectral gap of $P$.\n We present a natural quantum version of this algorithm based on repeated\nmeasurements of the {\\em quantum walk} $U_t = e^{-iPt}$. We show that it\nsamples almost uniformly from $S$ with logarithmic dependence on\n$\\epsilon^{-1}$ just as the classical walk $P$ does; previously, no such\nquantum walk algorithm was known. We then outline a framework for analyzing its\nrunning time and formulate two plausible conjectures which together would imply\nthat it runs in time $O(\\delta^{-1/2} \\log N \\log \\epsilon^{-1})$ when $P$ is\nthe standard transition matrix of a constant-degree graph. We prove each\nconjecture for a subclass of Cayley graphs.",
"arxiv_id": "quant-ph/0606202",
"authors": [
"Peter C. Richter"
],
"categories": [
"quant-ph"
],
"doi": "10.1088/1367-2630/9/3/072",
"journal_ref": "New J. Phys. 9 (2007) 72",
"title": "Almost uniform sampling via quantum walks",
"url": "https://arxiv.org/abs/quant-ph/0606202"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b3f23a88-6798-4ae1-8eb5-eb9004d2103f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}