dorsal/arxiv
View SchemaQuantum Algorithms and Covering Spaces
| Authors | Tobias J. Osborne, Simone Severini |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0403127 |
| URL | https://arxiv.org/abs/quant-ph/0403127 |
Abstract
In this paper we isolate the combinatorial property responsible (at least in part) for the computational speedups recently observed in some quantum walk algorithms. We find that continuous-time quantum walks can exploit the covering space property of certain graphs. We demonstrate that a quantum walk on a graph Y which covers a smaller graph X can be equivalent to a quantum walk on the smaller graph X. This equivalence occurs only when the walk begins on certain initial states, fibre-constant states, which respect the graph covering space structure. We illustrate these observations with walks on Cayley graphs; we show that walks on fibre-constant initial states for Cayley graphs are equivalent to walks on the induced Schreier graph. We also consider the problem of constructing efficient gate sequences simulating the time evolution of a continuous-time quantum walk. For the case of the walk on the m-torus graph T^m on 2^n vertices we construct a gate sequence which uses O(\poly(n)) gates which is independent of the time t the walk is simulated for (and so the sequence can simulate the walk for exponential times). We argue that there exists a wide class of nontrivial operators based on quantum walks on graphs which can be measured efficiently. We introduce a new general class of computational problems, HiddenCover, which includes a variant of the general hidden subgroup problem as a subclass. We argue that quantum computers ought to be able to utilise covering space structures to efficiently solve HiddenCover problems.
{
"annotation_id": "de0a89bb-89ac-4f87-990a-572d640fecb9",
"date_created": "2026-03-02T18:02:05.876000Z",
"date_modified": "2026-03-02T18:02:05.876000Z",
"file_hash": "7e4da197a5e94351f7b4b089ef562b33602134c687066255901bf587f3d70a41",
"private": false,
"record": {
"abstract": "In this paper we isolate the combinatorial property responsible (at least in\npart) for the computational speedups recently observed in some quantum walk\nalgorithms. We find that continuous-time quantum walks can exploit the covering\nspace property of certain graphs. We demonstrate that a quantum walk on a graph\nY which covers a smaller graph X can be equivalent to a quantum walk on the\nsmaller graph X. This equivalence occurs only when the walk begins on certain\ninitial states, fibre-constant states, which respect the graph covering space\nstructure. We illustrate these observations with walks on Cayley graphs; we\nshow that walks on fibre-constant initial states for Cayley graphs are\nequivalent to walks on the induced Schreier graph. We also consider the problem\nof constructing efficient gate sequences simulating the time evolution of a\ncontinuous-time quantum walk. For the case of the walk on the m-torus graph T^m\non 2^n vertices we construct a gate sequence which uses O(\\poly(n)) gates which\nis independent of the time t the walk is simulated for (and so the sequence can\nsimulate the walk for exponential times). We argue that there exists a wide\nclass of nontrivial operators based on quantum walks on graphs which can be\nmeasured efficiently. We introduce a new general class of computational\nproblems, HiddenCover, which includes a variant of the general hidden subgroup\nproblem as a subclass. We argue that quantum computers ought to be able to\nutilise covering space structures to efficiently solve HiddenCover problems.",
"arxiv_id": "quant-ph/0403127",
"authors": [
"Tobias J. Osborne",
"Simone Severini"
],
"categories": [
"quant-ph"
],
"title": "Quantum Algorithms and Covering Spaces",
"url": "https://arxiv.org/abs/quant-ph/0403127"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5538c571-91f1-4c70-8861-e3e355ba67c8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}