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.
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.
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.
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.
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.
In this work, we consider the spatial search for a general marked state on graphs by continuous time quantum walks. As a simplest case, we compute the amplitude expression of the search for the multi-vertex uniform superposition state on hypercube, and find that the spatial search algorithm is optimal for the two-vertex uniform state. However, on general graphs, a common formula can't be obtained for searching a general non-uniform superposition state. Fortunately, a Laplacian spectrum condition which determines whether the associated graph could be appropriate for performing the optimal spatial search is presented. The condition implies that if the proportion of the maximum and the non-zero minimum Laplacian eigenvalues is less or equal to 1+sqrt(1/2), then the spatial search is optimal for any general state. At last, we apply this condition to three kind graphs, the induced complete graph, the strongly regular graph and the regular complete multi-partite graphs. By the condition, one can conclude that these graphs will become suitable for optimal search with properly setting their graph parameters.
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
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.