Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
In Child's notes on quantum walks, he claims (section 16.6) "Since a quantum walk is a unitary process, we should not expect it to approach a limiting quantum state, no matter how long we wait."
But why should this be true? I understand that quantum mechanical processes must be time-reversible, but so long as the distribution is only stationary in the limit, it seems fine to allow quantum walks to merely approach a limiting state.
Suppose for contradiction that there is some limiting state $|f\rangle$ that an initial state $|s_1\rangle \neq |f\rangle$ approaches as a unitary operation $U$ is repeatedly applied. So there is some series of states $|s_1\rangle$, $|s_2\rangle$, etc where $|s_{k+1}\rangle = U |s_k\rangle$ and $\lim_{k \rightarrow \infty} |s_k\rangle = |f\rangle$.
Here's the problem. Unitary operations can't change relative dot products. It's always the case that $|\langle a | b \rangle| = |\langle Ua | Ub \rangle|$. Consider the overlap between the state of the iteration starting from $|s_1\rangle$, and what you would have gotten instead by starting from $|s_2\rangle$, as you repeatedly apply $U$. The initial overlap between the current state of these processes is some number less than one. But by assumption of the existence of $|f\rangle$ the action of iterating $U$ needs to send them both towards $|f\rangle$. The action needs to increase their overlap in a way that limits to 1. Iterating $U$ needs to increase their overlap, but unitary operations can't increase overlap. Contradiction. Therefore there is not actually a limiting state $|f\rangle$.
That's an interesting point and I suppose reversibility, interpreted as bijectivity, is not enough.
But unitarity implies a lot more. More specifically, unitary operators preserve distance. So we can prove a short impossibility result on limits existing, i.e., $U^n\vert x\rangle$ can never converge unless $\vert x\rangle$ is already an eigenvector of eigenvalue $1$.
Suppose for a contradiction that $U^nx$ converges to some state $y$ (I won't use kets just to make notation easier). Let $\epsilon > 0$. Pick whatever $N_1$ is large enough such that $\Vert U^N x - y\Vert < \epsilon$ for all $N\geq N_1$. But notice that $U^{N_1}$ is also unitary, so we can argue that
$$ \Vert U^{N_1}x - U^{2N_1}x\Vert = \Vert U^{N_1}(x - U^{N_1}x)\Vert = \Vert x - U^{N_1}x\Vert$$
and then use the triangle inequality
$$ \Vert U^{N_1}x - U^{2N_1}x\Vert \leq \Vert U^{N_1}x - y\Vert + \Vert y - U^{2N_1}x\Vert < 2\epsilon$$
but then we can further argue that
$$ \Vert x - y\Vert \leq \Vert x - U^{N_1}x\Vert + \Vert U^{N_1}x - y\Vert < 3\epsilon$$ by combining the equation and inequality above. Since $\epsilon$ was arbitrary, this implies $x=y$.
