Vertices cannot be hidden from quantum spatial search for almost all random graphs
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ő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 …