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

DOI10.1007/S11128-018-1844-7MaRDI QIDQ1654045zbMATH OpenOpenAlexWikidataFDO

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

Publication date 7 August 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

continuous-time quantum walkErdős-Rényi graphsquantum spatial searchrandom graphs

Mathematics Subject Classification ID

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

Abstract: In this paper we show that all nodes can be found optimally for almost all random ErdH{o}s-R'enyi $mathcalG(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(lo{g}^8(n)/n)$, while the seconds requires $pgeq(1+varepsilon)log(n)/n$, where $varepsilon>0$. The proof was made by analyzing the convergence of eigenvectors corresponding to outlying eigenvalues in the $|cdot{|}_{i}nfty$ norm. At the same time for $p<(1-varepsilon)log(n)/n$, the property does not hold for any matrix, due to the connectivity issues. Hence, our derivation concerning Laplacian matrix is tight.

Recommendations

• Quantum and randomized lower bounds for local search on vertex-transitive graphs
• Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
• Search on vertex-transitive graphs by lackadaisical quantum walk
• Adjacent vertices can be hard to find by quantum walks
• Adjacent vertices can be hard to find by quantum walks
• Visibility of quantum graph spectrum from the vertices
• On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
• Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation
• Random quantum graphs
• Automata, Languages and Programming

Cites work

• Entrywise bounds for eigenvectors of random graphs
• Exponential algorithmic speedup by a quantum walk
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• Laplacian versus adjacency matrix in quantum walk search
• Noise resistance of adiabatic quantum computation using random matrix theory
• On the spectra of general random graphs
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Random graphs.
• Robust quantum spatial search
• Spatial search by continuous-time quantum walk with multiple marked vertices
• Spectral measure of large random Hankel, Markov and Toeplitz matrices
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Spectral techniques applied to sparse random graphs

Cited in

(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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1654045)