# Quantum walk

Quantum walks are considered to be quantum analogs of random walks. The study of quantum walks started to get attention around 2000 in relation to a quantum computer.

**Contents**

### Discrete-time quantum walk on the line ｏ

#### Probability amplitude ｏ

The whole system of a discrete-time 2-state quantum walk on the line is described by probability amplitudes. The probability amplitude at position at time is expressed as a 2-component complex vector , as shown in the following figure.

#### Time evolution ｏ

Assuming is a unitary matrix, the time evolution is determined by a reccurence

where

and are complex numbers.

#### Probability disribution ｏ

The probability that the walker can be observed at position at time is defined by

where is a random variable and denotes the position of the quantum walker.

**Example**

**Quantum walk v.s. Random walk**

#### Limit theorem ｏ

For complex numbers , we take initial conditions to be

under the condition . The symbol means the transposed operator.

If we assume that the unitary matrix satisfies the condition , then we have

where

and

**Example**

In the case of a simple random walk, we have

where

### Continuous-time quantum walk on the line ｏ

#### Probability amplitude ｏ

The whole system of a continuous-time quantum walk on the line is also described by probability amplitudes. The probability amplitude at position at time is expressed as a complex number , as shown in the following figure.

#### Time evolution ｏ

The time evolution is defined by a discrete-space Schrödinger equation,

where , and is a positive constant.

#### Probability distribution ｏ

The quantum walker can be observed at position at time with probability

**Example**

#### Limit theorem ｏ

We take the initial conditions

Then we have

where

and

**Example**

### Interesting probability distributions of quantum walks ｏ

QIC, 15(13&14), 1248-1258 (2015)

QIC, 10(11&12), 1004-1017 (2010)

IWNC 2009 Proc. ICT, 2, 226-235 (2010)

### See also ｏ

#### Further reading ｏ

- Julia Kempe (2003). Quantum random walks – an introductory overview. Contemporary Physics
**44**(4): 307–327. DOI:10.1080/00107151031000110776. - Viv Kendon (2007). Decoherence in quantum walks – a review. Mathematical Structures in Computer Science
**17**(6): 1169–1220. DOI:10.1017/S0960129507006354. - Norio Konno (2008). Quantum Walks. Volume 1954 of Lecture Notes in Mathematics. Springer-Verlag, (Heidelberg) pp. 309–452. DOI:10.1007/978-3-540-69365-9.
- Salvador Elías Venegas-Andraca (2008). Quantum Walks for Computer Scientists. Morgan & Claypool Publishers. DOI:10.2200/S00144ED1V01Y200808QMC001.
- Salvador Elías Venegas-Andraca (2012). Quantum walks: a comprehensive review. Quantum Information Processing
**11**(5): 1015–1106. DOI:10.1007/s11128-012-0432-5.