Recurrence properties of unbiased coined quantum walks on infinite $d$-dimensional lattices

Recurrence properties of unbiased coined quantum walks on infinite $d$ -dimensional lattices

M. Štefaňák, T. Kiss, and I. Jex

Phys. Rev. A 78, 032306 – Published 3 September 2008

Abstract

The Pólya number characterizes the recurrence of a random walk. We apply the generalization of this concept to quantum walks [M. Štefaňák et al., Phys. Rev. Lett. 100, 020501 (2008)] which is based on a specific measurement scheme. The Pólya number of a quantum walk depends, in general, on the choice of the coin and the initial coin state, in contrast to classical random walks where the lattice dimension uniquely determines it. We analyze several examples to depict the variety of possible recurrence properties. First, we show that for the class of quantum walks driven by Hadamard tensor-product coins, the Pólya number is independent of the initial conditions and the actual coin operators, thus resembling the property of the classical walks. We provide an estimation of the Pólya number for this class of quantum walks. Second, we examine the two-dimensional Grover walk, which exhibits localization and thus is recurrent, except for a particular initial state for which the walk is transient. We generalize the Grover walk to show that one can construct in arbitrary dimensions a quantum walk which is recurrent. This is in great contrast with classical walks which are recurrent only for the dimensions $d = 1, 2$ . Finally, we analyze the recurrence of the 2D Fourier walk. This quantum walk is recurrent except for a two-dimensional subspace of the initial states. We provide an estimation of the Pólya number in its dependence on the initial state.

Received 7 May 2008

DOI:https://doi.org/10.1103/PhysRevA.78.032306

Authors & Affiliations

M. Štefaňák¹, T. Kiss², and I. Jex¹

¹Department of Physics, FJFI ČVUT, Břehová 7, 115 19 Praha 1-Staré Město, Czech Republic
²Department of Nonlinear and Quantum Optics, Research Institute for Solid State Physics and Optics, Hungarian Academy of Sciences, Konkoly-Thege M. u. 29-33, H-1121 Budapest, Hungary

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 78, Iss. 3 — September 2008

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
(Color online) Probability distribution of the 2D Hadamard walk after 50 steps and the probability $p_{0} (t)$ for different choices of the initial state. In the upper plot we choose the initial state $\frac{1}{2} {(1, i, i, - 1)}^{T}$ , which leads to a symmetric probability distribution, whereas in the middle plot we choose the initial state ${(1, 0, 0, 0)}^{T}$ resulting in a dominant peak of the probability distribution in the lower-left corner of the $(m, n)$ plane. However, the initial state influences the probability distribution only near the edges. The probability $p_{0} (t)$ is unaffected and is the same for all initial coin states. The lower plot confirms the asymptotic behavior $p_{0} (t) \sim t^{- 2}$ independent of the initial state.Reuse & Permissions
Figure 2
(Color online) Probability distribution of the Grover walk after 50 steps for different choices of the initial state. In the upper plot we choose the initial state $ψ_{S} = \frac{1}{2} {(1, i, i, - 1)}^{T}$ , which leads to a symmetric probability distribution with a dominant central spike. However, if we choose the initial state $ψ_{G}$ according to Eq. (51) we find that the central spike vanishes and most of the probability is situated at the edges, as depicted in the lower plot.Reuse & Permissions
Figure 3
The probability $p_{0} (t)$ for the Grover walk and different choices of the initial coin state. First, the walk starts with the coin state $ψ_{S} = \frac{1}{2} {(1, i, i, - 1)}^{T}$ , which leads to the nonvanishing value of $p_{0} (t)$ , as depicted in the upper plot. The situation is the same for all initial coin states, up to the asymptotic value of $p_{0} (t \to + \infty)$ , except for $ψ_{G} = \frac{1}{2} {(1, - 1, - 1, 1)}^{T}$ , as shown in the lower plot. Here we plot the probability $p_{0} (t)$ multiplied by $t^{2}$ to unravel the asymptotic behavior of $p_{0} (t)$ . The plot confirms the analytic result of the scaling $p_{0} (t) \sim t^{- 2}$ .Reuse & Permissions
Figure 4
(Color online) Probability distribution after 50 steps and the time evolution of the probability $p_{0} (t)$ for the Fourier walk with the initial state $ψ = {(1, 0, 0, 0)}^{T}$ . The upper plot of the probability distribution reveals a presence of the central peak. Indeed, $ψ$ is not a member of the family $ψ_{F} (a, b)$ . However, in contrast to the Grover walk the peak vanishes. In the lower plot we illustrate this by showing the probability $p_{0} (t)$ multiplied by $t$ to unravel the asymptotic behavior $p_{0} (t) \sim t^{- 1}$ .Reuse & Permissions
Figure 5
(Color online) Probability distribution after 50 steps and the time evolution of the probability $p_{0} (t)$ for the Fourier walk with the initial state given by Eq. (68). Since $ψ$ is a member of the family $ψ_{F} (a, b)$ the central peak in the probability distribution is not present, as depicted in the upper plot. The lower plot indicates that the probability $p_{0} (t)$ decays like $t^{- 2}$ .Reuse & Permissions
Figure 6
(Color online) Approximation of the Pólya numbers for the 2D Fourier walk and the initial states from the family of states defined by Eq. (67) in their dependence on the parameters of the initial state $a$ and $ϕ$ . Here we have evaluated the first 100 terms of $p_{0} (a, ϕ, t)$ exactly. The Pólya numbers cover the whole interval between the minimal value of $P_{F}^{\min} \approx 0.314$ and the maximal value of $P_{F}^{\max} \approx 0.671$ . The extreme values are attained for $a = 1 ∕ 2$ and $ϕ^{\min} = 7 π ∕ 4$ , respectively, $ϕ^{\max} = 3 π ∕ 4$ . On the lower plot we show the cut at the value $a = 1 ∕ 2$ containing both the maximum and the minimum.Reuse & Permissions

Physical Review A

covering atomic, molecular, and optical physics and quantum information