Source-linked AI summary
Spatial search by quantum walk is optimal for almost all graphs
Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser Omar
TL;DR
The paper addresses how to establish optimal continuous-time quantum-walk search on Erdős–Rényi graphs. It uses degenerate perturbation theory to analyze the search, and reports almost-sure optimality above the stated edge-probability threshold.
Problem
The paper addresses how to establish optimal continuous-time quantum-walk search on Erdős–Rényi graphs.
Source: §IV · p. 7Method
The authors use degenerate perturbation theory to analyze optimal search on Erdős–Rényi graphs.
Source: §IV · p. 7Results
For p ≥ log^1.5(n)/n, search on Erdős–Rényi graphs is almost surely optimal.
Source: §IV · p. 7Takeaways & Limitations
The proof also provides a basis for protocols for quantum state transfer and entanglement generation in these random networks.
Source: §IV · p. 7
Abstract
from arXiv · showhide
The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erd\"os-Renyi random graphs, i.e.\ graphs of $n$ vertices where each edge exists with probability $p$, search by CTQW is \textit{almost surely} optimal as long as $p\geq \log^{3/2}(n)/n$. Consequently, we show that quantum spatial search is in fact optimal for \emph{almost all} graphs, meaning that the fraction of graphs of $n$ vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.
I. SUFFICIENT CONDITION FOR OPTIMAL QUANTUM SEARCH: PROOF OF LEMMA 1
The proof analyzes the search Hamiltonian through its eigenvalues and eigenstates, then tunes its spectrum and evolution time to transfer amplitude from the initial state toward the marked-node state.
I. SUFFICIENT CONDITION FOR OPTIMAL QUANTUM SEARCH: PROOF OF LEMMA 1
- Rescaling H1 preserves its leading eigenvector while shifting the other eigenvalues into a controlled interval.The proof chooses r so the rescaled eigenvalues fall within [−2c/(1+c), 2c/(1−c)].Source: §I · p. 5
- The proof identifies two relevant eigenvalues near 1 and analyzes their associated eigenstates to characterize the search dynamics.It denotes these eigenvalues λ− and λ+ and considers the corresponding eigenvectors |v−⟩ and |v+⟩.Source: §I · p. 5
- Evolution for time π/(2δ) = Θ(1/epsilon) transforms the initial state into a superposition of the two relevant eigenstates.The stated evolution time is derived after the Hamiltonian rescaling.Source: §I · pp. 5–6
II. QUANTUM SEARCH ON RANDOM REGULAR GRAPHS
Random regular graphs have a spectral ratio that satisfies the paper’s sufficient condition for optimal quantum search, including at degree three and above.
II. QUANTUM SEARCH ON RANDOM REGULAR GRAPHS
- For random d-regular graphs with d ≥ 3, the second-largest eigenvalue is O(d^3/4) with high probability, while the largest eigenvalue is d.With γ = 1/d, the eigenvalue ratio is O(d^-1/4) < 1, so Lemma 1 implies optimal search.Source: §II · p. 6
- Quantum search is optimal on random regular graphs of degree three and larger.The proof applies the sufficient spectral-ratio condition to these graphs.Source: §II · p. 6
- The paper contrasts this degree threshold with lattices, where O(√n)-time search first occurs in dimension five.The cited lattice example is a regular graph of degree ten.Source: §II · p. 6
III. CONVERGENCE OF THE EIGENSTATE CORRESPONDING TO THE MAXIMUM EIGENVALUE OF AN ERD¨OS-RENYI RANDOM GRAPH
For Erdős–Rényi graphs above the stated edge-probability threshold, the leading eigenvector of the rescaled adjacency matrix approaches the uniform superposition almost surely.
III. CONVERGENCE OF THE EIGENSTATE CORRESPONDING TO THE MAXIMUM EIGENVALUE OF AN ERD¨OS-RENYI RANDOM GRAPH
- For p ≥ log^1.5(n)/n, the leading eigenvector’s overlap with the uniform superposition is at least 1 − o(1) almost surely.The eigenvector is associated with the largest eigenvalue of the rescaled adjacency matrix.Source: §III · p. 6
- The proof estimates the leading-eigenvector overlap using the remaining eigenvalues and their eigenvectors.It invokes bounds on the spectrum and Euclidean norm to control the overlap.Source: §III · p. 7
IV. PROOF OF OPTIMALITY OF SEARCH ON ERD¨OS-RENYI RANDOM GRAPHS USING DEGENERATE PERTURBATION THEORY
The Erdős–Rényi proof uses the spectral separation of the leading eigenvalue and a two-dimensional perturbation analysis to establish optimal search under the stated density condition.
IV. PROOF OF OPTIMALITY OF SEARCH ON ERD¨OS-RENYI RANDOM GRAPHS USING DEGENERATE PERTURBATION THEORY
- The leading eigenstate approaches the uniform superposition, while the second-largest eigenvalue remains separated from the largest with high probability.The paper uses this spectral separation in its search analysis.Source: §IV · p. 7
- When np → ∞, the semicircle-law radius R shrinks to zero as np grows.The section uses the shrinking radius in its discussion of the search spectrum.Source: §IV · p. 7
- For p ≥ log^1.5(n)/n, the proof states that search on Erdős–Rényi graphs retains optimality almost surely.The argument relates this condition to the shrinking spectral radius as np grows.Source: §IV · p. 7
- Degenerate perturbation theory diagonalizes the search Hamiltonian in the two-dimensional subspace spanned by the relevant states.The search begins in |s⟩ and chooses γp = 1/(np) to make |s⟩ and |w⟩ approximately degenerate for large n.Source: §IV · p. 7
- The marked-node observation probability follows the stated oscillatory expression under evolution by the search Hamiltonian.The probability is given as a function of time t and the frequency Ω.Source: §IV · p. 8