  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.
