Search on vertex-transitive graphs by lackadaisical quantum walk
- PDF / 639,564 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 206 Views
Search on vertex-transitive graphs by lackadaisical quantum walk Mason L. Rhodes1 · Thomas G. Wong1 Received: 15 April 2020 / Accepted: 20 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph with a weighted self-loop at each vertex. It uses a generalized Grover coin and the flipflop shift, which makes it equivalent to Szegedy’s quantum Markov chain. It has been shown that a lackadaisical quantum walk can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. In this paper, we observe that these are all vertex-transitive graphs, and when there is a unique marked vertex, the optimal weight of the self-loop equals the degree of the loopless graph divided by the total number of vertices. We propose that this holds for all vertextransitive graphs with a unique marked vertex. We present a number of numerical simulations supporting this hypothesis, including search on periodic cubic lattices of arbitrary dimension, strongly regular graphs, Johnson graphs, and the hypercube. Keywords Quantum walk · Lackadaisical quantum walk · Quantum search · Spatial search · Vertex transitive graph
1 Introduction The coined quantum walk is a quantum analogue of the discrete-time random walk. It was first discovered by Meyer [1] in the context of quantum cellular automata, and he proved [2] that an internal degree of freedom was necessary to make the evolution nontrivial. He also proved that the coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, with the internal degree of freedom playing the role of spin. Later, Aharonov et al. [3] and Ambainis et al. [4] reframed this in the context of quantum walks, with the internal degree of freedom playing the role
B
Thomas G. Wong [email protected] Mason L. Rhodes [email protected]
1
Department of Physics, Creighton University, 2500 California Plaza, Omaha, NE 68178, USA 0123456789().: V,-vol
123
334
Page 2 of 16
M. L. Rhodes, T. G. Wong
of a coin that specifies the direction of a walker. Since then, coined quantum walks have led to the discovery of several quantum algorithms, including algorithms for searching [5], solving element distinctness [6], finding triangles in graphs or networks [7], and evaluating Boolean formulas [8]. The walk is encoded on a graph of N vertices, where the vertices specify the possible positions of the walker, and the edges specify the directions along which the walker can face. If the graph is regular with degree d, the Hilbert space of the quantum walk is C N ⊗ Cd , which is the tensor product of the vertex space and the coin space. One step of a coined quantum walk consists of applying a quantum coin flip (I N ⊗ C) followed by a shift S to adjacent vertices, so Uwalk = S(I N ⊗ C). To search for a marked vertex using a quantum walk, the walker |ψ(t) begins in a uniform superposition over the vertices and directions: |ψ(0) = |
Data Loading...
