Exponential Speedups for Quantum Walks in Random Hierarchical Graphs
Authors:
Open Access
- 1 August 2025
- journal article
- research article
- Published by Springer Nature in Communications in Mathematical Physics
- Vol. 406 (9) , 1-72
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 d-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.Keywords
All Related Versions
Funding Information
- National Science Foundation Graduate Research Fellowship Program (1745302)
- NTT Research (AGMT DTD 9/24/20)
- Division of Physics (1818914)
- Samsung Advanced Institute of Technology (Global Research Partnership, 1818914)
- Division of Computing and Communication Foundations (1729369)
- Office of Multidisciplinary Activities (2016245)
- Office of Science (DE-SC0012704)
- Simons Foundation (MP-SIP-00001553, AWH)
This publication has 42 references indexed in Scilit:
- Probability-22019
- Dyson’s Spike for Random Schroedinger Operators and Novikov–Shubin Invariants of GroupsCommunications in Mathematical Physics, 2017
- Quantum walks: a comprehensive reviewQuantum Information Processing, 2012
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- Discrete Quantum Walks Hit Exponentially FasterProbability Theory and Related Fields, 2005
- The quantum query complexity of the hidden subgroup problem is polynomialInformation Processing Letters, 2004
- Quantum Walks on the Hypercube2002
- Quantum Cryptanalysis of Hidden Linear Functions1995
- Bounds on the density of states in disordered systemsZeitschrift für Physik B Condensed Matter, 1981
- The statistics of dimers on a latticePhysica, 1961