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 \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 x at time t 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 T means the transposed operator.

If we assume that the unitary matrix U 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.



Time evolution


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

\[  i\frac{d\Psi_t(x)}{dt}=-\nu\left\{\Psi_t(x-1)-2\Psi_t(x)+\Psi_t(x+1)\right\},\]

where i=\sqrt{-1}, and \nu is a positive constant.


Probability distribution


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

\[ \mathbb{P}(X_t=x)= |\Psi_t(x)|^2.\]


  • Example


Limit theorem


We take the initial conditions

\[  \psi_0(x)=\left\{\begin{array}{ll}		     1&(x=0),\\			    0&(x\neq 0).			   \end{array}\right.\]

Then we have

\[  \lim_{t\rightarrow\infty}\mathbb{P}\left(\frac{X_t}{t}\leq x\right)=\int_{-\infty}^x f(y) \,I_{(-2\nu,2\nu)}(y)\,dy,\]

where

\[ f(x)=\frac{1}{\pi\sqrt{(2\nu)^2-x^2}},\]

and

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



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.

External link