_{1}

^{*}

We review (not exhaustively) the quantum random walk on the line in various settings, and propose some questions that we believe have not been tackled in the literature. In a sense, this article invites the readers (beginner, intermediate, or advanced), to explore the beautiful area of quantum random walks.

The author would first like to thank Scientific Research Publishing with the invitation to contribute to the special issue on “Stochastic Processes”. I also acknowledge all active researchers in “Quantum Wonderland”.

The quantum walk (QW) is regarded as the quantum analogue of the random walk (RW). In the RW, a particle is located at one of a set of definite positions (such as the set of integers on the line). In response to a random event―for example, the flipping of a coin―the particle moves either left or right. This process is iterated, and the motion of the particle is analyzed statistically. These systems provide good models for diffusion and other stochastic processes. The QW is studied in various contexts and settings. The main difference between the RW and the QW can be simply stated in terms of the dynamics on

In these notes we have touched on some major topics on the QW that has been the subject of extensive research by many authors from the experimental and theoretical point of view. It is my hope that the reader at any level interested in research on the QW, will take this opportunity to read these notes, and explore some of the questions we have proposed here, as an initiation into “Quantum Wonderland”.

A good working knowledge of probability, statistics, linear algebra, and analysis, is a prerequisite necessary to commence research on the QW. Aside, motivation, passion, mathematical maturity, and the ability to think in abstract and applied terms, are also key ingredients to becoming a successful researcher in this area.

Apart from the books mentioned in these notes, the following books make it possible for the reader with a good working knowledge of probability, statistics, linear algebra, and analysis, to start reading the research papers on QW in the literature:

・ Nielsen and Chuang, Quantum Information and Quantum Computation, Cambridge University Press (2011).

・ Portugal, Quantum Walks and Search Algorithms, Springer (2013).

・ Wang and Manouchehri, Physical Implementation of Quantum Walks, Springer (2013).

・ McMahon, Quantum Computing Explained, Wiley-IEEE Computer Society Pr (2007).

The quantum walk [

The discrete-time quantum walk with spatially or temporally random defects as a consequence of interactions with random environments is known as the disordered quantum walk. In this paper we review the disordered quantum walk as defined by N. Konno [

When the quantum walk is position dependent it is said to be inhomogeneous. The inhomogeneous quantum walk is studied in various settings, especially in the applications. In [

In [

walks can be bounded or unbounded. The coin flip used in [

[

As far as we can tell the quantum walk on the line with phase parameters was initiated by Villagra et al. [

Recently Mc. Gettrick [

As is well known the physical implementation of the quantum walk faces many obstacles including environmental noise and imperfections collectively known as decoherence. The decoherence in the quantum walk is intensely investigated in the literature in various settings and contexts, and the overarching goal is to study possible routes to classical behavior. In [

Some introductory studies on the decoherent quantum walk can be found in [

As the author of the present paper pointed out in [

In this paper we follow the convention of obtaining the limit of the decoherent quantum walk by analyzing the characteristic function, following discussion of the result of Fan et al. [

Related to decoherence is the notion of entanglement. The (asymptotic) entanglement in quantum walks is intensely investigated in the literature in various context, see [

where

sition degrees of freedom. We should remark that studies involving this measure of entanglement have focused mainly where

In the general setting the time-evolution of the one-dimensional quantum walk is given by the following unitary

matrix

tion, and

location

where

We should remark that

where

Theorem 1 (Konno Density Function): Consider the one-dimensional quantum walk

If

Remark 2: We are referring to the probability distribution in Theorem 1, in the sense of weak limit theorem.

The weak limit theorems for quantum random walks have a storied history. In fact going back to Grimmett, Janson, and Scudo [

one or more dimension. In particular, let

weakly as

Theorem 3: If

Proof/Sketch of Proof: Let

then

where

Combining the expressions for

Let

Let

The authors further extend Theorem 3 to arbitrary dimension

Theorem 4: For the

where

The papers [

The weak limit theorem can also be written in terms of the density matrices at position

Theorem 5: For

where,

and

Remark 6: We should note a version of Theorem 5 for the interference terms have been given in [

Consider the time evolution of the quantum walk governed by the following infinite random unitary matrices

Let

and

Moreover, we assume that

scribed by the above process with the additional requirement that

Let

The state of the walk

where

and

For the analysis of the walk on line we consider the projection at time

where

right respectively. The probability of being at position

evolution of the walk is given by

Let

Let

then

with the following effect on

where

and

In the general setting, the time evolution of the walk is determined by a sequence of

with

and

It should be noted that

Here we will discuss two approaches, the first by Fan et al. [

Consider the quantum random walk on the general square lattice

and

where

where

Let

The eigenvectors

with eigenvalue

Therefore in the

where

We should remark that

Let

defined as follows, before each unitary transformation acting on the coin, a measurement given by the unital operators is performed on the coin, after which a density operator

The general density operator of the quantum random walk is given by

where

and

Suppose the quantum walk starts in

After

where

for every

Let

where we have used the following property of the dirac delta function

Let

where

We should remark that the proof is similar to Lemma 3.1 in Fan et al. [

Lemma 1: Suppose

We should remark from Lemma 1 that

where

elements. In column form let us write

Let

where

only the first row action

the following lemma whose proof is similar to Lemma 3.2 in Fan et al. [

We should remark that the proof of Lemma 3.2 in Fan et al. [

Lemma 2: Suppose

Let us define the probability mass function on

The limit theorem for the decoherent two-dimensional quantum walk is given by the following:

CLAIM:

Proof of Claim: [C. Ampadu, Quantum Inf Process (2012) 11: 1921-1929]

Consider the special unitary matrix

that

the density matrices at position

tion between the interference terms and the moments of

Lemma 1: For

where

Proof: [T. Machida, Quantum Information and Computation, Vol.13 No.7 & 8, pp. 661-671 (2013)].

On the other hand, if we assume that the 2-state quantum walk, starts from the origin with the initial state given by

Theorem 2: For

where

where

Proof: [T. Machida, Quantum Information and Computation, Vol. 13 No. 7&8, pp. 661-671 (2013)].

In this section we define the 4-state quantum walk (4QW) without memory. The state space of the 4-state quantum walk is composed of the following vectors:

states we put

where

The one-step time evolution operator is given by

where the nonzero entries of

Recalling that

and

then the evolution of the QW is determined by

The probability that the quantum walker

where

By the inverse Fourier transform we have

The time evolution of

where

The standard argument by induction on the time step gives

Consider the quantum walk on the

It is an open problem to obtain the limit theorems for the quantum walk for a general

Consider the following question: “If, say, a quantum walker which could be a quantum particle exists only at one site initially in some media, perhaps with disorder, will the quantum walker remain trapped with high probability near the initial position?” This phenomenon of the quantum walker is termed Localization.

1) Consider the disordered quantum walk as described in this paper, and evolution in the Fourier picture,

where

and

It can be shown that none of the eigenvalues are independent of

2) What is the localization criterion for a general

Example (Five-State Quantum Walk): The Hadamard walk as is well known plays a key role in the studies of the quantum walks, thus the generalization of the Hadamard walk is one of the many fascinating challenges. The simplest and well studied example of the Hadamard walk is given by the following unitary matrix

The five-state quantum walk is a kind of generalized Hadamard walk in the plane, and differs markedly from the previous studies. The particle ruled by the 5QW is characterized in the Hilbert space which is defined by a direct product of a chirality-state space

Let

be the amplitude of the wave function of the particle corresponding to the chiralities

where

Note that if the matrix, say

One finds clearly that the chiralities

In the Fourier domain, the dynamics of the wave function is defined by

The standard argument by induction on the time step allows us to write the evolution as

It can be shown that the strongly degenerate eigenvalue of 1, associated with this model, is a necessary condition for localization, see [

1) Consider discussion of the asymptotic behavior of the quantum walker subject to decoherence in the two dimensional setting [

2) Consider discussion of the asymptotic behavior of the quantum walker subject to entanglement in the sense of Machida [

1) The Grover operator as is well known was first introduced by Moore and Russell in their study of quantum walks on the hypercube [

where

and

In general given an undirected graph, let

If

quantum walk with phase parameters in this paper, it is an open question what is the limiting distribution of

2) In a paper of Venegas-Andraca [

Motivated Example (2cQW): Let the Hilbert space of the entangled coin subspace of the 2cQW be given by

We should remark the labeling

particle at time

be the amplitude of the wave function, where

correspond to the chirality states right, stall right, stall left, and left respectively. Define

where

be the initial state of the system in the Fourier picture, then the evolution of the 2cQW is given by

where

Now consider the “2cQW” where the unitary matrix governing the walk is given by

Consider the discrete-time nearest-neighbor quantum walk in a random environment (QWRE) on the line, whose evolution proceeds almost everywhere as in the case of the inhomogeneous quantum walk. The definition of the QWRE can be made more precise as follows: Let

where

that is, let

and thus

both the quenched and annealed QWRE for the Grover-type operator

Consider the discussion of the inhomogeneous quantum walk in this paper. Suppose

For

We clearly see

It is an open question what is the limiting distribution of the inhomogeneous walk

it is interesting to have an asymptotic probability function that captures this phenomenon. The result will be significant for quantum information processing task.

Clement Ampadu, (2014) On Some Questions of C. Ampadu Associated with the Quantum Random Walk. Applied Mathematics,05,3040-3066. doi: 10.4236/am.2014.519291