dorsal/arxiv
View SchemaUniversal Mixing of Quantum Walk on Graphs
| Authors | W. Carlson, A. Ford, E. Harris, J. Rosen, C. Tamon, K. Wrobel |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0608044 |
| URL | https://arxiv.org/abs/quant-ph/0608044 |
| Journal | Quantum Information and Computation 7(8):738-751, 2007 |
Abstract
We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph G is universal mixing if the instantaneous or average probability distribution of the quantum walk on G ranges over all probability distributions on the vertices as the weights are varied over non-negative reals. The graph is uniform mixing if it visits the uniform distribution. Our results include the following: (a) All weighted complete multipartite graphs are instantaneous universal mixing. This is in contrast to the fact that no unweighted complete multipartite graphs are uniform mixing (except for the four-cycle). (b) The weighted claw or star graph is a minimally connected instantaneous universal mixing graph. In fact, as a corollary, the unweighted claw is instantaneous uniform mixing. This adds a new family of uniform mixing graphs to a list that so far contains only the hypercubes. (c) Any weighted graph is average almost-uniform mixing unless its spectral type is sublinear in the size of the graph. This provides a nearly tight characterization for average uniform mixing on circulant graphs. (d) No weighted graphs are average universal mixing. This shows that weights do not help to achieve average universal mixing, unlike the instantaneous case. Our proofs exploit the spectra of the underlying weighted graphs and path collapsing arguments.
{
"annotation_id": "4accf50b-0112-4915-85b0-fefe1de2c5c5",
"date_created": "2026-03-02T18:02:30.926000Z",
"date_modified": "2026-03-02T18:02:30.926000Z",
"file_hash": "a88223cffe1bd34d248592c0c10cdfe0f98dc0ba0d1ee326ae45cbc2b6c3c83c",
"private": false,
"record": {
"abstract": "We study the set of probability distributions visited by a continuous-time\nquantum walk on graphs. An edge-weighted graph G is universal mixing if the\ninstantaneous or average probability distribution of the quantum walk on G\nranges over all probability distributions on the vertices as the weights are\nvaried over non-negative reals. The graph is uniform mixing if it visits the\nuniform distribution. Our results include the following:\n (a) All weighted complete multipartite graphs are instantaneous universal\nmixing. This is in contrast to the fact that no unweighted complete\nmultipartite graphs are uniform mixing (except for the four-cycle).\n (b) The weighted claw or star graph is a minimally connected instantaneous\nuniversal mixing graph. In fact, as a corollary, the unweighted claw is\ninstantaneous uniform mixing. This adds a new family of uniform mixing graphs\nto a list that so far contains only the hypercubes.\n (c) Any weighted graph is average almost-uniform mixing unless its spectral\ntype is sublinear in the size of the graph. This provides a nearly tight\ncharacterization for average uniform mixing on circulant graphs.\n (d) No weighted graphs are average universal mixing. This shows that weights\ndo not help to achieve average universal mixing, unlike the instantaneous case.\n Our proofs exploit the spectra of the underlying weighted graphs and path\ncollapsing arguments.",
"arxiv_id": "quant-ph/0608044",
"authors": [
"W. Carlson",
"A. Ford",
"E. Harris",
"J. Rosen",
"C. Tamon",
"K. Wrobel"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information and Computation 7(8):738-751, 2007",
"title": "Universal Mixing of Quantum Walk on Graphs",
"url": "https://arxiv.org/abs/quant-ph/0608044"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b0001bae-96e9-4d4e-9bbf-23a309d79c2c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}