  We establish a lower bound concerning the computational complexity of
Grover's algorithms on fractal networks. This bound provides general
predictions for the quantum advantage gained for searching unstructured lists.
It yields a fundamental criterion, derived from quantum transport properties,
for the improvement a quantum search algorithm achieves over the corresponding
classical search in a network based solely on its spectral dimension, $d_{s}$.
Our analysis employs recent advances in the interpretation of the venerable
real-space renormalization group (RG) as applied to quantum walks. It clarifies
the competition between Grover's abstract algorithm, i.e., a rotation in
Hilbert space, and quantum transport in an actual geometry. The latter is
characterized in terms of the quantum walk dimension $d_{w}^{Q}$ and the
spatial (fractal) dimension $d_{f}$ that is summarized simply by the spectral
dimension of the network. The analysis simultaneously determines the optimal
time for a quantum measurement and the probability for successfully
pin-pointing a marked element in the network. The RG further encompasses an
optimization scheme devised by Tulsi that allows to tune this probability to
certainty, leaving quantum transport as the only limiting process. It considers
entire families of problems to be studied, thereby establishing large
universality classes for quantum search, which we verify with extensive
simulations. The methods we develop could point the way towards systematic
studies of universality classes in computational complexity to enable
modification and control of search behavior.
