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)
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. 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′=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.
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.
Let χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.