Discrete Quantum Walks: Problems

1. Linear Algebra

  1. 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.
  2. If $H$ is Hermitian, show that $I-iH$ is invertible and $(I+iH)(I-iH)^{-1}$ is unitary.
  3. 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$.]
  4. 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$?
  5. 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.]
  6. 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.]
  7. 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.]
  8. 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

  1. 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$.
  2. Show that the transition matrix of the arc reversal Grover walk for a $d$-regular graph $X$ is $\frac2d A(LD(X))-R$.
  3. 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

  1. Show that $A(X)$ is a sum of $d$ permutation matrices if and only if $X$ is $d$-regular.