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.
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.
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.
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.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
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.
Quantum walks are the quantum analogues of classical random walks or Markov chains. They are universal models of quantum computing, and they underpin a variety of quantum algorithms. We prove that a continuous-time quantum walk effected by a generalized Laplacian, which can arise in spin chains, can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix. This generalized Laplacian consists of the standard Laplacian plus a real-valued multiple of the degree matrix, and we prove that as the magnitude of the multiple of the degree matrix is increased, its corresponding quantum walk can search the complete bipartite graph with multiple marked vertices in time that approaches the optimal. This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.