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

DOI10.1007/s11128-018-1844-7zbMath1395.81083arXiv1709.06829OpenAlexW3102370491WikidataQ62582413 ScholiaQ62582413MaRDI QIDQ1654045

Adam Glos, Aleksandra Krawiec, Zbigniew Puchała, Ryszard Kukulski

Publication date: 7 August 2018

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.06829

zbMATH Keywords

random graphscontinuous-time quantum walkquantum spatial searchErdős-Rényi graphs

Mathematics Subject Classification ID

Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Quantum computation (81P68)

Related Items (3)

Impact of the malicious input data modification on the efficiency of quantum spatial search ⋮ Limiting properties of stochastic quantum walks on directed graphs ⋮ Impact of global and local interaction on quantum spatial search on chimera graph

Cites Work

• Unnamed Item
• Unnamed Item
• Spatial search by continuous-time quantum walk with multiple marked vertices
• Robust quantum spatial search
• Laplacian versus adjacency matrix in quantum walk search
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• On the spectra of general random graphs
• Entrywise bounds for eigenvectors of random graphs
• Spectral measure of large random Hankel, Markov and Toeplitz matrices
• Noise resistance of adiabatic quantum computation using random matrix theory
• Exponential algorithmic speedup by a quantum walk
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Spectral techniques applied to sparse random graphs

This page was built for publication: Vertices cannot be hidden from quantum spatial search for almost all random graphs