dorsal/arxiv
View SchemaQuantum walks with infinite hitting times
| Authors | Hari Krovi, Todd A. Brun |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606094 |
| URL | https://arxiv.org/abs/quant-ph/0606094 |
| DOI | 10.1103/PhysRevA.74.042334 |
| Journal | Phys. Rev. A 74, 042334 (2006) |
Abstract
Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well-defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.
{
"annotation_id": "321a83ec-3d42-44a7-acbe-327b3263e740",
"date_created": "2026-03-02T18:02:27.515000Z",
"date_modified": "2026-03-02T18:02:27.515000Z",
"file_hash": "357c2262e76f78dcd07557d6997b1e653913875ad80adb8995c4e5c3e563ff55",
"private": false,
"record": {
"abstract": "Hitting times are the average time it takes a walk to reach a given final\nvertex from a given starting vertex. The hitting time for a classical random\nwalk on a connected graph will always be finite. We show that, by contrast,\nquantum walks can have infinite hitting times for some initial states. We seek\ncriteria to determine if a given walk on a graph will have infinite hitting\ntimes, and find a sufficient condition, which for discrete time quantum walks\nis that the degeneracy of the evolution operator be greater than the degree of\nthe graph. The set of initial states which give an infinite hitting time form a\nsubspace. The phenomenon of infinite hitting times is in general a consequence\nof the symmetry of the graph and its automorphism group. Using the irreducible\nrepresentations of the automorphism group, we derive conditions such that\nquantum walks defined on this graph must have infinite hitting times for some\ninitial states. In the case of the discrete walk, if this condition is\nsatisfied the walk will have infinite hitting times for any choice of a coin\noperator, and we give a class of graphs with infinite hitting times for any\nchoice of coin. Hitting times are not very well-defined for continuous time\nquantum walks, but we show that the idea of infinite hitting-time walks\nnaturally extends to the continuous time case as well.",
"arxiv_id": "quant-ph/0606094",
"authors": [
"Hari Krovi",
"Todd A. Brun"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.74.042334",
"journal_ref": "Phys. Rev. A 74, 042334 (2006)",
"title": "Quantum walks with infinite hitting times",
"url": "https://arxiv.org/abs/quant-ph/0606094"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d1e38b96-4170-45b5-bc62-a154b94f2bc6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}