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
Continuous-time quantum walk on the line
Interesting probability distributions of quantum walks
See also
- Further reading
- External link

Discrete-time quantum walk on the line †

↑

Probability amplitude †

The whole system of a discrete-time 2-state quantum walk on the line $\mathbb{Z}=\left\{0,\pm 1,\pm 2,\ldots\right\}$ is described by probability amplitudes. The probability amplitude at position $x\in\mathbb{Z}$ at time $t\in\left\{0,1,2,\ldots\right\}$ is expressed as a 2-component complex vector $\psi_t(x)$ , as shown in the following figure.

↑

Time evolution †

Assuming P+Q=U is a $2\times 2$ unitary matrix, the time evolution is determined by a reccurence

$\psi_{t+1}(x)=P\psi_t(x+1)+Q\psi_t(x-1),$

where

$P=\left[\begin{array}{cc} a&b\\0&0 \end{array}\right],\, Q=\left[\begin{array}{cc} 0&0\\c&d \end{array}\right],$

and a,b,c,d are complex numbers.

↑

Probability disribution †

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

$\mathbb{P}(X_t=x)= ||\psi_t(x)||^2,$

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

Example

Suppliment PDF file

Quantum walk v.s. Random walk

↑

Limit theorem †

For complex numbers $\alpha,\beta$ , we take initial conditions to be

$\psi_0(x)=\left\{\begin{array}{ll} {}^T[\alpha,\beta]&(x=0),\\ {}^T[0,0]&(x\neq 0), \end{array}\right.$

under the condition $|\alpha|^2+|\beta|^2=1$ . The symbol means the transposed operator.

If we assume that the unitary matrix satisfies the condition $abcd\neq 0$ , then we have

$\lim_{t\to\infty} \mathbb{P}\left(\frac{X_t}{t} \leq x\right)=\int_{-\infty}^{x} f(y)\,I_{(-|a|,|a|)}(y)\,dy,$

where

$f(x)=\frac{\sqrt{1-|a|^2}}{\pi(1-x^2)\sqrt{|a|^2-x^2}}\left\{1-\left(|\alpha|^2-|\beta|^2+\frac{a\alpha\overline{b\beta}+\overline{a\alpha}b\beta}{|a|^2}\right)x\right\},$

and

$I_{A}(x)=\left\{\begin{array}{cl} 1&(x\in A), \\ 0& (x\notin A). \end{array}\right.$

Example

In the case of a simple random walk, we have

$\lim_{t\to\infty} \mathbb{P}\left(\frac{X_t}{\sqrt{t}} \leq x\right)=\int_{-\infty}^{x} f(y)\,dy,$

where

$f(x)=\frac{1}{\sqrt{2\pi}}\,e^{-x^2/2}.$

↑

Continuous-time quantum walk on the line †

↑

Probability amplitude †

The whole system of a continuous-time quantum walk on the line $\mathbb{Z}$ is also described by probability amplitudes. The probability amplitude at position $x\in\mathbb{Z}$ at time $t\,\geq 0$ is expressed as a complex number $\Psi_t(x)$ , as shown in the following figure.