International Conference on Software and Computer Applications (ICSCA)
Discrete-time quantum walk search on the dihedral Cayley graph
Yong Qing Tiong, Kai Lin Ong, Ian K. T. Tan, Wei Lin Teoh
Abstract
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.