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

Abstract

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 seconds requires $p\ge (1+\epsilon )\log (n)/n$, where $\epsilon >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-\epsilon )\log (n)/n$, the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.

18 pages, 3 figure

References in corpus (4)

• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Noise resistance of adiabatic quantum computation using random matrix theory
• Quantum transport on small-world networks: A continuous-time quantum walk approach

Cited by in corpus (10)

• On the optimality of spatial search by continuous-time quantum walk
• Quantum spatial search on graphs subject to dynamical noise
• How fast do quantum walks mix?
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
• Impact of global and local interaction on quantum spatial search on chimera graph
• Asymptotic entropy of the Gibbs state of complex networks
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Spectral similarity for Barabási-Albert and Chung-Lu models
• Universal scaling hypothesis of quantum spatial search in complex networks