One-Shot and Concurrent Hitting Times for Grover-Coined Quantum Walks on Cubelike Graphs

Abstract

We study the one-shot and concurrent hitting for the discrete-time Grover-coined quantum walk on cubelike graphs $G=\text{Cay}({\mathbb{Z}}_2^d,\Omega )$ of degree $\Delta =|\Omega |$. Starting from the vertex labeled $0$, we identify $\sigma ={⨁}_{\omega \in \Omega }\omega$ as a natural target vertex; for the hypercube, $\sigma$ is precisely the antipodal vertex. For families with $\Delta \to \infty$, let $T$ be an integer having the same parity as $\Delta$ and satisfying $\left|T-\frac{\pi \Delta }{2}\right|\le 1.$ We show that the probability $p_T(\sigma )$ of finding the walker at $\sigma$ when it is measured at time $T$ satisfies $$p_T(\sigma )=1-O({\Delta }^{-1/5}).$$ Thus the target is found with probability tending to one after $\Theta (\Delta )$ steps. For the concurrently measured walk, let $H_T^{\mathrm{Conc}}(\sigma )$ denote the probability that the target is detected at or before time $T$ when it is tested after every step. We prove $$p_T(\sigma )\le T{H}_T^{\mathrm{Conc}}(\sigma ),$$ which implies $H_T^{\mathrm{Conc}}(\sigma )=\Omega ({\Delta }^{-1})$ over the same time scale. The proof uses the Walsh-Fourier decomposition, an exact two-dimensional reduction of each Fourier mode, and a universal second-moment identity for the associated character sums. Our results extend Kempe's hypercube hitting phenomenon (J. Kempe, Probab. Theory Relat. Fields 133, 215-235, 2005) to arbitrary cubelike generating sets and establish the conjectured asymptotic hitting behavior for cublelike and augmented cubes in Mulherkar, Rajdeepak and Sunitha (Int. J. Quantum Inf. 20,2250020, 2022)

arXiv comment23 pages 1 figure