Vertices cannot be hidden from quantum spatial search for almost all random graphs

In this paper we show that all nodes can be found optimally for almost all random Erd\H{o}s-R'enyi $\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)\mathrm{/}n)$, while the seconds requires $p\geq(1+\varepsilon)\log (n)/n$,where$\varepsilon>0$. The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_{\mathrm{\infty }}$ norm. At the same time for $p<(1-\epsilon )\log (n)\mathrm{/}n$, the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.