Quantum Search on Networks
Stefan Boettcher · Journal of Physics Conference Series · 2019
Abstract 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 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 in terms of the quantum walk dimension d w Q and the spatial (fractal) dimension df or, alternatively, the spectral dimension of the network, ds , even when translational invariance is broken.