Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems

• URL: http://arxiv.org/abs/2202.13824v2
• Date: Thu, 9 Jun 2022 09:37:49 GMT
• Title: Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems
• Authors: Luca Razzoli, Paolo Bordone, Matteo G. A. Paris
• Abstract summary: We prove that the continuous-time quantum walk (CTQW) -- with Hamiltonian $H=gamma L$ -- does not depend on the graph $G$. We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fully connected vertex $w$ in a simple graph $G$ of order $N$ is a vertex connected to all the other $N-1$ vertices. Upon denoting by $L$ the Laplacian matrix of the graph, we prove that the continuous-time quantum walk (CTQW) -- with Hamiltonian $H=\gamma L$ -- of a walker initially localized at $\vert w \rangle$ does not depend on the graph $G$. We also prove that for any Grover-like CTQW -- with Hamiltonian $H=\gamma L +\sum_w \lambda_w \vert w \rangle\langle w \vert$ -- the probability amplitude at the fully connected marked vertices $w$ does not depend on $G$. The result does not hold for CTQW with Hamiltonian $H=\gamma A$ (adjacency matrix). We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices, proving that CTQWs on any graph $G$ inherit the properties already known for the complete graph of the same order, including the optimality of the spatial search. Our results provide a unified framework for several partial results already reported in literature for fully connected vertices, such as the equivalence of CTQW and of spatial search for the central vertex of the star and wheel graph, and any vertex of the complete graph.

Related papers

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Quantum walks on join graphs [0.0]
  We explore the behaviour of a continuous quantum walk on a weighted join graph having the adjacency matrix or Laplacian matrix as its associated Hamiltonian. We characterize strong cospectrality, periodicity and perfect state transfer (PST) in a join graph. We demonstrate that the bound $frac2|V(X)|$ is tight for infinite families of graphs.
  arXiv  Detail & Related papers  (2023-12-12T00:33:30Z)
• Quantum walks on blow-up graphs [0.0]
  A blow-up of $n$ copies of a graph $G$ is the graph $oversetnuplusG$. We investigate the existence of quantum state transfer on a blow-up graph $oversetnuplusG$.
  arXiv  Detail & Related papers  (2023-08-26T14:07:25Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-10-11T05:07:50Z)
• Laplacian State Transfer on Graphs with an Edge Perturbation Between Twin Vertices [0.0]
  We consider quantum state transfer relative to the Laplacian matrix of a graph. We investigate the existence of quantum state transfer between a pair of twin vertices in a graph when the edge between the vertices is perturbed.
  arXiv  Detail & Related papers  (2021-09-11T15:48:18Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
  Lackadaisical quantum walk (LQW) is a quantum analog of a classical lazy walk. We numerically study search by LQW for different types of 2D grids -- triangular, rectangular and honeycomb.
  arXiv  Detail & Related papers  (2021-04-20T13:33:16Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$. Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
  arXiv  Detail & Related papers  (2021-04-06T15:34:14Z)

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.