Of Shadows and Gaps in Spatial Search
- URL: http://arxiv.org/abs/2204.04355v2
- Date: Tue, 30 Aug 2022 23:05:28 GMT
- Title: Of Shadows and Gaps in Spatial Search
- Authors: Ada Chan, Chris Godsil, Christino Tamon, Weichen Xie
- Abstract summary: We show that some families of distance-regular graphs, such as Hamming and Grassmann graphs, have optimal spatial search.
We also show a matching lower bound on time for spatial search with constant fidelity, which extends a bound due to Farhi and Gutmann for perfect fidelity.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spatial search occurs in a connected graph if a continuous-time quantum walk
on the adjacency matrix of the graph, suitably scaled, plus a rank-one
perturbation induced by any vertex will unitarily map the principal eigenvector
of the graph to the characteristic vector of the vertex. This phenomenon is a
natural continuous-time analogue of Grover search. The spatial search is said
to be optimal if it occurs with constant fidelity and in time inversely
proportional to the shadow of the target vertex on the principal eigenvector.
Extending a result of Chakraborty et al. (Physical Review A, 102:032214, 2020),
we prove a simpler characterization of optimal spatial search. Based on this
characterization, we observe that some families of distance-regular graphs,
such as Hamming and Grassmann graphs, have optimal spatial search. We also show
a matching lower bound on time for spatial search with constant fidelity, which
extends a bound due to Farhi and Gutmann for perfect fidelity. Our elementary
proofs employ standard tools, such as Weyl inequalities and Cauchy determinant
formula.
Related papers
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
This article presents a novel and succinct algorithmic framework via alternating quantum walks.
It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs.
The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
arXiv Detail & Related papers (2024-07-01T06:09:19Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.
Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix.
Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
arXiv Detail & Related papers (2024-02-29T09:26:46Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure.
We introduce a new class of manifold, named soft manifold, that can solve this situation.
Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
arXiv Detail & Related papers (2023-11-29T12:48:33Z) - No Infinite Tail Beats Optimal Spatial Search [0.0]
We show that spatial search remains optimal in a complete graph even in the presence of an infinitely long path (or tail)
We show that the search algorithm is oblivious in that it does not need to know whether the tail is present or not, and if so, where it is attached to.
arXiv Detail & Related papers (2023-01-18T01:25:12Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs.
The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
arXiv Detail & Related papers (2022-03-27T20:22:17Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm.
We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
arXiv Detail & Related papers (2021-12-29T18:46:52Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree.
In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z) - Deterministic spatial search using alternating quantum walks [0.0]
We prove that for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established.
This improves on the original spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability.
It is expected that this new framework can be readily extended to deterministic spatial search on other families of graph structures.
arXiv Detail & Related papers (2021-04-08T14:32:48Z) - Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
We consider the block model where connection between vertices is perturbed by some latent (and unobserved) random geometric graph.
The objective is to prove that spectral methods are robust to this type of noise, even if they are agnostic to the presence (or not) of the random graph.
arXiv Detail & Related papers (2020-11-09T10:15:40Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$.
We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
arXiv Detail & Related papers (2020-05-13T14:53:36Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.