We study the discrete quantum walk on a regular graph X that assigns negative identity coins to marked vertices S and Grover coins to the unmarked ones. We find combinatorial bases for the eigenspaces of the transition matrix, and derive a formula for the average vertex mixing matrix M ˆ . We then find bounds for entries in M ˆ , and study when these bounds are tight. In particular, the average probabilities between marked vertices are lower bounded by a matrix determined by the induced subgraph X [ S ] , the vertex-deleted subgraph ﹨ X ﹨ S , and the edge deleted subgraph X − E ( S ) . We show this bound is achieved if and only if the marked vertices have walk-equitable neighborhoods in the vertex-deleted subgraph. Finally, for quantum walks attaining this bound, we determine when M ˆ [ S , S ] is symmetric, positive semidefinite or uniform.
We study the discrete quantum walk on a regular graph X that assigns negative identity coins to marked vertices S and Grover coins to the unmarked ones. We find combinatorial bases for the eigenspaces of the transition matrix, and derive a formula for the average vertex mixing matrix M ˆ . We then find bounds for entries in M ˆ , and study when these bounds are tight. In particular, the average probabilities between marked vertices are lower bounded by a matrix determined by the induced subgraph X [ S ] , the vertex-deleted subgraph ﹨ X ﹨ S , and the edge deleted subgraph X − E ( S ) . We show this bound is achieved if and only if the marked vertices have walk-equitable neighborhoods in the vertex-deleted subgraph. Finally, for quantum walks attaining this bound, we determine when M ˆ [ S , S ] is symmetric, positive semidefinite or uniform.
Search algorithms based on discrete-time quantum walk (QW) can be considered as alterations of the standard QW: Use a different coin operator that distinguishes target and nontarget vertices, or, mark the target vertices first followed by the standard QW. Two most frequently used marking coins are [Formula: see text] and [Formula: see text] the negative identity operator and the negative Grover diffusion operator. We show that search algorithms corresponding to these four combinations can be reduced to two, denoted as [Formula: see text] and [Formula: see text], and they are equivalent when searching for nonadjacent multiple targets. For adjacent target vertices, numerical simulations show that the performance of the algorithm [Formula: see text] highly depends on the density of the underlying graph, and it outperforms [Formula: see text] when the density is large enough. At last, a generalized stationary state of both search algorithms on the graphs with even-numbered degree is provided.
Let X be a weighted graph and M be its adjacency, Laplacian or signless Laplacian matrix. In a continuous quantum walk on X, local ε-uniform mixing occurs at vertex u if the uth column of the matrix U(t)=eitM can be made arbitrarily close to a vector whose all entries have equal magnitude. Using the spectral and combinatorial properties of X, we derive necessary conditions for local ε-uniform mixing to occur in X. This includes an inequality involving all entries of each eigenvector of M, as well as an upper bound on the degree of vertex u when M is the Laplacian or signless Laplacian matrix. We use these necessary conditions to rule out local ε-uniform mixing in numerous classes of graphs, most of which are non-regular. We also show that almost all planar graphs (resp., trees) contain a vertex that does not admit local ε-uniform mixing for any assignment of edge weights. Furthermore, we prove if X has n vertices and admits local ε-uniform mixing at a vertex contained in a subgraph with a twin, then the number of vertices of this twin subgraph must be at least n. In particular, we establish that a graph on n≥5 vertices does not admit local ε-uniform mixing at a vertex with a twin.
The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given l self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of N vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Shenvi, Kempe, and Whaley (2003) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when l scales less than N , while the second requires that l scale less than N 2 . Finally, continuous-time quantum walks differ from both of these discrete-time examples—the self-loops make no difference at all. These behaviors generalize to multiple marked vertices.
Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.