Laziness of Quantum Walks on Graphs

• URL: http://arxiv.org/abs/2608.20739v1
• Date: Fri, 21 Aug 2026 04:58:07 GMT
• Title: Laziness of Quantum Walks on Graphs
• Abstract summary: The trace of the average mixing matrix of a quantum walk measures the "laziness" of the walk.<n>We develop tools to study this graph invariant arising from Laplacian quantum walks.
• Score: 0.15190409693764184
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The trace of the average mixing matrix of a quantum walk measures the "laziness" of the walk: the higher the trace, the more likely that the walker returns home in the long run. In this paper, we develop tools to study this graph invariant arising from Laplacian quantum walks. It is known that the complete graph $K_n$ is the laziest connected graph on $n$ vertices. Using our machinery, we show that the star $S_n$ is the second laziest connected graph on $n$ vertices (and hence the laziest tree on $n$ vertices), the complete multipartite graph $K_{n-2,1,1}$ is the third laziest connected graph on $n$ vertices, and the double star $DS(n-3,1)$ is the second laziest tree on $n$ vertices. We also show that on the same number of vertices, more unbalanced double stars are lazier.

Related papers

• A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
  We prove Feige's 2008 conjecture on the hypergraph Moore bound.<n>For every $kge3$ and every $1leellle n$, any $k$-uniform hypergraph on $n$ vertices with more than $C,nk/2/ellk/2-1$ hyperedges contains an even cover of size at most $A,elllog(en/ell)$.
  arXiv  Detail & Related papers  (2026-07-28T17:38:31Z)
• Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing [28.977968088499566]
  We study a sequential decision-making problem on a $n$-node graph $mathcalG$ where each node has an unknown label.<n>We design a Gittins index-based policy that applies to general graphs and is provably optimal when $mathcalG$ is a forest.
  arXiv  Detail & Related papers  (2025-05-27T18:48:42Z)
• Preparing graph states forbidding a vertex-minor [1.864621482724548]
  Measurement based quantum computing is preformed by adding non-Clifford measurements to a prepared stabilizer states.<n>Every stabilizer state is local-Clifford equivalent to a graph state, so we may focus on graph states $leftvert G rightrangle$.<n>We obtain significantly improved bounds when $G$ is contained within certain proper classes of graphs.
  arXiv  Detail & Related papers  (2025-03-31T23:25:35Z)
• 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)
• Almost zero transfer in continuous-time quantum walks on weighted tree graphs [0.0]
  We study continuous-time quantum walks on weighted tree graphs. We map Cayley trees $C_3,2$ and $C_3,3$ into these spider graphs and observe the same dependency.
  arXiv  Detail & Related papers  (2024-04-05T13:41:11Z)
• Complexity of graph-state preparation by Clifford circuits [2.4032529562561176]
  We consider general quantum algorithms acting on at most two qubits for graph-state preparations.<n>We show a connection between the CZ-complexity of graph state $|Grangle$ and the rank-width of the graph $G$.<n>We present quantum algorithms for preparing graph states for three specific graph classes related to intervals: interval graphs, interval containment graphs, and circle graphs.
  arXiv  Detail & Related papers  (2024-02-08T18:08:09Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  We introduce GraphsGPT, featuring a Graph2Seq encoder that transforms Non-Euclidean graphs into learnable Graph Words. A GraphGPT decoder reconstructs the original graph from Graph Words to ensure information equivalence.
  arXiv  Detail & Related papers  (2024-02-04T12:29:40Z)
• 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)
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems [0.0]
  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.
  arXiv  Detail & Related papers  (2022-02-28T14:33:44Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  We leverage existing fast extreme eigenvector computation algorithms for speedy execution. Our embedding is among the fastest in the literature, while producing the best clustering performance for manifold graphs.
  arXiv  Detail & Related papers  (2021-12-15T03:45:39Z)
• 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)

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.