Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks via Renormalization

I will describe how we determined a lower bound on the computational complexity of Grover's quantum search algorithms in low-dimensional networks using the renormalization group (RG). It highlights the competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. It can be characterized entirely in terms the spectral dimension of the network, even when translational invariance is broken. 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. It considers entire families of problems to be studied, thereby establishing large universality classes for quantum search, which we verify with extensive simulations.