Vertices cannot be hidden from quantum spatial search for almost all random graphs
arXiv:1709.06829 · doi:10.1007/s11128-018-1844-7
Abstract
In this paper we show that all nodes can be found optimally for almost all random Erdős-Rényi graphs using continuous-time quantum spatial search procedure. This works for both adjacency and Laplacian matrices, though under different conditions. The first one requires , while the seconds requires , where . The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the norm. At the same time for , the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.
arXiv comment18 pages, 3 figure
References in corpus (14)
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
- Spectral statistics of Erdős-Rényi graphs I: Local semicircle law
- Spatial search by quantum walk is optimal for almost all graphs
- Google in a Quantum Network
- Quantum Navigation and Ranking in Complex Networks
- Noise resistance of adiabatic quantum computation using random matrix theory
- Quantum transport on small-world networks: A continuous-time quantum walk approach
- Quantum Google in a Complex Network
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Optimal quantum spatial search on random temporal networks
- Continuous-Time Quantum Search on Balanced Trees
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
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