In this paper, we show that all nodes can be found optimally for almost all random Erdős–Rényi $$\mathcal G(n,p)$$ 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)$$ p=ω(log8(n)/n) , while the second requires $$p\ge (1+\varepsilon )\log (n)/n$$ p≥(1+ε)log(n)/n , where $$\varepsilon >0$$ ε>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$$ 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.