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=Cay(ℤ2d,Ω) of degree Δ=|Ω|. Starting from the vertex labeled $0$, we identify σ=⨁ω∈Ωω as a natural target vertex; for the hypercube, σ is precisely the antipodal vertex. For families with Δ→∞, let T be an integer having the same parity as Δ and satisfying $ \left|T-\frac{πΔ}{2}\right|\leq 1. $ We show that the probability pT(σ) of finding the walker at σ when it is measured at time T satisfies pT(σ)=1−O(Δ−1/5). Thus the target is found with probability tending to one after Θ(Δ) steps. For the concurrently measured walk, let HTConc(σ) denote the probability that the target is detected at or before time T when it is tested after every step. We prove pT(σ)≤ T HTConc(σ), which implies HTConc(σ)=Ω(Δ−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)
Related
- Harmonic Reduction of Spin-Coupled Grover Walks on Hypercubes via Quantum Bernoulli Noises
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
- Ancilla-mediated fixed-point quantum search using Grover iterations
- Experimental quantum-computing-enhanced sensing using Grover's algorithm
- Do Quantum AIs Dream in Paths? Path-Integral Slow Thinking through Grover Interference
BibTeX
@misc{mulherkar2026oneshot,
title = {{One-Shot and Concurrent Hitting Times for Grover-Coined Quantum Walks on Cubelike Graphs}},
author = {Jaideep Mulherkar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04503},
eprint = {2609.04503},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04503},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - One-Shot and Concurrent Hitting Times for Grover-Coined Quantum Walks on Cubelike Graphs
AU - Jaideep Mulherkar
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04503
UR - https://arxiv.org/abs/2609.04503
AB - We study the one-shot and concurrent hitting for the discrete-time Grover-coined quantum walk on cubelike graphs G=Cay(ℤ_2^d,Ω) of degree Δ=|Ω|. Starting from the vertex labeled $0$, we identify σ=⨁_ω∈Ωω as a natural target vertex; for the hypercube, σ is precisely the antipodal vertex. For families with Δ→∞, let T be an integer having the same parity as Δ and satisfying $ \left|T-\frac{πΔ}{2}\right|\leq 1. $ We show that the probability p_T(σ) of finding the walker at σ when it is measured at time T satisfies p_T(σ)=1−O(Δ^−1/5). Thus the target is found with probability tending to one after Θ(Δ) steps. For the concurrently measured walk, let H_T^Conc(σ) denote the probability that the target is detected at or before time T when it is tested after every step. We prove p_T(σ)≤ T H_T^Conc(σ), which implies H_T^Conc(σ)=Ω(Δ^−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)
ER -