dorsal/arxiv
View SchemaQuantum speedup of classical mixing processes
| Authors | Peter C. Richter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0609204 |
| URL | https://arxiv.org/abs/quant-ph/0609204 |
| DOI | 10.1103/PhysRevA.76.042306 |
| Journal | Phys. Rev. A 76, 042306 (2007) |
Abstract
Most approximation algorithms for #P-complete problems (e.g., evaluating the permanent of a matrix or the volume of a polytope) work by reduction to the problem of approximate sampling from a distribution $\pi$ over a large set $\S$. This problem is solved using the {\em Markov chain Monte Carlo} method: a sparse, reversible Markov chain $P$ on $\S$ with stationary distribution $\pi$ is run to near equilibrium. The running time of this random walk algorithm, the so-called {\em mixing time} of $P$, is $O(\delta^{-1} \log 1/\pi_*)$ as shown by Aldous, where $\delta$ is the spectral gap of $P$ and $\pi_*$ is the minimum value of $\pi$. A natural question is whether a speedup of this classical method to $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$, the diameter of the graph underlying $P$, is possible using {\em quantum walks}. We provide evidence for this possibility using quantum walks that {\em decohere} under repeated randomized measurements. We show: (a) decoherent quantum walks always mix, just like their classical counterparts, (b) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (c) the mixing time of the decoherent quantum walk on a periodic lattice $\Z_n^d$ is $O(n d \log d)$, which is indeed $O(\sqrt{\delta^{-1}} \log 1/\pi_*)$ and is asymptotically no worse than the diameter of $\Z_n^d$ (the obvious lower bound) up to at most a logarithmic factor.
{
"annotation_id": "d0235e9b-3397-4033-b7bc-c119216fa9a4",
"date_created": "2026-03-02T18:02:31.253000Z",
"date_modified": "2026-03-02T18:02:31.253000Z",
"file_hash": "56cec225b059b2764e6874f28230627b18b2ffbe8d4ff47f8db82b7c1227fcbb",
"private": false,
"record": {
"abstract": "Most approximation algorithms for #P-complete problems (e.g., evaluating the\npermanent of a matrix or the volume of a polytope) work by reduction to the\nproblem of approximate sampling from a distribution $\\pi$ over a large set\n$\\S$. This problem is solved using the {\\em Markov chain Monte Carlo} method: a\nsparse, reversible Markov chain $P$ on $\\S$ with stationary distribution $\\pi$\nis run to near equilibrium. The running time of this random walk algorithm, the\nso-called {\\em mixing time} of $P$, is $O(\\delta^{-1} \\log 1/\\pi_*)$ as shown\nby Aldous, where $\\delta$ is the spectral gap of $P$ and $\\pi_*$ is the minimum\nvalue of $\\pi$. A natural question is whether a speedup of this classical\nmethod to $O(\\sqrt{\\delta^{-1}} \\log 1/\\pi_*)$, the diameter of the graph\nunderlying $P$, is possible using {\\em quantum walks}.\n We provide evidence for this possibility using quantum walks that {\\em\ndecohere} under repeated randomized measurements. We show: (a) decoherent\nquantum walks always mix, just like their classical counterparts, (b) the\nmixing time is a robust quantity, essentially invariant under any smooth form\nof decoherence, and (c) the mixing time of the decoherent quantum walk on a\nperiodic lattice $\\Z_n^d$ is $O(n d \\log d)$, which is indeed\n$O(\\sqrt{\\delta^{-1}} \\log 1/\\pi_*)$ and is asymptotically no worse than the\ndiameter of $\\Z_n^d$ (the obvious lower bound) up to at most a logarithmic\nfactor.",
"arxiv_id": "quant-ph/0609204",
"authors": [
"Peter C. Richter"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.76.042306",
"journal_ref": "Phys. Rev. A 76, 042306 (2007)",
"title": "Quantum speedup of classical mixing processes",
"url": "https://arxiv.org/abs/quant-ph/0609204"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "18d66b34-768e-4a40-8fc6-64bfe1268afa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}