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