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:2108.13769 · International Journal of Quantum Information

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

Jaideep Mulherkar, Rishikant Rajdeepak, V. Sunitha

Published Jul 13, 2022• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1142/s0219749922500204

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

Experimental Implementation of Discrete Time Quantum Walk with the IBM Qiskit Library

Pierriccardo Olivieri, Mehrnoosh Askarpour, Elisabetta Di Nitto

This paper presents an implementation of quantum random walk using the Qiskit library, given the quantum circuits extracted from the literature. We started by implementing an instance of Coined Discrete Quantum Walk on an 8-node cyclic graph. Observing the limitations of this implementation, we experimented a different approach by proposing an implementation for Szegedy Quantum Walk in the IBM Qiskit library [1]. The proposed solution could be used as a building block to construct quantum implementation of other classic algorithms.

IEEE/ACM International Workshop on Quantum Software Engineering (Q-SE)•Jun 1, 2021•5 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

Quantum networks on cubelike graphs

Anna Bernasconi, Chris D. Godsil, Simone Severini B

Cubelike graphs are the Cayley graphs of the elementary Abelian group ${\mathbb{Z}}_{2}^{n}$ (e.g., the hypercube is a cubelike graph). We study perfect state transfer between two particles in quantum networks modeled by a large class of cubelike graphs. This generalizes the results of Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and Facer et al. [Phys. Rev. A 92, 187902 (2008)].

arXiv:0808.0510•Physical Review A•Nov 12, 2008•88 citations

Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs

Ellinor Wanzambi, Andersson, Stina

In recent years, quantum walks have been widely researched and have shown exciting properties. One such is a quadratic speed-up in hitting time compared to its classical counterpart. In this paper, we design a quantum circuit for the MNRS algorithm, which finds a marked node in a graph with a quantum walk, and use it to find a hitting time for the marked nodes in the walk. We do this by implementing the circuit on IBM quantum simulators and show that the execution on a noise-free simulator results in hitting times that agree with the theoretical expectations. We also run the algorithm on a mock backend that simulates the noise of the IBM Melbourne computer. As expected, the noise has an extensive impact on the output, resulting in outcomes far from the noise-free simulation.

arXiv:2108.02723•Aug 5, 2021•7 citations

Generalized Efficient Quantum Circuit Implementation of Discrete-Time Quantum Walks on Cayley Graphs

Seoyoon Kang

We present a generalized and efficient quantum circuit framework for implementing discrete-time quantum walks (DTQWs) on Cayley graphs of arbitrary dimension. Building on the Boundary QFT scheme of Razzoli et al., we introduce a systematic multi-stage decomposition of the shift operator for 1D Cayley graphs across three classes of generating sets: inverse-closed without involutions, inverse-closed with an involution, and non-inverse-closed. The decomposition hierarchically factorizes the QFT-diagonalized shift operator into structured block components, progressively reducing the control degree of the required rotation gates and replacing high-degree multi-qubit controlled operations with collections of lower-degree equivalents. We extend this construction to $d$-dimensional torus graphs and provide explicit circuit implementations for an 8-Cayley graph and a $\mathbb{Z}_{16} \times \mathbb{Z}_8$ torus graph as concrete illustrations. Gate complexity analysis using the linear CNOT scaling of Rosa et al. demonstrates that the decomposed implementation achieves a substantial reduction in upper-bound CNOT cost relative to the naive implementation within the regime $k \leq 64$ for inverse-closed graphs and $k \leq 16$ for non-inverse-closed graphs, where $k$ denotes the degree of the generating set. Benchmarking further reveals that this efficiency gain is largely insensitive to the system size $N$, identifying $k$ as the dominant resource parameter for the shift operator. These results provide a scalable and hardware-conscious pathway toward practical DTQW implementations on near-term quantum devices.

quant-pharXiv:2608.25136•Aug 27, 2026•0 citations
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.
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)
This paper presents an implementation of quantum random walk using the Qiskit library, given the quantum circuits extracted from the literature. We started by implementing an instance of Coined Discrete Quantum Walk on an 8-node cyclic graph. Observing the limitations of this implementation, we experimented a different approach by proposing an implementation for Szegedy Quantum Walk in the IBM Qiskit library [1]. The proposed solution could be used as a building block to construct quantum implementation of other classic algorithms.
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.
Cubelike graphs are the Cayley graphs of the elementary Abelian group Z2n{\mathbb{Z}}_{2}^{n}Z2n​ (e.g., the hypercube is a cubelike graph). We study perfect state transfer between two particles in quantum networks modeled by a large class of cubelike graphs. This generalizes the results of Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and Facer et al. [Phys. Rev. A 92, 187902 (2008)].
In recent years, quantum walks have been widely researched and have shown exciting properties. One such is a quadratic speed-up in hitting time compared to its classical counterpart. In this paper, we design a quantum circuit for the MNRS algorithm, which finds a marked node in a graph with a quantum walk, and use it to find a hitting time for the marked nodes in the walk. We do this by implementing the circuit on IBM quantum simulators and show that the execution on a noise-free simulator results in hitting times that agree with the theoretical expectations. We also run the algorithm on a mock backend that simulates the noise of the IBM Melbourne computer. As expected, the noise has an extensive impact on the output, resulting in outcomes far from the noise-free simulation.
We present a generalized and efficient quantum circuit framework for implementing discrete-time quantum walks (DTQWs) on Cayley graphs of arbitrary dimension. Building on the Boundary QFT scheme of Razzoli et al., we introduce a systematic multi-stage decomposition of the shift operator for 1D Cayley graphs across three classes of generating sets: inverse-closed without involutions, inverse-closed with an involution, and non-inverse-closed. The decomposition hierarchically factorizes the QFT-diagonalized shift operator into structured block components, progressively reducing the control degree of the required rotation gates and replacing high-degree multi-qubit controlled operations with collections of lower-degree equivalents. We extend this construction to ddd-dimensional torus graphs and provide explicit circuit implementations for an 8-Cayley graph and a Z16×Z8\mathbb{Z}_{16} \times \mathbb{Z}_8Z16​×Z8​ torus graph as concrete illustrations. Gate complexity analysis using the linear CNOT scaling of Rosa et al. demonstrates that the decomposed implementation achieves a substantial reduction in upper-bound CNOT cost relative to the naive implementation within the regime k≤64k \leq 64k≤64 for inverse-closed graphs and k≤16k \leq 16k≤16 for non-inverse-closed graphs, where kkk denotes the degree of the generating set. Benchmarking further reveals that this efficiency gain is largely insensitive to the system size NNN, identifying kkk as the dominant resource parameter for the shift operator. These results provide a scalable and hardware-conscious pathway toward practical DTQW implementations on near-term quantum devices.