Quantum walk

Consider the dynamics of a non-relativistic, spin-less free quantum particle with mass ${\displaystyle m}$ propagating on an infinite one-dimensional spatial domain. The particle's motion is completely described by its wave function ${\displaystyle \psi$ :\mathbb {R} \times \mathbb {R} _{\geq 0}\to \mathbb {C} } which satisfies the one-dimensional, free particle Schrödinger equation

${\displaystyle {\textbf {i}}\hbar {\frac {\partial \psi }{\partial t}}=-{\frac {\hbar ^{2}}{2m}}{\frac {\partial ^{2}\psi }{\partial x^{2}}}}$

where ${\displaystyle {\textbf {i}}={\sqrt {-1}}}$ and ${\displaystyle \hbar }$ is the reduced Planck's constant. Now suppose that only the spatial part of the domain is discretized, ${\displaystyle \mathbb {R} }$ being replaced with ${\displaystyle \mathbb {Z} _{\Delta x}\equiv \{\ldots ,-2\,\Delta x,-\Delta x,0,\Delta x,2\,\Delta x,\ldots \}}$ where ${\displaystyle \Delta x}$ is the separation between the spatial sites the particle can occupy. The wave function becomes the map ${\displaystyle \psi$ :\mathbb {Z} _{\Delta x}\times \mathbb {R} _{\geq 0}\to \mathbb {C} } and the second spatial partial derivative becomes the discrete laplacian

${\displaystyle {\frac {\partial ^{2}\psi }{\partial x^{2}}}\to {\frac {L_{\mathbb {Z} }\psi (j\,\Delta x,t)}{\Delta x^{2}}}\equiv {\frac {\psi \left((j+1)\,\Delta x,t\right)-2\psi \left(j\,\Delta x,t\right)+\psi \left((j-1)\,\Delta x,t\right)}{\Delta x^{2}}}}$

The evolution equation for a continuous time quantum walk on ${\displaystyle \mathbb {Z} _{\Delta x}}$ is thus

${\displaystyle {\textbf {i}}{\frac {\partial \psi }{\partial t}}=-\omega _{\Delta x}L_{\mathbb {Z} }\psi }$

where ${\displaystyle \omega _{\Delta x}\equiv \hbar /2m\,\Delta x^{2}}$is a characteristic frequency. This construction naturally generalizes to the case that the discretized spatial domain is an arbitrary graph ${\displaystyle G=(V,E)}$ and the discrete laplacian ${\displaystyle L_{\mathbb {Z} }}$is replaced by the graph Laplacian ${\displaystyle L_{G}\equiv D_{G}-A_{G}}$where ${\displaystyle D_{G}}$ and ${\displaystyle A_{G}}$ are the degree matrix and the adjacency matrix, respectively. Common choices of graphs that show up in the study of continuous time quantum walks are the d-dimensional lattices ${\displaystyle \mathbb {Z} ^{d}}$, cycle graphs ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$, d-dimensional discrete tori ${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{d}}$, the d-dimensional hypercube ${\displaystyle \mathbb {Q} ^{d}}$and random graphs.

Probability distribution resulting from one-dimensional discrete time random walks. The quantum walk created using the Hadamard coin is plotted (red) vs a classical walk (blue) after 50 time steps.

The evolution of a quantum walk in discrete time is specified by the product of two unitary operators: (1) a "coin flip" operator and (2) a conditional shift operator, which are applied repeatedly. The following example is instructive here.[7] Imagine a particle with a spin-1/2-degree of freedom propagating on a linear array of discrete sites. If the number of such sites is countably infinite, we identify the state space with ${\displaystyle \mathbb {Z} }$. The particle's state can then be described by a product state

${\displaystyle |\Psi \rangle =|s\rangle \otimes |\psi \rangle }$

consisting of an internal spin state

${\displaystyle |s\rangle \in {\mathcal {H}}_{C}=\left\{a_{\uparrow }|{\uparrow }\rangle +a_{\downarrow }|{\downarrow }\rangle :a_{\uparrow /\downarrow }\in \mathbb {C} \right\}}$

and a position state

${\displaystyle |\psi \rangle \in {\mathcal {H}}_{P}=\left\{\sum _{x\in \mathbb {Z} }\alpha _{x}|x\rangle$ :\sum _{x\in \mathbb {Z} }|\alpha _{x}|^{2}<\infty \right\}}

where ${\displaystyle {\mathcal {H}}_{C}=\mathbb {C} ^{2}}$ is the "coin space" and ${\displaystyle {\mathcal {H}}_{P}=\ell ^{2}(\mathbb {Z} )}$ is the space of physical quantum position states. The product ${\displaystyle \otimes }$ in this setting is the Kronecker (tensor) product. The conditional shift operator for the quantum walk on the line is given by

${\displaystyle S=|{\uparrow }\rangle \langle {\uparrow }|\otimes \sum \limits _{i}|i+1\rangle \langle i|+|{\downarrow }\rangle \langle {\downarrow }|\otimes \sum \limits _{i}|i-1\rangle \langle i|,}$

i.e. the particle jumps right if it has spin up and left if it has spin down. Explicitly, the conditional shift operator acts on product states according to

${\displaystyle S(|{\uparrow }\rangle \otimes |i\rangle )=|{\uparrow }\rangle \otimes |i+1\rangle }$

${\displaystyle S(|{\downarrow }\rangle \otimes |i\rangle )=|{\downarrow }\rangle \otimes |i-1\rangle }$

If we first rotate the spin with some unitary transformation ${\displaystyle C:{\mathcal {H}}_{C}\to {\mathcal {H}}_{C}}$ and then apply ${\displaystyle S}$, we get a non-trivial quantum motion on ${\displaystyle \mathbb {Z} }$. A popular choice for such a transformation is the Hadamard gate ${\displaystyle C=H}$, which, with respect to the standard z-component spin basis, has matrix representation

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&\;\;1\\1&-1\end{pmatrix}}}$

When this choice is made for the coin flip operator, the operator itself is called the "Hadamard coin" and the resulting quantum walk is called the "Hadamard walk". If the walker is initialized at the origin and in the spin-up state, a single time step of the Hadamard walk on ${\displaystyle \mathbb {Z} }$ is

${\displaystyle |{\uparrow }\rangle \otimes |0\rangle \;\,{\overset {H}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle +|{\downarrow }\rangle )\otimes |0\rangle \;\,{\overset {S}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle \otimes |1\rangle +|{\downarrow }\rangle \otimes |{-1}\rangle ).}$

Measurement of the system's state at this point would reveal an up spin at position 1 or a down spin at position −1, both with probability 1/2. Repeating the procedure would correspond to a classical simple random walk on ${\displaystyle \mathbb {Z} }$. In order to observe non-classical motion, no measurement is performed on the state at this point (and therefore do not force a collapse of the wave function). Instead, repeat the procedure of rotating the spin with the coin flip operator and conditionally jumping with ${\displaystyle S}$. This way, quantum correlations are preserved and different position states can interfere with one another. This gives a drastically different probability distribution than the classical random walk (Gaussian distribution) as seen in the figure to the right. Spatially one sees that the distribution is not symmetric: even though the Hadamard coin gives both up and down spin with equal probability, the distribution tends to drift to the right when the initial spin is ${\displaystyle |{\uparrow }\rangle }$. This asymmetry is entirely due to the fact that the Hadamard coin treats the ${\displaystyle |{\uparrow }\rangle }$ and ${\displaystyle |{\downarrow }\rangle }$ state asymmetrically. A symmetric probability distribution arises if the initial state is chosen to be

${\displaystyle |\Psi _{0}^{\text{symm}}\rangle ={\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle -{\textbf {i}}|{\downarrow }\rangle )\otimes |0\rangle }$