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:1305.6849

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

I. M. Khuziev

Published May 29, 2013• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1305.6849

Related papers

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

Jaideep Mulherkar

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)

quant-pharXiv:2609.04503•Sep 7, 2026•0 citations

Discrete-time quantum walk search on the dihedral Cayley graph

Yong Qing Tiong, Kai Lin Ong, Ian K. T. Tan +1 more

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.

International Conference on Software and Computer Applications (ICSCA)•Feb 3, 2026•0 citations

Implementation of hitting times of discrete time quantum random walks on Cubelike graphs

Jaideep Mulherkar, Rishikant Rajdeepak, V. Sunitha

We demonstrate an implementation of the hitting time of a discrete time quantum random walk on cubelike graphs using IBM's Qiskit platform. Our implementation is based on efficient circuits for the Grover and Shift operators. We verify the results about the one-shot hitting time of quantum walks on a hypercube as proved in [https://link.springer.com/article/10.1007/s00440-004-0423-2]. We extend the study to another family of cubelike graphs called the augmented cubes [https://onlinelibrary.wiley.com/doi/abs/10.1002/net.10033]. 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. That is, for any cubelike graph of degree $Δ$, the probability of finding the quantum random walk at the target node at time $\frac{πΔ}{2}$ approaches 1 as the degree $Δ$ of the cubelike graph approaches infinity.

arXiv:2108.13769•Aug 31, 2021•0 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•87 citations

Quantum Random Walks Hit Exponentially Faster

Julia Kempe

We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum random walks. We provide the framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We then give an application to random routing.

arXiv:quant-ph/0205083•May 14, 2002•95 citations

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.

International Journal of Quantum Information•Jul 13, 2022•0 citations
Quantum walk in symmetric Cayley graph over Z2n\Z_2^nZ2n​
We show that the hitting time of the discrete quantum walk on a symmetric Cayley graph over Z2n\Z_2^n Z2n​ 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 Z2n\Z_2^n Z2n​ 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.
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 $ \left|T-\frac{πΔ}{2}\right|\leq 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)
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 S\mathcal {S}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′=1Nw^{\prime }=\frac{1}{N}w′=N1​. 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.
We demonstrate an implementation of the hitting time of a discrete time quantum random walk on cubelike graphs using IBM's Qiskit platform. Our implementation is based on efficient circuits for the Grover and Shift operators. We verify the results about the one-shot hitting time of quantum walks on a hypercube as proved in [https://link.springer.com/article/10.1007/s00440-004-0423-2]. We extend the study to another family of cubelike graphs called the augmented cubes [https://onlinelibrary.wiley.com/doi/abs/10.1002/net.10033]. 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. That is, for any cubelike graph of degree ΔΔΔ, the probability of finding the quantum random walk at the target node at time πΔ2\frac{πΔ}{2}2πΔ​ approaches 1 as the degree ΔΔΔ of the cubelike graph approaches infinity.
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.
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.