$\def\conf{\mathtt{conf}} \def\cov{\mathtt{cov}} \def\Int{\mathbb{Z}} \def\Real{\Bbb{R}} \def\Comp{\mathbb{C}} \def\ZN{\Int_N} \def\attr{{\mathcal{A}}} \def\U{{\mathcal U}} \def\Ed{{\mathcal E}} \def\Rd{{\Real}^d} \def\cN{{\mathbf N}} \def\OO{{\mathcal O}} \def\DD{{\mathcal D}} \def\HH{{\mathcal H}} \def\NN{{\mathcal N}} \def\VV{{\mathcal V}} \def\domain{{\mathcal{B}}} \def\ii{{\mathbf i}} \def\T{{\mathbb T}} \def\torus{\mathbb{T}} \def\S{{\mathbb S}} \def\mod{{\mathit mod}} \def\Cycle{{\mathbf \sigma}} \def\prob{{\mathbb P}} \def\ex{{\mathbb E}} \def\codim{{\mathit{codim}}} \def\paths{{\mathcal P}} \def\sens{{\mathcal S}} \def\measurements{{\mathcal E}} \def\indep{{\mathcal I}} \def\one{\mathbb{I}} \def\dim{\mathtt{dim}} \def\nset{\mathbf{n}} \def\mset{\mathbf{m}} \def\Nat{\mathbb{N}} \def\types{\mathfrak{F}} \def\ideal{\mathcal{I}} \def\bz{\bar{z}} \def\bn{\bar{n}} \def\arrange{\mathcal{A}} \def\fld{\Bbbk} \def\attr{\mathfrak{A}} \def\Int{\mathbb{Z}} \def\Real{\mathbb{R}} \def\Comp{\mathbb{C}} \def\ZN{\Int_N} \def\one{{\mathbf 1}} \def\amoeba{\mathcal{A}} \def\Ed{{\mathcal E}} \def\Rd{{\Real}^d} \def\cN{{\mathbf N}} \def\OO{{\mathcal O}} \def\DD{{\mathcal D}} \def\HH{{\mathcal H}} \def\NN{{\mathcal N}} \def\VV{{\mathcal V}} \def\ii{{\mathbf i}} \def\T{{\mathbb T}} \def\mod{{\mathit mod}} \def\Cycle{{\mathbf \sigma}} \def\LL{\mathtt{Log}} %%%%%%%%%%%%%%%%YMB \def\Int{\mathbb{Z}} \def\Nat{\mathbb{N}} \def\Comp{\mathbb{C}} \def\Real{\mathbb{R}} \def\para{\mathbf{M}} \def\lmaps{\mathtt{Lin}} \def\kg{\kappa} \def\ig{\rho} \def\ker{\mathtt{Ker}} \def\ima{\mathtt{Im}} \def\grass{\mathtt{Gr}} \def\obs{\mathcal{O}} \def\Proj{\mathbb{P}} \def\circle{\mathtt{S}^1} \def\bx{\mathbf{x}} \def\br{\mathbf{r}} \def\tr{\mathtt{tr}} %%%%%%%%%%%%%%%%%%QRW \def\basis{\mathcal{B}} \def\hilb{\he_L} \def\he{\mathcal{H}} \def\coin{\mathbf{U}} \def\bk{\mathbf{k}} \def\bl{\mathbf{l}} \def\bz{\mathbf{z}} \def\bp{\mathbf{p}} \def\bj{\mathbf{j}} \def\qstep{\mathbf{S}} \def\b0{\mathbf{0}} \def\torus{\mathbb{T}} \def\torL{\torus_L} \def\ch{\mathbf{P}} \def\bigt{{\mathbb{T}}^\sharp_L} \def\spectral{\Sigma} \def\proje{\mathbf{\rho}} \def\lebesg{\lambda} \def\gauss{{\mathtt{G}}} \def\limmes{\mathbf{\lambda}} \def\simplex{\bm{\Delta}} \def\Un{\bm{U}(n)} \def\torusU{\bm{K}} \def\jt{\mathbf{j}} \def\tvect{\theta} $

random quantum random walks

yuliy baryshnikov

UIUC, mathematics and ECE


Quantum random walks in discrete time describe an evolution of a single particle under a caricature of Dirac equation.

Introduced in early '90ies (by Aharonov, Davidovich, Zagury) Quantum Random Walks drew a lot of attention in the 2000's (see surveys by Kempe '03, Konno'08).

We deal here with the Quantum Random Walks in discrete time on a lattice $L\cong\Int^d$.

To define a quantum random walk one needs the following data:

  • a lattice $L$of rank $d$;

  • a spin space: an $n$-dimensional Hilbert space $\he\cong\Comp^n$ with a fixed orthonormal basis $\basis:=e_1,\ldots,e_n$;

  • a coin: an unitary operator $\coin$ on the spin space $\he$;

  • the jump map: a mapping $j:\basis\to L$. We will assume (without loss of generality) that the jumps $j_i=j(e_i),i=1,\ldots,n$ span $L$ affinely.;

These data engender the quantum random walk as a unitary operator on $\hilb=l_2(L)\otimes \he$, defined as the composition of two unitary operators.

First, one applies the coin $\coin$ (at each site), acting on each $\he_\bk, \bk\in L$ diagonally.

Second halfstep consists of shifting each of the "layers" $l_2(L)\otimes e_k, k=1,\ldots,n$ $$ \bk\otimes e_k\mapsto (\bk+\bj_k)\otimes e_k. $$

The resulting unitary operator is denoted by $\qstep$. The evolution defined by $\{{\qstep}^T\}_{T\in\Int_+}$ exhibits interesting ballistic behavior.

It is immediate that the matrix elements $$ (\bk\otimes e_k, \qstep^T \bl\otimes e_l) $$ depend only on $(\bl-\bk)$, $k$ and $l$, and vanish if $\bl-\bk$ cannot be represented as a sum of $T$ lattice vectors from $j(\basis)$.

In particular, these matrix elements vanish when $(\bl-\bk)$ is outside of the scaled by $T$ convex hull of the set of generating vectors $\mathbf{j}_k$ $$ \ch_j=\mathtt{conv}\left\{\bj_k=j(e_k), k=1,\ldots,n\right\}. $$

We will be interested in the wave functions $$ a_{\bk}^{(T)}(kl):= (\bk\otimes e_k, \qstep^T \mathbf{0}\otimes e_l). $$


The internal space $\he$ is spanned by $\mathbf{NE},\mathbf{NW},\mathbf{SE},\mathbf{SW}$, and the coin is given by $$ U={1\over 2} \begin{pmatrix} 1 & -1 & -1 & -1 \\ -1 & 1 & -1 & -1 \\ -1 & -1 & 1 & -1 \\ -1 & -1 & -1 & 1 \\ \end{pmatrix} $$
The lattice $L$ is the even sublattice of $\Int^2$, and the jump map is obvious from the state names.

The picture show simulated amplitudes for Hadamard planar random, in faux colors, for the even lattice and initial state being NE.
The number of steps is $T=200$.

The amplitudes of quantum random walks also can be viewed as statistical sums $$ \sum_{i_0,\ldots,i_{T-1}} \prod_t U_{i_ti_{t+1}}, $$ over the paths $\gamma$ such that $\gamma_{t+1}=\gamma_t+j_{i_t}, t=0,\ldots,T-1$, $\gamma(0)=\mathbf{0}$ and $\gamma(T)=\bk$.

In the case of the Hadamard coin, admissible paths have steps $(\pm 1, \pm 1)$, and the absolute value of the weight of any path is $$ 2^{-\mathtt{length\ of\ the\ path}}. $$
However, there is a phase: the weight is multiplied by $-1$ each time the direction of the trajectory is changing.

My interest in the area was sparked by a question by C. Moore, whether one can prove the visually apparent fact, that the range of Hadamard walks is a circle (meaning that the wave function is exponentially small outside the circle and has uniform scaling inside)

As simulations show, the amplitudes $a_{\cdot}$ exhibit beautiful interference patterns, localized strictly within the polytope $T\ch$.
Outside of the visible support, the amplitudes of $a$ do not vanish but rather are exponentially small.

Like the amplitudes, the (discrete) nonnegative measures (probabilities to be located at a site) $$ p_{u,v}(\bk, T)=|u^\dagger a(\bk,T) v|^2 $$ oscillate wildly.

When rescaled, the sqared absolute values of the amplitudes weakly converge to certain probability measure as $T\to\infty$, $$ p_{u,v}(\lfloor T\bp\rfloor, T)\to \limmes_{u,v}. $$

Random Coin

The limiting probability measure $\limmes^\coin_{u,v}$ (corresponding to the coin $\coin$) is supported by the polytope $\ch$, the convex hull of the jump vectors $\bj_i=j(e_i), i=1,\ldots,n$.

What is the typical behavior of these probability measures?

In these plots, a circle going through a unitary matrix is chosen at random, and their amplitudes at some time are plotted, one trace a frame.
A natural question to ask is about the average behavior of the asymptotic measures $\limmes=\limmes^\coin$ for random $\coin$.

The answer is surprisingly simple.

The picture shows the average probability measures over a few hundreds of simulation, in which a random unitary coins, drawn from Haar distribution in $\mathbf{U}(4)$, (and the jumps like in the Hadamard example) were used.

Here's the main result:

The average of $\limmes^\coin$ over $\coin$'s (with respect to the Haar measure) is the pushforward of the uniform measure on the simplex $\Delta$ spanned by the basis vectors $e_i,i=1,\ldots,n$ under the jump map, $j:e_i\mapsto \bj_i$, i.e. $$ \int \limmes^\coin d\coin=j_*({\mathtt{Uni}}_{\Delta}). $$

Asymptotics of the Amplitudes

The oscillation patterns of the amplitudes of quantum random walks are best understood in terms of the spectral surface.
For each $\bz=(z_1,\ldots,z_d)\in\Comp^d=L\otimes\Comp$ we define the operator $$ U_\bz=\mathtt{diag}(\bz^{\bj_1},\ldots,\bz^{\bj_n})U. $$
Say, for the Hadamard 2D walk (after the change of the jumps to E, W, N, S), $$ U_\bz=\begin{pmatrix} \frac{z_1}{2} &\frac{-z_1}{2} & \frac{-z_1}{2} & \frac{-z_1}{2} \\ \frac{-1}{2 z_1} &\frac{1}{2 z_1} & \frac{-1}{2 z_1} & \frac{-1}{2 z_1} \\ \frac{-z_2}{2} &\frac{-z_2}{2} & \frac{z_2}{2} & \frac{-z_2}{2} \\ \frac{-1}{2 z_2} &\frac{-1}{2 z_2} & \frac{-1}{2 z_2} & \frac{1}{2 z_2} \\ \end{pmatrix} $$

A quick computation yields, that the (operator-valued) generating function $$ a_T(\bz):=\sum_\bk a^{(T)}_\bk \bz^\bk $$ is given by $$ a_T(\bz)=U_\bz^T, $$ and the total generating function by $$ a(z_o,\bz):=\sum_{T\geq 0}z_o^T a_T(\bz)=(\one-z_o\coin_\bz)^{-1}. $$

Let $\torus_L$ be the torus of characters of $L$. Extend it to $\bigt=\torus^1\times \torus_L$.

The spectral surface is defined as $$ \spectral=\{(z_o,\bz)\in \bigt: \det(\one-z_oU_\bz)=0\}. $$

This is a (possibly, singular) real algebraic $d$-dimensional variety.

The projection $\pi_L:\bigt\to\torus_L$ restricted to $\spectral$ is an $n$-sheeted covering of $\torus_L$.

The spectral decomposition of $\coin_\bz$ gives for each point $(z_o,\bz)\in\spectral$ a projection $\proje(z_o,\bz)$ onto the corresponding eigenspace.

Proposition (many authors)
The amplitudes $a_\bk^{(T)}$ are the Fourier coefficients of the (operator valued) surface measure $\proje d\bz$, i.e. $$ a_{\bk}^{(T)}=\int_\spectral z_o^{-T}\bz^{-\bk}\proje d\bz. $$
This result allows one to view the asymptotics of the amplitudes as some special cases of oscillating integrals, using the standard tools of singularity theory.

It is useful to switch to logarithmic coordinates, identifying $\torus_L$ and $\bigt$ with $ (L_\Real)/L^*$ and $(\Real\times L_\Real)/(\Int\times L^*), $ respectively.
We will keep the notation for the spectral variety $\spectral\subset \bigt$.

The Fourier coefficients representation implies that the amplitudes $$ a_{\lfloor T\bp\rfloor, T} $$ decay faster than any degree of $T$ unless $(1,\bp)$ is a normal at some point of $\spectral$.

At a generic point of $(z_o, \bz)\in\spectral$, the corresponding contribution to $a$ is asymptotic to $$ \proje(z_o,\bz) |H(z_o,\bz)|^{-1/2} (z_o\bz^\bp)^T, - $$ here $H$ is the determinant of the second quadratic form of $\spectral$ at $(z_o,\bz)$.

Further, near a typical point of the boundary of the essential support of the amplitudes, they are given by Airy integral.
One finds also Pearcey integrals, and further oscillating integrals (depending on parameters).

Probability Measures associated with a QRW

When rescaled, the sqared absolute values of the amplitudes weakly converge. In fact, the limiting measure admits a geometric characterization:

As $T\to\infty$, $$ p_{u,v}(\lfloor T\bp\rfloor, T)\to \gauss_* (|u^\dagger \proje v|^2 dz), $$ the push-forward of the measure $|u^\dagger \proje v|^2 dz$ supported by $\spectral$ under the Gauss map.
(A version of this result is due to Grimmett, Janson, Scudo,'04.)

One can split this limiting probability density $$ p_v=\sum_{e_i\in \mathtt{Eig}(\coin)} p_{v,e_i}; $$ into the contribution from different sheets of $\spectral$.

One consequence is that the total mass coming from each of the $n$ sheets of $\spectral$ is $1/n$.
In particular, the total energy on the bright spot in the Hadamard QRW is $1/2$.

Random Coin

Thus far we established that the limiting probability density of the rescaled position of a QRW corresponding to a coin $\coin$ (with a starting state $v\otimes {\mathbf{0}}, |v|^2=1$) is the image of the measure $d\bz$ lifted to $\spectral$ under the Gauss map.

Recall our main result:

The average of $\limmes^\coin$ over $U$'s (with respect to the Haar measure) is the pushforward of the uniform measure on the simplex $\Delta$ spanned by the basis vectors $e_i,i=1,\ldots,n$ under the jump map, $j:e_i\mapsto \bj_i$, i.e. $$ \int \limmes^\coin d\coin=j_*({\mathtt{Uni}}_{\Delta}). $$

The proof is quite straightforward.
Denote by $\mathbf{K}$ the maximal torus in $\mathbf{U}(n)$. The augmented (multiplied by $z_o$) jump map defines a mapping $$ \jt:\bigt\to\mathbf{K}. $$
Let $(z_o,\bz)\in\spectral_U$ be a generic (smooth) point of the spectral surface for a generic coin $U$. In particular, this implies that $\proje=u\otimes u^\dagger$ has rank $1$.

Let $m(\proje)$ be the image of $\proje$ under the ``moment map'', i.e. $$ m(\proje)=(|u_1|^2,\ldots,|u_n|^2). $$

For a generic point $(z_o,\bz)$ of $\spectral_U$ of a generic $U$, $\tvect\in T_{(z_o,\bz)}\spectral$ iff $(m(\proje),\jt_*\tvect)=0$.

In other words, the Gauss map at $(z_o,\bz)$ is given by $\jt^*(m(\proje))$.

The theorem follows now from the standard facts: primarily, from the fact that the moment map takes the uniform measure on the unit sphere in $\Comp^n$ to the uniform measure on the $(n-1)$-simplex.