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,Ω) 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(σ)≤THTConc(σ), 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)
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.
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.
A discrete-time quantum walk on a graph is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. We derive an expression for hitting time using superoperators, and numerically evaluate it for the walk on the hypercube for various coins and decoherence models. 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 phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group.
Symmetries of a graph, given by its automorphism group, can be inherited by the evolution operator. 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. Symmetry can cause the walk to also be confined to a subspace of the original Hilbert space for cartain initial states. We show that a quantum walk confined to the subspace corresponding to this symmetry group can be seen as a different quantum walk on a smaller quotient graph. We give an explicit construction of the quotient graph for any subgroup H of the automorphism group. The automorphisms of the quotient graph which are inherited from the original graph are the original automorphism group modulo the subgroup H used to construct it. We conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speed-up. Finally, we use symmetry and the theory of decoherence-free subspaces to determine when the subspace of the quotient graph is a decoherence-free subspace of the dynamics.