General methods and properties to evaluate continuum limits of the 1D discrete time quantum walk

The discrete time quantum walk (DTQW) has been the subject of much attention since it was introduced in Ref. [1] and independently in Ref. [2], and also its applications to quantum computing were discovered in the analysis of Hadamard Walks [3]. The DTQW has since been used in a variety of quantum computing algorithms, including the Oracular Search [4] and Element distinctness [5] algorithms (for a full list, see Ref. [6]).

As noted in Ref. [7], a now well-studied limit of the DTQW was introduced by Feynman and Hibbs [8] in constructing a path integral formulation for the propagator of the Dirac equation. According to Feynman, a particle zig-zags at the speed of light across a spacetime lattice, flipping its chirality from left to right with an infinitesimal probability at each time step [7]. The Dirac equation results when the continuous spacetime limit is taken, with the mass of the particle determined by the flipping rate. More recent works have produced notions of discrete spacetimes (see Refs. [9, 10]) and consequent questions regarding how they produce our apparent continuum.

Since the writing of this paper it has been communicated to us that our work has intersected the results of Ref. [11]. By analyzing different scalings among \(\varDelta x\), \(\varDelta t\), and the speed of propogation c, the authors in Ref. [11] have developed a quantum simulation scheme known as a Plastic Quantum Walk which supports a continuous spacetime limit and a continuous time-discrete space limit. They also show that the procedure for obtaining such a walk yields a curved spacetime Hamiltonian for lattice-fermions with synchronous coordinates. In particular, the results in Sect. 4 of our work intersect those in Ref. [11], as we both find all parametrizations of unitary coins which permit continuous time-discrete space 1D continuum limits. However, our work deviates from theirs when we use these parametrizations to find solutions to the resultant continuum limit in Corollary 1, and in Sect. 7 we use the parametrization to show how the DTQW is related to the CTQW in general.

Other notable recent work includes Mlodinow and Brun in Ref. [12] demonstrating how to constrain a 3D DTQW to obtain a resulting fully Lorenz invariant continuum limit. They showed that their symmetry requirement necessitates the inclusion of antimatter, and, in Ref. [13], discuss experimental methods to distinguish between the DTQW and its continuum limiting Dirac equation as a description of fermion dynamics. These limits were also central to Refs. [14, 15]. Their continuum limits for DTQWs transformed discrete time evolution equations to partial differential equations (PDEs), as the PDEs analyzed were much simpler than the discrete recursion relations of the DTQW.

Strauch [7] also used the continuum limit to connect the DTQW and CTQW, and Refs. [16, 17], and more recently [18], demonstrate that the free particle Dirac evolution could be obtained by taking continuum limits of the DTQW. Strauch also demonstrated, in Ref. [16], the DTQW’s connections with zitterbewegung, which is an interference effect among free relativistic Dirac particles between their positive and negative energy parts that produces a quivering motion [19]. Strauch shows that zitterbewegung in the DTQW can be tuned based on the value of its coin rotation parameter, and shows that the CTQW contains zitterbewegung-like oscillations (which Strauch denotes as anomalous zitterbewegung) even though there is only one energy for the CTQW [16].

At this time, several forms of continuum limits have already been rigorously developed, including general space and time limits with coin variations, in Refs. [16, 20], and the continuous time limit for a very particular choice of coin in Ref. [7].

The purpose of this work is to formulate a general framework within which continuum limits of the DTQW can be taken, and to analyze the corresponding dynamics in the various limits. From our analysis, we determine all possible coins with which a continuous time and discrete space limit can be taken in 1D\(+\)1 (Sect. 4), and we show that the previous result in [11] is a special case of our general procedure. We also show that taking time and space limits simultaneously with a fixed coin is possible when steps in the walk are allowed and yields a massless dirac equation (Sect. 5). We then show that the ensuing time evolution derived from taking a continuous space limit of the continuous time limit of the DTQW is a massless dirac equation as well (Sect. 6). Lastly, we prove that the solutions of the continuous time limit of the DTQW can always be related to the solutions of the CTQW for any choice of coin allowed to undergo the continuous time limit of the DTQW (Sect. 7).

Skipping steps Before formulating a universal definition of continuum limits for the quantum walk, we want to establish the important notion of so-called alternating limits, in which only steps of a certain parity (e.g. even or odd) are considered observed. We first provide an informal example demonstrating that trivial divergences occur in the \(\varDelta t \rightarrow 0\) limit arising from multiple parity-dependent limits in the discrete walk. Such limits were considered in Ref. [7].

Consider the DTQW with coin \(C=i\mathrm{e}^{i\theta \sigma _x}\), with \(\sigma _x\) a standard Pauli matrix and \(\theta \equiv \theta (\varDelta t)\) a real number (modulo \(2\pi \)) depending on the time discretization parameter \(\varDelta t\). For the example we construct an informal continuous time limit, to be formalized in Definition 1. Essentially we will take the \(\varDelta t\rightarrow 0\) limit in Eq. (5). The continuous time limit then amounts to identifying the limiting operatorassuming a fixed space of functions \({\mathbb {X}}\) on which it acts; here \({\mathbb {I}}\) is the identity. This is defined more carefully later in this section within Formal definitions.

For this analysis of a continuous time limit for the discrete space and time quantum walk, we will seek the most general scaling of walk parameters that admit nontrivial limits as \(\varDelta t\rightarrow 0\). In this case we will admit all scalings for the coin parameter of the form \(\theta =\pi /2+\gamma \varDelta t\), with \(\gamma >0\), which were introduced by Strauch [7]. Thus from the operator standpoint we seek a limit of the form \(\lim _{\varDelta t\rightarrow 0}\frac{i\mathrm{e}^{ik\varDelta x\sigma _z}i\sigma _x \mathrm{e}^{i\gamma \varDelta t\sigma _x}-{\mathbb {I}}}{\varDelta t}\), which in fact does not exist generically. We show here however, that if we consider only even parity steps (i.e. even numbers of steps, effectively considering only every other step), then non-trivial limits exist. Thus, we will be considering only iterations of the even parity operator SCSC rather than the fundamental step SC, and we will identify a limit \(\lim _{\varDelta t\rightarrow 0}\frac{{\widetilde{S}}(\varDelta x)C(\varDelta t){\widetilde{S}}(\varDelta x)C(\varDelta t)-{\mathbb {I}}}{\varDelta t}\), which structurally is:As might be expected, it will be clear below that replacing the above even power \((SC)^n\) with \(n=2\) by \(n=3\), the above limiting process will no longer exist; existence of the limit will hold only for even powers n. In general, restricting to fixed even step sizes n will lead to continuous limiting processes as above (with scaling of the coin based on \(\varDelta t\)), while non-even step sizes will never admit such limits (see Theorem 2, proved in Appendix A).

Formal definitions. Definitions of our operator limits require common spaces for their domains. We will redefine all operators on such a common space, given aswhere \(\Sigma \) is the space spanned by \(|{L}\rangle =\begin{pmatrix}1\\ 0\end{pmatrix}\) and \(|{R}\rangle =\begin{pmatrix}0\\ 1\end{pmatrix}\). Note that the effective domain space of the above tensor product space is \({\mathbb {R}}\times \Sigma \), with \(\Sigma ={L,R}\). Thus, \(\overrightarrow{\varPsi }(x,t)\) is assumed once continuously differentiable in t, with two components in \(L^2\) (i.e. square integrable functions in \(x\in {\mathbb {R}}\) for fixed t).

We will consider general quantum walks that have \(\varDelta t\rightarrow 0\) limits when step numbers \(n=km\) are restricted to whole multiples of an integer n, i.e. generalizing the above parity restriction for step numbers \((n=2)\) to accommodate more general step number restrictions. Thus, let \(\overrightarrow{\varPsi }(x,t)\in {\mathbb {X}}\), n be the number of skipped steps, \(\partial _t\) be the time derivative operator, and define the discrete derivative as \(\varDelta _t\overrightarrow{\varPsi }(x,t)=\frac{\overrightarrow{\varPsi }(x,t+n\varDelta t)-\overrightarrow{\varPsi }(x,t)}{n\varDelta t}\). If \(\overrightarrow{\varPsi }(x,t)\in {\mathbb {X}}\) is a wave function, then the DTQW time evolution equation isWe denote the level of discretization of our space and time operations by \(\eta =(\varDelta x, \varDelta t)\). We will consider a discrete space and time quantum walk governed byon \({\mathbb {X}}\), with \(H_\eta \) the above family of operators parametrized by \(\eta =(\varDelta x,\varDelta t)\). The continuous time limit of the walk in Eq. (10) exists if the right hand side of the equation has a limit (for \(\overrightarrow{\varPsi }\in {\mathbb {X}}\)) as \(\eta \rightarrow (0,0)\) along a given prescribed path, for which both the DTQW functions and continuum limit of the DTQW functions are in \({\mathbb {X}}\). Continuum space limits in the absence of any change in \(\varDelta t\) will not be considered here because \(S\rightarrow {\mathbb {I}}\) as \(\varDelta x \rightarrow 0\), so the walk reduces simply to a coin acting on the spin portion of the wave function at each time step. With no traversal of the lattice there results a trivial walk. Formally, we state the definition of continuous time limit and continuous limit as:

Our goal is to explore the most general possibilities for these two cases. We remark that our inclusion of n expands the number of continuum limits that exist; in particular this possibility was not considered in Ref. [20]

Additionally, we need the following definition to allow parametrized coin variations:

The following discussion is based on terminology and results explored in Ref. [20]. We will study a critical aspect of coins that change under the continuous time and spacetime limits; this, in turn, will help to interpret the theorems in Sects. 4 and 5. To obtain these results, we will follow the DTQW wave function through n time steps of length \(\varDelta t\). All limits in this section will be in the topology of the space \({\mathbb {X}}\). We begin with the basic equationwith \(S=S(\varDelta x)\) and \(C=C(\varDelta t)\) both dependent on the increment \(\eta = (\varDelta x, \varDelta t)\). If a continuous spacetime limit is taken with \((\varDelta t\), \(\varDelta x)\rightarrow (0,0)\), then due to \(S\rightarrow {\mathbb {I}}\) when \(\varDelta x\rightarrow 0\), we must haveas the limit could otherwise not exist. In particular, unless \(C(\varDelta t)\) is constantly the identity, it must vary (as in Definition 2) in the continuous time limit.

If only a continuous time limit is taken (i.e. \(\varDelta t\rightarrow 0\)), then (by continuity of the left side in t) for the left and right sides of Eq. (11) to be equal, we must havewhere we include \(\varDelta t\) dependence in C for generality. Note that the constraint in the continuous time limit involves both the coin and the shift operator, not just the coin as in the continuous spacetime limit. Now for the following definition:

By the previous definition and the above analysis of Eq. (11), we have the following theorem:

From this analysis, we have obtained a general property of coins which undergo continuum limit transformations, and we will refer to this property in the future.

In this section, we will identify the set of DTQWs for which a continuous time limit exists, as according to Definition 1. We will then analyze the properties of the resulting time evolutions in the continuous time limit.

We consider a general unitary coin, which can be written via:We wish to know for which \(2\times 2\) matrices, as parametrized by Eq. (14), does the continuum limit exist, according to Definition 1. Before introducing the relevant theorem we make a few remarks. First, a constraint on \(\delta \) is necessary to satisfy the finiteness condition for existence of the limit in Definition 1. The value of \(\delta \) is arbitrary as it amounts to an overall energy shift in the Hamiltonian, which does not change measureables. This point is explained further in the proof of Lemma 4. Second, assuming that the elements of C cannot depend on the elements of S, observe that the limit in Definition 1 cannot be finite unless C depends on \(\varDelta t\). Thus, we will assume that the coin varies in the process of the continuum limit; here we have defined such variation in Definition 2. A proof of the following theorem is presented in Appendix A.

Thus, the class of coins that admit continuous time limits have the form(here parameters are \(\psi _0\), \(\theta _1\), and \(\phi _0\)). We observe that the Hamiltonian obtained from the continuous time limit does not depend on any parameters that are coefficients in terms \(O(\varDelta t)\) except \(\theta _1\) [so they do not need to be included in Eq. (16)]. \(\theta _1\) can be interpreted as a driving factor for the final Hamiltonian’s time evolution. Its value completely determines how much of the mixing between the left and right states will be due to the evolution operator SC. Note that when \(\theta _1=0\) all operators in the coin commute with the shift operator and no mixing occurs, which corresponds to the wave function recurring every other step in the DTQW.

Now we compare our Hamiltonian from Theorem 2 to the massless Hamiltonian obtained in Ref. [11]. We begin by writing the Hamiltonian obtained from the continuous time limit in Ref. [11] (Eq. (4) in [11]) in a way we can easily compare to the Hamiltonian in Theorem 2:We see that \(\frac{c}{2}=\frac{\theta _1}{4}\), and that \(H_L\) is a special case of Eq. (15) with \(\phi _0=0\) and \(\psi _0=\pi \). It is the degrees of freedom possessed by the parameters \(\phi _0\) and \(\psi _0\) which cause our procedure to be more general.

We now make an additional observation on the need for skipping steps (i.e. for an even n) for a sensible limit to occur. An explicit proof justifying this can be seen in Appendix A; for a more intuitive explanation, note that for existence of a continuous DTQW time limit, the Fourier Hamiltonianmust be finite. The operator \(\mathrm{e}^{ik\varDelta x\sigma _z}C\) does not homotope to the identity as \(\varDelta t\rightarrow 0\) for any C, so no continuous time limit can exist for \(n=1\). However, for the coin in Eq. (16), the operator \(\mathrm{e}^{ik\varDelta x\sigma _z}C\mathrm{e}^{ik\varDelta x\sigma _z}C\) does homotope to the identity since for coins in Eq. (16) \(C\mathrm{e}^{ik\varDelta x\sigma _z}C=\mathrm{e}^{-ik\varDelta x\sigma _z}+O(\varDelta t)\). That is, the coins in Theorem 2 invert the shift operator up to \(O(\varDelta t)\), making the \(O(\varDelta t^0)\) term in SCSC the identity. After identities cancel in Eq. (18) only the \(O(\varDelta t)\) term remains, i.e., the Hamiltonian in the Theorem.

It should be noted that Ref. [7] derives a special version of the Hamiltonian in Theorem 2, using the coin \(C=\mathrm{e}^{-i\theta \sigma _x}\), and has \(\theta =\frac{\pi }{2}-\gamma \varDelta t\). The angle values parametrizing the general unitary coin in Theorem 2 for the particular choice in Ref. [7] including \(\varDelta t\) dependence have the form:with \(\gamma \) the jumping rate from vertex to vertex. If we do not have \(\delta =p\pi \) for odd integer p, we obtain a final H with constant infinite energy contributions, which should then be ignored, as only energy differences lead to observable quantities.

Another important property of the coins derived in Theorem 2 is that they themselves homotopically approach a root of unity in that, as can be checked, \(\lim _{\varDelta t\rightarrow 0}C^n={\mathbb {I}}\). This does not follow directly from our analysis in Sect. 3 of the continuous time limit, and a full characterization of all coins that admit continuous time limits was needed to obtain this property. Also, the limiting Hamiltonian in Theorem 2 will be used in Sect. 6 to determine how a continuous time limit followed by a continuous space limit compares to a simultaneous continuous spacetime limit.

We now analyze wave functions which that undergo the time evolution dictated by the Hamiltonian in Theorem 2. A proof of the following corollary is found in Appendix B.

This solution reduces to that found in Ref. [7] when the corresponding parameters in Eq. (19) are used, except for a sign difference stemming from the shift operator in Ref. [7] being defined as the inverse of S. The locations for which \(\overrightarrow{\varPsi }_L(x,0)\) is nonzero will contribute to \(\overrightarrow{\varPsi }_L(m\varDelta x,t)\) if they are an even number of steps away from m, and the nonzero locations of \(\overrightarrow{\varPsi }_R(x,0)\) will contribute to \(\overrightarrow{\varPsi }_L(m\varDelta x,t)\) if they are an odd number of steps away from m, and the opposite scenario is true for \(\overrightarrow{\varPsi }_R(m\varDelta x,t)\). For a full description of the effects \(\alpha \) and \(\beta \) have on the probability distribution, see Sect. 7.

In this section we will demonstrate for which DTQWs the continuous spacetime limit exists and what the ensuing time evolution is if there is no coin variation involved, as defined in Definition 2. We present a theorem to illustrate that it is possible to obtain a continuous spacetime limit of a DTQW with non-varying coin, and to identify the necessary properties of coins which can undergo this type of limit. A proof of the following theorem is presented in Appendix C.

The massless Dirac Hamiltonian is the limiting Hamiltonian of this continuum limit. In the continuous spacetime limit, the mass term is generated by the coin’s variation with time step, as can be seen in Appendix F. The ensuing continuous spacetime Hamiltonian will have no mass because the coin in Theorem 3 does not vary in the continuum limit.

The above theorem also states that a coin with no variation will have a continuum limit if it is a root of unity. This is expected in light of Theorem 1, as the continuous parameter in the coin is no longer present, so the coin itself must be a root of unity. This theorem may seem at odds with the discussion at the start of Ref. [20] (which we repeat in Sect. 3), but skipping steps in the walk was not considered when taking the continuum limit, which is how a limit was obtained for this walk, even when the coin did not vary in the continuum limit.

In this section we state a theorem on the existence of non-trivial continuous space limits of the continuous time limit of the DTQW. We begin with the theorem (proof in Appendix D):

The reason why \(\phi _0\) and \(\psi _0\) cannot depend on \(\varDelta x\) is given by the following conjecture:

If no spatial derivatives are present, no spatial translation will occur for the wave function in the continuous space limit, resulting in a trivial stationary walk. Another observation of Theorem 4 is that a different time evolution equation occurs when a simultaneous continuous spacetime limit is taken. As can be seen in Appendix F, when a simultaneous spacetime continuum limit is taken, a massive Dirac equation results.

In the following section, we will build on Strauch’s result from Ref. [7], in which a connection was found between the DTQW and CTQW by taking a continuous time limit of the DTQW. Strauch used a specific coin \(\mathrm{e}^{-i\theta \sigma _x}\), and let \(\theta =\frac{\pi }{2}-\gamma \varDelta t\) when the continuous time limit was taken. Now that a general parametrization of all the possible coins which can undergo a continuous time quantum walk has been obtained from Theorem 2, we will investigate whether or not a relationship between the CTQW and DTQW exists for a general coin. We begin by reviewing Strauch’s specific results in Ref. [7].