Vertices cannot be hidden from quantum spatial search for almost all random graphs
Adam Glos, Aleksandra Krawiec, Ryszard Kukulski, Zbigniew Puchała · Quantum Information Processing · 2018
In this paper, we show that all nodes can be found optimally for almost all random Erdős–Rényi $$\mathcal G(n,p)$$ graphs using continuous-time quantum spatial search procedure. This works for both adjacency and Laplacian matrices, though under different conditions. The first one requires $$p=\omega (\log ^8(n)/n)$$ , while the second requires $$p\ge (1+\varepsilon )\log (n)/n$$ , where $$\varepsilon >0$$ . The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the $$\Vert \cdot \Vert _\infty $$ norm. At the same time for $$p<(1-\varepsilon )\log (n)/n$$ , the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.