﻿Ito’s Formula for the Discrete-Time Quantum Walk in Two Dimensions

Journal of Quantum Information Science
Vol.2 No.2(2012), Article ID:20144,7 pages DOI:10.4236/jqis.2012.22008

Ito’s Formula for the Discrete-Time Quantum Walk in Two Dimensions

Received December 24, 2011; revised April 23, 2012; accepted May 12, 2012

Keywords: Quantum Random Walk; Ito’s Formula; Brownian Motion

ABSTRACT

Following Konno [1], it is natural to ask: What is the Ito’s formula for the discrete time quantum walk on a graph different than Z, the set of integers? In this paper we answer the question for the discrete time quantum walk on Z2, the square lattice.

1. Introduction

Ito’s formula which is related to the Ito’s lemma is used in stochastic calculus to find the differential of a function of a particular type of stochastic process, and has a wide range of applications. According to the author in [1], the Ito’s formula for the random walk has been investigated [2,3]. However, in the quantum walk case, the Ito’s formulas are unknown. In [1] the author presents the Ito formula for the one-dimensional discrete-time quantum walk and gives some examples including Tanaka’s formula by using the formula. Integrals for the quantum walk are also discussed.

In the present paper new results on the Ito’s formula for the discrete-time quantum walk on the square lattice is given. This paper is organized as follows. In Section 2 we define the quantum walk on the square lattice, there the dynamics of the walk in the Fourier picture is recorded in Lemma 1. In Section 3 we present an Ito’s formula for the discrete-time quantum walk on the square lattice as well as a Tanaka-type formula for the quantum walk. In [4] the author of the present paper computed some sojourn times of the Grover walk in two dimensions. The Tanaka-type formula may be useful in computing local time at the origin. Section 4 is devoted to the conclusions, there two types of problems for further exploration is discussed. The first concerns integrals for the quantum walk whilst the second concerns another relation on the Ito’s formula for the discrete-time quantum walk on the square lattice.

2. Definitions

Recall that the discrete-time quantum walk is the quantum analogue of the classical random walk with an additional degree of freedom call chirality. In the two-dimensional setting on the square lattice, the chirality takes values left, right, downward, and upward, and means the direction of motion of the walker. At each time step, the particle moves according to its chirality state. For example, if the chirality state is upward, then the particle moves one step up. Let us define

, , , andwhere L, R, D, U refer to the left, right, down, and up chirality states respectively. The time evolution of the quantum walk on Z2 is determined by, where, with a, b, c, d Î C, where C is the set of complex numbers. The unitarity of U gives , , , , where denotes complex conjugation, and = with. We should remark that is a 4 × 4 matrix which is also unitary. In order to define the dynamics of the model we write

, where

,

,

.

We should note that represents the walker moves to the left, right, downward, and upward directions respectively at position at each time step. Let the set of initial quibit states at the origin for the quantum walk be given by

.

Let denote the sum of all paths starting from the origin in the trajectory consisting of l steps left, r steps right, d steps downwards, and u steps upwards. For time, and position, , we have

where the summation is taken over all integers satisfying, , , , and. We should note that the definition implies we can write

.

The probability that the quantum walker is in position at time n starting from the origin with is defined by, where, , and. The probability amplitude at position at time n is given by

.

So,. From now on we consider the Fourier transform of. By definition

.

The Fourier transform of, that is, is given by , from which it follows that

.

Put

then and . From

for, we obtain the following Lemma 1: For any

.

Here is given by

Note that

where. In terms of it follows by induction on n from Lemma 1 that. Note that

where * means the adjoint operator. Write

then,

Since is a power of n, in order to calculate it is usual practice to diagonalize the matrix. We should note that is also a power of n by the adjoint operation.

3. Ito-Type Formulas for the Discrete-Time Quantum Walk on the Square Lattice

Let

,

,

, ,

,

,

,

,

where indicates the indicator function for a set A. Note that . From now on we consider the quantum walk on. To do so let, , , and noting that

as well as, a direct computation gives the following.

Proposition 2: Let. For any and we have

(a)

(b)

Proof: (b) can easily been seen by summing the expressions in (a) from 0 to, with respect to the indices m and m’ to get the first and second expressions respectively. In particular, it is easy to see that the righthand side of the expressions in (b) have been left in terms of the sigma notation, where the sum over the appropriate indices run from 0 to. After summing the expressions in (a) from 0 to, with respect to the indices m and m’, the left hand side becomes a telescoping sum, that is, the sum collapses to just two terms as can been seen in the left hand side of the expressions in (b). To see the expressions in a), for example the first one, let, then after some algebra we get

however we have let

so

thus we have

and the proof is finished.

We should remark that the expressions in part (A) of Proposition 2 is the Ito formulas for the discrete-time quantum walk on the square lattice.

Put

and

and let

where

, and is defined in a similar way, then from Proposition 2 we immediately obtain the following.

Theorem 3: Let. For any and we have(a)

(b)

We should remark that when we consider

, ,

, andwith, where p, q, r, s corresponds to the probabilities of the walker moving left, right, down, and up in a random walk, then Theorem 3 is the corresponding result for the random walk on the square lattice which is not symmetric. If, then the results corresponds to the simple symmetric random walk on the square lattice.

Next we present a Tanaka-type formula for the dis-crete-time quantum walk on the square lattice.

From first expression in part (A) of Theorem 3, we put

,

for any k,

where denotes the sign function,

.

Making a similar substitution in the second expression in part (A) of Theorem 3, we get the Tanaka-type formula for the discrete-time quantum walk on the square lattice as follows.

Corollary 4:

(a)

(b)

Recall to compute it is necessary to diagonalize since it is a power of n in the expression for. Next we give a formula that slightly expands making use of Theorem 3.

Let

and for any k, k’, and n’, then the LHS of the first expression in part (b) of Theorem 3 becomes

.

As for the RHS of the first expression in part (b) of Theorem 3, we can write the first term as

Similarly, we can show that the second term on the RHS of the first expression in part (b) of Theorem 3, can be written as

So the RHS of the first expression in part (b) of Theorem 3 becomes

Now equating the expression immediately above to, we get

Repeating the argument immediately above to the LHS and RHS of the second expression in part (b) of Theorem 3, we also get

So from the expressions immediately above we have the following.

Corollary 5:

4. Concluding Remarks

In this paper we have shown the Ito’s formula for the discrete-time quantum walk on the square lattice and as a consequence obtained a Tanaka-type formula for the quantum walk. The relation to the simple random walk on the square lattice has also been clarified in the biased and unbiased case. Following the author in [1] it is an interesting problem to clarify the relation between

and. If f is a function of two variables,. It is well known that, exploiting this relation another Ito formula for the discrete-time quantum walk on the square lattice is the following. We record as a conjecture, therefore one of the future interesting problems is to verify or refute the following.

Conjecture 6:

Let. For any and, we have

REFERENCES

1. N. Konno, “A Note on Ito’s Formula for Discrete-Time Quantum Walk,” Cornell University Library, New York, 2011.
2. T. Fujita, “Stochastic Calculus for Finance (in Japanese),” Kodansha, Tokyo, 2002.
3. T. Fujita, “Random Walks and Stochastic Calculus (in Japanese),” Nippon-Hyoron-sha Co. Ltd., Tokyo, 2008.
4. C. Ampadu, “Sojourn Times for the One Dimensional Grover Walk,” Cornell University Library, New York, 2011.