Exponential speedups for quantum walks in random hierarchical graphs
arXiv:2307.15062 · doi:10.1007/s00220-025-05370-x
Abstract
There are few known exponential speedups for quantum algorithms and these tend to fall into even fewer families. One speedup that has mostly resisted generalization is the use of quantum walks to traverse the welded-tree graph, due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to generalize this to a large class of hierarchical graphs in which the vertices are grouped into "supervertices" which are arranged according to a -dimensional lattice. Supervertices can have different sizes, and edges between supervertices correspond to random connections between their constituent vertices. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians. The speedups range from superpolynomial to exponential, depending on the underlying dimension and the random graph model. We also provide concrete realizations of these hierarchical graphs, and introduce a general method for constructing graphs with efficient quantum traversal times using graph sparsification.
69 pages, 7 figures, v2: minor fixes and improved discussion of Section 6
References in corpus (12)
- Probing many-body dynamics on a 51-atom quantum simulator
- Quantum many-body scars
- Quantum walks: a comprehensive review
- Exponential algorithmic speedup by quantum walk
- User-friendly tail bounds for sums of random matrices
- Nearest neighbor tight binding models with an exact mobility edge in one dimension
- The quantum query complexity of the hidden subgroup problem is polynomial
- Non-backtracking random walks mix faster
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
- Symmetries, graph properties, and quantum speedups
- Dyson's spike for random Schroedinger operators and Novikov-Shubin invariants of groups