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=\bigoplus_{\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|\leq 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)\leq 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:2609.04503 [quant-ph]

(or arXiv:2609.04503v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.04503 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.