  Quantum walks provide a natural framework to approach graph problems with
quantum computers, exhibiting speedups over their classical counterparts for
tasks such as the search for marked nodes or the prediction of missing links.
Continuous-time quantum walk algorithms assume that we can simulate the
dynamics of quantum systems where the Hamiltonian is given by the adjacency
matrix of the graph. It is known that such can be simulated efficiently if the
underlying graph is row-sparse and efficiently row-computable. While this is
sufficient for many applications, it limits the applicability for this class of
algorithms to study real world complex networks, which, among other properties,
are characterized by the existence of a few densely connected nodes, called
hubs. In other words, complex networks are typically not row-sparse, even
though the average connectivity over all nodes can be very small. In this work,
we extend the state-of-the-art results on quantum simulation to graphs that
contain a small number of hubs, but that are otherwise sparse. Hopefully, our
results may lead to new applications of quantum computing to network science.
