Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.

arXiv:2112.03744Journal of Physics A Mathematical and TheoreticalMay 12, 20229 citations

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$ -regular, $d$ -colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$ , but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$-regular, $d$-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).

arXiv:1501.06950Physical Review AJun 5, 201517 citations

d

-regular,

d

-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time

O(\sqrt{N}logN)

, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the

O(\sqrt{N}logN)

scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).