One-dimensional coinless quantum walks

A coinless, discrete-time quantum walk possesses a Hilbert space whose dimension is smaller compared to the widely studied coined walk. Coined walks require the direct product of the site basis with the coin space; coinless walks operate purely in the site basis, which is clearly minimal. These coinless quantum walks have received considerable attention recently because they have evolution operators that can be obtained by a graphical method based on lattice tessellations and they have been shown to be as efficient as the best known coined walks when used as a quantum search algorithm. We argue that both formulations in their most general form are equivalent. In particular, we demonstrate how to transform the one-dimensional version of the coinless quantum walk into an equivalent extended coined version for a specific family of evolution operators. We present some of its basic, asymptotic features for the one-dimensional lattice with some examples of tessellations, and analyze the mixing time and limiting probability distributions on cycles.

Figure 1

Depiction of tessellation options for reflection operators $U_{\vec{0},\vec{1}}$ in Eq. (4) in $D=1$ (left) and $D=2$ (right). Here, we use square blocks of length 2 in both dimensions (top left, and right). However, alternative (local) tessellations are conceivable, such as block-length 3, as shown for $D=1$ (bottom left), which lead to equally efficient QW. As a minimal requirement, at least the combination of both tessellations needs to cover the lattice and both should be sufficiently overlapping.

Figure 2

Plot of the rescaled PDF $t{p}_x\left(t\right)\sim \rho \left(v\right)$ at $t=30$ in the scaling variable $v=\frac{x}{2t}$ for the coinless QW in $D=1$ at $\alpha +\beta =\pi$ and $v_0=sin\alpha =\frac{3}{4}$, initiated at $t=0$ on site $x=0,\left|\mathrm{\Psi }\right(0)\rangle =|0\rangle$. The simulation (dark line) contains some more structure than the full asymptotic form (green shaded line) from Eq. (39) can represent at $t=30$. The envelope function (thickened blue line), also obtained from Eq. (39) by removing the explicitly $t$-dependent phase, represents the average behavior and eccentricity of the exact data quite well, within the range of its validity bracketed by poles at $v=\pm v_0$.

Figure 3

Probability distribution of the coinless three-state QW after 20 steps with the initial state located at $x=0$. The sharp peak at the origin is the signature of the locality always present in the three-state case.

Figure 4

Limiting probability density function for $N=200$. Upper blue (lower red) curve is the PDF for even (odd) sites.

Figure 5

Rescaled total variation distance $\left(t\mathrm{TVD}/N\right)$ as a function of $t/N$ for $N=500$, 2000, and 5000 with colors red, blue, and black, respectively. The dashed line corresponds to the TVD without the oscillatory term, i.e., after removing the term $exp(i({\lambda }_k-{\lambda }_{k^{\prime }})t)$.

Figure 6

Behavior of the first (red $+)$ and second (blue $\times )$ terms of Eq. (68) as a function of $N$. The first term clearly is $O\left(N\right)$.