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.
Comments
6 pages, 3 figures; additional 7 pages of supplemental material
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.
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.
A single excitation in a quantum spin network described by the Heisenberg model can affect a variety of continuous-time quantum walks on unweighted graphs, including those governed by the discrete Laplacian, adjacency matrix, and signless Laplacian. In this paper, we show that the Heisenberg model can affect these three quantum walks on signed weighted graphs, as well as a generalized Laplacian equal to the discrete Laplacian plus a real-valued multiple of the degree matrix, for which the standard Laplacian, adjacency matrix, and signless Laplacian are special cases. We explore the algorithmic consequence of this generalized Laplacian quantum walk when searching a weighted barbell graph consisting of two equal-sized, unweighted cliques connected by a single signed weighted edge or bridge, with the search oracle constituting an external magnetic field in the spin network. We prove that there are two weights for the bridge (which could both be positive, both negative, or one of each, depending on the multiple of the degree matrix) that allow amplitude to cross from one clique to the other---except for the standard and signless Laplacians that respectively only have one negative or positive weight bridge---boosting the success probability from 0.5 to 0.820 or 0.843 for each weight. Moreover, one of the weights leads to a two-stage algorithm that further boosts the success probability to 0.996.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
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.
Quantum walks generated by the adjacency matrix or the Laplacian are known to exhibit low transfer fidelity on general graphs. In this paper, we study continuous-time quantum walks governed by the generalized Laplacian operator L_k = A+kD, where A is the adjacency matrix, D is the degree matrix, and k is a real-valued parameter. Recent work of Duda, McLaughlin, and Wong showed that in the single-excitation Heisenberg (XYZ) spin model, one can realize walks generated by this family of operators on signed weighted graphs. Motivated by earlier studies on vertex-weighted graphs, we demonstrate that for certain graphs, tuning the parameter k can significantly enhance the fidelity of state transfer between endpoints.
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.