Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.04503

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

Jaideep Mulherkar

quant-phSubmitted Sep 3, 2026• Announced Sep 7, 2026• 0 citations
arXivHTMLPDF

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,Ω)$ of degree $Δ=|Ω|$. Starting from the vertex labeled $0$, we identify $σ=\bigoplus_{ω\inΩ}ω$ as a natural target vertex; for the hypercube, $σ$ is precisely the antipodal vertex. For families with $Δ\to\infty$, 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^{\mathrm{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(σ)\leq T H_T^{\mathrm{Conc}}(σ), $$ which implies $H_T^{\mathrm{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)

Comments
23 pages 1 figure

Related papers

Implementation of quantum hitting times of cubelike graphs on IBM’s Qiskit platform

Jaideep Mulherkar, Rishikant Rajdeepak, V. Sunitha

In this paper, we give a procedure to construct quantum circuits for implementing discrete-time quantum walks on a family of Cayley graphs called cubelike graphs. We construct these circuits on IBM’s Qiskit platform and demonstrate an implementation of the quantum hitting times on cubelike graphs. Based on our numerical study, we conjecture that for all families of cubelike graphs there is a linear relationship between the degree of a cubelike graph and its hitting time which holds asymptotically. This conjecture, if proved, will generalize the result of hitting times of discrete-time quantum walks on hypercubes to general family of cubelike graphs.

arXiv:2108.13769•International Journal of Quantum Information•Jul 13, 2022•1 citation

Influence of coin symmetry on infinite hitting times in quantum walks

Prithviraj Prabhu, Todd A. Brun

Classical random walks on finite graphs have an underrated property: a walk from any vertex can reach every other vertex in finite time, provided they are connected. Discrete-time quantum walks on finite connected graphs, however, can have infinite hitting times. This phenomenon is related to graph symmetry, as previously characterized by the group of direction-preserving graph automorphisms that trivially affect the coin Hilbert space. If a graph is symmetric enough (in a particular sense), then the associated quantum walk unitary will contain eigenvectors that do not overlap a set of target vertices for any coin-flip operator. These eigenvectors span the infinite-hitting-time (IHT) subspace. Quantum states in the IHT subspace never reach the target vertices, leading to infinite hitting times. However, this is not the whole story: the graph of the three-dimensional cube does not satisfy this symmetry constraint, yet quantum walks on this graph with certain symmetric coins can exhibit infinite hitting times. We study the effect of coin symmetry by analyzing the group of coin-permutation symmetries (CPSs): graph automorphisms that act nontrivially on the coin Hilbert space but leave the coin operator invariant. Unitaries using highly symmetric coins with large CPS groups, such as the permutation-invariant Grover coin, are associated with higher probabilities of never arriving, as a result of their larger IHT subspaces.

arXiv:2107.02383•Physical Review A•Mar 11, 2022•2 citations

Quantum walk in symmetric Cayley graph over $\Z_2^n$

I. M. Khuziev

We show that the hitting time of the discrete quantum walk on a symmetric Cayley graph over $\Z_2^n $ from a vertex to its antipodal is polynomial in degree of the graph. We prove that returning time of quantum walk on a symmetric Cayley graph over $\Z_2^n $ is polynomial and the probability to hit is almost one. To prove it, we give a new estimation of Kravchuk coefficients. We give an example of a probabilistic polynomial algorithm that finds an antipodal vertex in symmetric Cayley graphs.

arXiv:1305.6849•May 29, 2013•2 citations

Quantum walks with infinite hitting times

Hari Krovi, Todd A. Brun

Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.

arXiv:quant-ph/0606094•Physical Review A•Oct 27, 2006•84 citations

Quantum walks on embedded hypercubes

Adi Makmal, Manran Zhu, Daniel Manzano +2 more

It has been proved by Kempe that discrete quantum walks on the hypercube (HC) hit exponentially faster than the classical analog. The same was also observed numerically by Krovi and Brun for a slightly different property, namely, the expected hitting time. Yet, to what extent this striking result survives in more general graphs is to date an open question. Here, we tackle this question by studying the expected hitting time for quantum walks on HCs that are embedded into larger symmetric structures. By performing numerical simulations of the discrete quantum walk and deriving a general expression for the classical hitting time, we observe an exponentially increasing gap between the expected classical and quantum hitting times, not only for walks on the bare HC, but also for a large family of embedded HCs. This suggests that the quantum speedup is stable with respect to such embeddings.

arXiv:1309.5253•Physical Review A•Aug 14, 2014•19 citations

Hitting time for quantum walks on the hypercube

Hari Krovi, Todd A. Brun

Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. To be analogous to the hitting time for a classical walk, the quantum hitting time must involve repeated measurements as well as unitary evolution. We derive an expression for hitting time using superoperators, and numerically evaluate it for the discrete walk on the hypercube. The values found are compared to other analogs of hitting time suggested in earlier work. The dependence of hitting times on the type of unitary ``coin'' is examined, and we give an example of an initial state and coin which gives an infinite hitting time for a quantum walk. Such infinite hitting times require destructive interference, and are not observed classically. Finally, we look at distortions of the hypercube, and observe that a loss of symmetry in the hypercube increases the hitting time. Symmetry seems to play an important role in both dramatic speed-ups and slow-downs of quantum walks.

arXiv:quant-ph/0510136•Physical Review A•Mar 27, 2006•131 citations
We study the one-shot and concurrent hitting for the discrete-time Grover-coined quantum walk on cubelike graphs G=Cay(Z2d,Ω)G=\text{Cay}(\mathbb Z_2^d,Ω)G=Cay(Z2d​,Ω) of degree Δ=∣Ω∣Δ=|Ω|Δ=∣Ω∣. Starting from the vertex labeled 000, we identify σ=⨁ω∈Ωωσ=\bigoplus_{ω\inΩ}ωσ=⨁ω∈Ω​ω as a natural target vertex; for the hypercube, σσσ is precisely the antipodal vertex.
For families with Δ→∞Δ\to\inftyΔ→∞, let TTT be an integer having the same parity as ΔΔΔ and satisfying ∣T−πΔ2∣≤1.\left|T-\frac{πΔ}{2}\right|\leq 1.​T−2πΔ​​≤1. We show that the probability pT(σ)p_T(σ)pT​(σ) of finding the walker at σσσ when it is measured at time TTT satisfies pT(σ)=1−O(Δ−1/5).p_T(σ)=1-O(Δ^{-1/5}).pT​(σ)=1−O(Δ−1/5). Thus the target is found with probability tending to one after Θ(Δ)Θ(Δ)Θ(Δ) steps.
For the concurrently measured walk, let HTConc(σ)H_T^{\mathrm{Conc}}(σ)HTConc​(σ) denote the probability that the target is detected at or before time TTT when it is tested after every step. We prove pT(σ)≤THTConc(σ),p_T(σ)\leq T H_T^{\mathrm{Conc}}(σ),pT​(σ)≤THTConc​(σ), which implies HTConc(σ)=Ω(Δ−1)H_T^{\mathrm{Conc}}(σ)=Ω(Δ^{-1})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)
In this paper, we give a procedure to construct quantum circuits for implementing discrete-time quantum walks on a family of Cayley graphs called cubelike graphs. We construct these circuits on IBM’s Qiskit platform and demonstrate an implementation of the quantum hitting times on cubelike graphs. Based on our numerical study, we conjecture that for all families of cubelike graphs there is a linear relationship between the degree of a cubelike graph and its hitting time which holds asymptotically. This conjecture, if proved, will generalize the result of hitting times of discrete-time quantum walks on hypercubes to general family of cubelike graphs.
Classical random walks on finite graphs have an underrated property: a walk from any vertex can reach every other vertex in finite time, provided they are connected. Discrete-time quantum walks on finite connected graphs, however, can have infinite hitting times. This phenomenon is related to graph symmetry, as previously characterized by the group of direction-preserving graph automorphisms that trivially affect the coin Hilbert space. If a graph is symmetric enough (in a particular sense), then the associated quantum walk unitary will contain eigenvectors that do not overlap a set of target vertices for any coin-flip operator. These eigenvectors span the infinite-hitting-time (IHT) subspace. Quantum states in the IHT subspace never reach the target vertices, leading to infinite hitting times. However, this is not the whole story: the graph of the three-dimensional cube does not satisfy this symmetry constraint, yet quantum walks on this graph with certain symmetric coins can exhibit infinite hitting times. We study the effect of coin symmetry by analyzing the group of coin-permutation symmetries (CPSs): graph automorphisms that act nontrivially on the coin Hilbert space but leave the coin operator invariant. Unitaries using highly symmetric coins with large CPS groups, such as the permutation-invariant Grover coin, are associated with higher probabilities of never arriving, as a result of their larger IHT subspaces.
Quantum walk in symmetric Cayley graph over Z2n\Z_2^nZ2n​
Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.
It has been proved by Kempe that discrete quantum walks on the hypercube (HC) hit exponentially faster than the classical analog. The same was also observed numerically by Krovi and Brun for a slightly different property, namely, the expected hitting time. Yet, to what extent this striking result survives in more general graphs is to date an open question. Here, we tackle this question by studying the expected hitting time for quantum walks on HCs that are embedded into larger symmetric structures. By performing numerical simulations of the discrete quantum walk and deriving a general expression for the classical hitting time, we observe an exponentially increasing gap between the expected classical and quantum hitting times, not only for walks on the bare HC, but also for a large family of embedded HCs. This suggests that the quantum speedup is stable with respect to such embeddings.
Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. To be analogous to the hitting time for a classical walk, the quantum hitting time must involve repeated measurements as well as unitary evolution. We derive an expression for hitting time using superoperators, and numerically evaluate it for the discrete walk on the hypercube. The values found are compared to other analogs of hitting time suggested in earlier work. The dependence of hitting times on the type of unitary ``coin'' is examined, and we give an example of an initial state and coin which gives an infinite hitting time for a quantum walk. Such infinite hitting times require destructive interference, and are not observed classically. Finally, we look at distortions of the hypercube, and observe that a loss of symmetry in the hypercube increases the hitting time. Symmetry seems to play an important role in both dramatic speed-ups and slow-downs of quantum walks.