Quantum walk is the quantum analogue of the classical random walk. Its application in search has demonstrated the capability to solve certain types of problems more efficiently than classical methods. The quantum walk search on the dihedral Cayley graph with 2N vertices is examined under several generating sets \(\mathcal {S}\). With the minimal generating set, the results show that the layout is an exceptional configuration. By adding a self-loop edge with some weight w > 0, which coincides with the lackadaisical quantum walk framework, and extra edges for each vertex, a nearly constant success probability of around 0.80 can be obtained using the proposed weight \(w^{\prime }=\frac{1}{N}\). The fitted number of steps is given by τ′ = 1.221N − 0.391. A comparison with the cycle graph is made, demonstrating improvement in the expected number of steps under the same vertex set size.
Quantum walk is the quantum analogue of the classical random walk. Its application in search has demonstrated the capability to solve certain types of problems more efficiently than classical methods. The quantum walk search on the dihedral Cayley graph with 2N vertices is examined under several generating sets (\mathcal {S}). With the minimal generating set, the results show that the layout is an exceptional configuration. By adding a self-loop edge with some weight w > 0, which coincides with the lackadaisical quantum walk framework, and extra edges for each vertex, a nearly constant success probability of around 0.80 can be obtained using the proposed weight (w^{\prime }=\frac{1}{N}). The fitted number of steps is given by τ′ = 1.221N − 0.391. A comparison with the cycle graph is made, demonstrating improvement in the expected number of steps under the same vertex set size.
Lackadaisical quantum walks are coined quantum walk models in which each vertex is associated with a weighted self-loop, allowing the walker to remain at its current position. They have been shown to effectively enhance spatial search on various graphs under different oracle models, with the cyclic graph being the most fundamental instance. In this paper, lackadaisical quantum walk search is studied on Cayley graphs of dicyclic groups, a non-abelian extension of cyclic groups, under three different oracle models. A preliminary analysis of the search performance is first conducted on dicyclic Cayley graphs with respect to the minimal generating set of the underlying dicyclic group. By expanding the generating sets to enable symmetric exploration and applying an appropriate oracle, the quantum walk search achieves a near-one success probability. Under our proposed configurations, the expected runtime to search on dicyclic Cayley graphs outperforms both quantum walk search on the cycle graph and classical unstructured search.
Abstract The evolution operator of the lackadaisical quantum walk on a weighted cycle graph with self-loop weight w>0 w > 0 is examined. With Grover oracle, the effect of different values of w w on the success probability of the search under various hyperparameter combinations is analyzed. The success probability function of the first few steps is provided algebraically, which in turn highlights the role of w w in governing the evolutionary behavior of the quantum walk search. These studies subsequently allow the numerical results to be obtained for various hyperparameter combinations, showing that the highest success probability for the weighted cycle graph with N N vertices is achieved using a flip-flop shift operator, a weighted coin superposition initial state, and w=N1.26 w = 1.26 N . A comparison is also made with other known oracle, demonstrating that the proposed configuration provides a better trade-off between success probability and runtime. An extension of the study to the SKW scheme is also included, and it demonstrates that the scheme provides more variability and potential for quantum walk search.
Abstract Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science. The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks. Quantum walks show promise for faster mixing times than classical methods but lack universal proof, especially in finite group settings. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D 2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω ( n 2 log ( 1 / 2 ϵ ) ) , the continuous-time quantum walk mixing time on D 2n is of order O ( n ( log n ) 5 log ( 1 / ϵ ) ) , achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D 2n . This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
Abstract We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy’s quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has l integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight l . We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover’s algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when l < 3 + 2 2 ≈ 5.828 .
Abstract Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.
The concept of lackadaisical quantum walk -- quantum walk with self loops -- was first introduced for discrete-time quantum walk on one-dimensional line. Later it was successfully applied to improve the running time of the spacial search on two-dimensional grid. In this paper we study search by lackadaisical quantum walk on the two-dimensional grid with multiple marked vertices. First, we show that the lackadaisical quantum walk, similarly to the regular (non-lackadaisical) quantum walk, has exceptional configuration, i.e. placements of marked vertices for which the walk has no speed-up over the classical exhaustive search. Next, we demonstrate that the weight of the self-loop suggested in the previous papers is not optimal for multiple marked vertices. And, last, we show how to adjust the weight of the self-loop to overcome the aforementioned problem.