Discrete Quantum Walks: Problems
1. Linear Algebra
- If $U$ is a unitary matrix, it is normal and has a spectral decomposition
\[ U = \sum_r \la_r F_r.\]
Use this to show that there is a Hermitian matrix $H$ such that $U=\exp(iH)$.
If $U$ is not diagonal, show that $H$ is not unique.
- If $H$ is Hermitian, show that $I-iH$ is invertible and $(I+iH)(I-iH)^{-1}$ is
unitary.
- If $\pi$ is a partition of $\{1,\ldots,n\}$ with $k$-cells, its characteristic
matrix $P$ is the $n \times k$ matrix with the characteristic vectors of the
cells of $\pi$ as its columns. We have $D=P^TP$ is diagonal. Prove that
$Q=P^TD^{-1}P^T$ is a projection and $(2Q-I)^2=I$. [Here $Q$ represents orthogonal
projection from the space of real functions on $\{1,\ldots,n\}$ to the subspace
of real functions that are constant on each cell of $\pi$.]
- Let $X$ be a directed graph with $n$ vertices and $m$ arcs. Define the head partition
$\pi_h$ of the arcs where two arcs are in the same cell if they have the same head.
Similarly define $\pi_t$, the tail partition. Let $P_h$ and $P_t$ be the
respective characteristic matrices of these partitions. Prove that $P_hP_t^T$ is
the adjacency matrix of the line digraph of $X$. What is $P_t^TP_h$?
- Let $X$ be a bipartite graph, vertices coloured white and black. We can partition the
edges in two ways: according to the white vertex they contain, or according to the
black vertex. Denote them by $\pi_w$ and $\pi_b$ respectively, and let $P_w$ and $P_b$
be the associated normalized characteristic matrices. Then we get two reflections,
and a discrete quantum walk on the edges (not arcs) of $X$. Show that we can get
the arc-reversal walk with the Grover coin in this way. [Remark: we call walks of this form
bipartite walks.]
- Assume $U$ is unitary and $(U^k)_{i,j}=0$ for all $k$. If $i\ne j$, prove that $(U^k){j,i}=0$.
Prove that we cannot have $i=j$. [Remark: My proof uses spectral decomposition.]
- Let $U$ be a $d\times d$ unitary matrix. Then the matrices
\[ I, U, U^2,\ldots \]
form an infinite sequence of elements of the unitary group $U_d(\cx)$.
Since the unitary group is a compact subset of $\cx^{d\times d}$,
this sequence has limit points. Let $W$ be one of these.
Given $\eps>0$, there are infinitely many integers $k$ such that
$\|U^k-W\| \lt \eps$. (Why?) Deduce that there are distinct integers $k$ and $\ell$
such that $\|U^k-U^\ell\| \lt 2\eps$. Using this, prove
that if $\epsilon\gt0$, there is an integer $m$ such that $\|I-U^m\|\lt\eps$.
[This exercise shows that any discrete quantum walk is "approximately recurrent".
One problem is that the waiting time can be very large.]
- Let $P$ be an orthogonal projection $P^2=P=P^*$. Show that a matrix $M$ commutes
with $P$ if and only if both subspaces $\im(P)$ and $\ker(P)$ are $M$-invariant.
2. Arc-Reversal Walks
- Let $U$ be the transition matrix of the arc reversal Grover walk. Let $\hat{A}$ be the
weighted adjacency matrix of the graph. Show that if $\lambda=\cos(\theta)$ is an
eigenvalue of $\hat{A}$, then $e^{\pm i \theta}$ is an eigenvalue of $U$.
- Show that the transition matrix of the arc reversal Grover walk for a $d$-regular graph $X$
is $\frac2d A(LD(X))-R$.
- Let ${C_1, ..., C_k}$ be an equitable partition of $V(X)$. Let $C_{i,j}$ be the set
of arcs $(a, b)$ such that $a\in C_i$ and $b \in C_j$.
Show that the sets $C_{i,j}$ form an equitable partition of $V(LD(X))$.
3. Shunt Decompositions
- Show that $A(X)$ is a sum of $d$ permutation matrices if and only
if $X$ is $d$-regular.