Open AccessQuantum Search on Networks
Author(s) -
Stefan Boettcher
Publication year - 2019
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1252/1/012008
Subject(s) - hilbert space , dimension (graph theory) , algorithm , quantum , rotation (mathematics) , fractal dimension , computer science , fractal , mathematics , physics , artificial intelligence , combinatorics , quantum mechanics , mathematical analysis
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 d f or, alternatively, the spectral dimension of the network, d s , even when translational invariance is broken.