Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2107.05580 · Physical Review A

Equivalent Laplacian and adjacency quantum walks on irregular graphs

Thomas G. Wong, Joshua Lockhart

Published Oct 25, 2021• 6 citations
arXivHTMLPDF

Abstract

The continuous-time quantum walk is a particle evolving by Schr\"odinger's equation in discrete space. Encoding the space as a graph of vertices and edges, the Hamiltonian is proportional to the discrete Laplacian. In some physical systems, however, the Hamiltonian is proportional to the adjacency matrix instead. It is well known that these quantum walks are equivalent when the graph is regular, i.e., when each vertex has the same number of neighbors. If the graph is irregular, however, the quantum walks evolve differently. In this paper, we show that for some irregular graphs, if the particle is initially localized at a certain vertex, the probability distributions of the two quantum walks are identical, even though the amplitudes differ. We analytically prove this for a graph with five vertices and a graph with six vertices. By simulating the walks on all 1 018 689 568 simple, connected, irregular graphs with 11 vertices or less, we found 64 graphs with this notion of equivalence. We also give eight infinite families of graphs supporting these equivalent walks.

DOI
10.1103/physreva.104.042221

Related papers

Experimental investigation of equivalent Laplacian and adjacency quantum walks on irregular graphs

Dengke Qu, Lei Xiao, Kunkun Wang +2 more

The continuous-time quantum walk denotes the evolution of a particle on a given graph governed by Schr\"odinger's equation. For different applications, the corresponding Hamiltonian is proportional to either the Laplacian or the adjacency matrix of the graph. The two quantum walks are equivalent on regular graphs, since each vertex has the same degree. However, for irregular graphs, the evolutions of the two quantum walks are generally different. In this paper, we report an experimental investigation of the two quantum walks on irregular graphs with single photons and interferometric networks. We demonstrate that it is possible to obtain equivalent probability distributions with the two quantum walks on specific irregular graphs, where the particle is initially localized at a vertex or uniformly distributed at multiple vertices. Our results not only deepen the understanding of the equivalence between the two quantum walks, but also extend the application of the continuous-time quantum walk.

Physical Review A•Jun 27, 2022•8 citations

Searching weighted barbell graphs with Laplacian and adjacency quantum walks

Jonas Duda, Thomas G. Wong

A quantum particle evolving by Schr\"odinger's equation in discrete space constitutes a continuous-time quantum walk on a graph of vertices and edges. When a vertex is marked by an oracle, the quantum walk effects a quantum search algorithm. Previous investigations of this quantum search algorithm on graphs with cliques have shown that the edges between the cliques can be weighted to enhance the movement of probability between the cliques to reach the marked vertex. In this paper, we explore the most restrictive form of this by analyzing search on a weighted barbell graph that consists of two cliques of the same size joined by a single weighted edge or bridge. This graph is generally irregular, so quantum walks governed by the graph Laplacian or by the adjacency matrix can differ. We show that the Laplacian quantum walk's behavior does not change, no matter the weight of the bridge, and so the single bridge is too restrictive to affect the walk. Similarly, the adjacency quantum walk's behavior is unchanged for most weights, but when the weight equals the size of a clique, the probability does collect at the clique containing the marked vertex, and utilizing a two-stage algorithm with different weights for each stage, the success probability is boosted from 0.5 to 0.996, independent of the size of the barbell graph.

arXiv:2408.08244•Physical Review A•Oct 15, 2024•2 citations

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

Luca Razzoli, Paolo Bordone, Matteo G. A. Paris

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 = γL —of a walker initially localized at | w ⟩ does not depend on the graph G . We also prove that for any Grover-like CTQW—with Hamiltonian H = γL + ∑ w λ w | w ⟩⟨ w |—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 = γ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.

arXiv:2202.13824•Journal of Physics A Mathematical and Theoretical•May 25, 2022•9 citations

Quantum walks on join graphs

Steve Kirkland, Hermie Monterde

The join X ∨ Y of two graphs X and Y is the graph obtained by joining each vertex of X to each vertex of Y . We explore the behaviour of a continuous quantum walk on a join graph with positive edge weights having the adjacency matrix or Laplacian matrix as its associated Hamiltonian, where the underlying graphs are assumed to be regular when dealing with the adjacency matrix. We characterize strong cospectrality, periodicity and perfect state transfer (PST) in a join graph. We also determine conditions in which strong cospectrality, periodicity and PST are preserved in the join. Under certain conditions, we show that there are graphs with no PST that exhibit PST when joined with another graph. We also show that | | U M ( X ∨ Y , t ) u , v | − | U M ( X , t ) u , v | | ≤ 2 | V ( X ) | for all vertices u and v of X , where U M ( X ∨ Y , t ) and U M ( X , t ) denote the transition matrices of X ∨ Y and X respectively relative to the adjacency or Laplacian matrix. We demonstrate that the bound 2 | V ( X ) | is tight for infinite families of graphs.

arXiv:2312.06906•Discrete Mathematics•Oct 8, 2025•6 citations

Quantum walk search on the complete bipartite graph

Mason L. Rhodes, Thomas G. Wong

The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of $N$ vertices for one of $k$ marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches $1/2$, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is $8/9$. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.

arXiv:1812.06079•Physical Review A•Mar 1, 2019•33 citations

Quantum search with the signless Laplacian

Molly E. McLaughlin, Thomas G. Wong

Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular nonuniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.

arXiv:2501.17128•Physical Review A•Mar 25, 2025•1 citation
The continuous-time quantum walk is a particle evolving by Schr"odinger's equation in discrete space. Encoding the space as a graph of vertices and edges, the Hamiltonian is proportional to the discrete Laplacian. In some physical systems, however, the Hamiltonian is proportional to the adjacency matrix instead. It is well known that these quantum walks are equivalent when the graph is regular, i.e., when each vertex has the same number of neighbors. If the graph is irregular, however, the quantum walks evolve differently. In this paper, we show that for some irregular graphs, if the particle is initially localized at a certain vertex, the probability distributions of the two quantum walks are identical, even though the amplitudes differ. We analytically prove this for a graph with five vertices and a graph with six vertices. By simulating the walks on all 1 018 689 568 simple, connected, irregular graphs with 11 vertices or less, we found 64 graphs with this notion of equivalence. We also give eight infinite families of graphs supporting these equivalent walks.
The continuous-time quantum walk denotes the evolution of a particle on a given graph governed by Schr\"odinger's equation. For different applications, the corresponding Hamiltonian is proportional to either the Laplacian or the adjacency matrix of the graph. The two quantum walks are equivalent on regular graphs, since each vertex has the same degree. However, for irregular graphs, the evolutions of the two quantum walks are generally different. In this paper, we report an experimental investigation of the two quantum walks on irregular graphs with single photons and interferometric networks. We demonstrate that it is possible to obtain equivalent probability distributions with the two quantum walks on specific irregular graphs, where the particle is initially localized at a vertex or uniformly distributed at multiple vertices. Our results not only deepen the understanding of the equivalence between the two quantum walks, but also extend the application of the continuous-time quantum walk.
A quantum particle evolving by Schr\"odinger's equation in discrete space constitutes a continuous-time quantum walk on a graph of vertices and edges. When a vertex is marked by an oracle, the quantum walk effects a quantum search algorithm. Previous investigations of this quantum search algorithm on graphs with cliques have shown that the edges between the cliques can be weighted to enhance the movement of probability between the cliques to reach the marked vertex. In this paper, we explore the most restrictive form of this by analyzing search on a weighted barbell graph that consists of two cliques of the same size joined by a single weighted edge or bridge. This graph is generally irregular, so quantum walks governed by the graph Laplacian or by the adjacency matrix can differ. We show that the Laplacian quantum walk's behavior does not change, no matter the weight of the bridge, and so the single bridge is too restrictive to affect the walk. Similarly, the adjacency quantum walk's behavior is unchanged for most weights, but when the weight equals the size of a clique, the probability does collect at the clique containing the marked vertex, and utilizing a two-stage algorithm with different weights for each stage, the success probability is boosted from 0.5 to 0.996, independent of the size of the barbell graph.
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 = γL —of a walker initially localized at | w ⟩ does not depend on the graph G . We also prove that for any Grover-like CTQW—with Hamiltonian H = γL + ∑ w λ w | w ⟩⟨ w |—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 = γ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.
The join X ∨ Y of two graphs X and Y is the graph obtained by joining each vertex of X to each vertex of Y . We explore the behaviour of a continuous quantum walk on a join graph with positive edge weights having the adjacency matrix or Laplacian matrix as its associated Hamiltonian, where the underlying graphs are assumed to be regular when dealing with the adjacency matrix. We characterize strong cospectrality, periodicity and perfect state transfer (PST) in a join graph. We also determine conditions in which strong cospectrality, periodicity and PST are preserved in the join. Under certain conditions, we show that there are graphs with no PST that exhibit PST when joined with another graph. We also show that | | U M ( X ∨ Y , t ) u , v | − | U M ( X , t ) u , v | | ≤ 2 | V ( X ) | for all vertices u and v of X , where U M ( X ∨ Y , t ) and U M ( X , t ) denote the transition matrices of X ∨ Y and X respectively relative to the adjacency or Laplacian matrix. We demonstrate that the bound 2 | V ( X ) | is tight for infinite families of graphs.
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of NNN vertices for one of kkk marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/21/21/2, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/98/98/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.
Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular nonuniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.