Efficiency Bounds on Quantum Search Algorithms in low-dimensional Geometries*

We find a lower bound on the computational complexity of Grover's quantum search algorithms in low-dimensional networks using the renormalization group (RG). It reveals a competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. It can be characterized in terms of the quantum walk dimension d_w^Q and the spatial (fractal) dimension d_f or, alternatively, the spectral dimension of the network, d_s, even when translational invariance is broken.The analysis simultaneously determines the optimal time for a quantum measurement and the probability for successfully pin-pointing the sought-after element in the network. The RG further encompasses an optimization scheme devised by Tulsi that allows to tune this probability to certainty. Our RG considers entire families of problems to be studied, thereby establishing large universality classes for quantum search and how these can be broken, which we verify with extensive simulations. The methods we propose open the door to a systematic study of universality classes in computational complexity and how a class may be broken to modify and control search behavior. (https://arxiv.org/abs/1708.05339)