Blog - quantum network theory (part 2) (Rev #3)

This page is a blog article in progress, written by Tomi Johnson. Part 1 is found here. To see discussion of the pair of articles while they are being written, visit the Azimuth Forum.

guest post by **Tomi Johnson**

Last time I told you how a stochastic walk could be used to analyze a network, in particular Google uses it to rank nodes. In the case of an undirected network, the steady state of the stochastic walk tells us the degrees of the nodes.

Here, I’m going to show this to you. I’m also going to connect this to a corresponding quantum walk, also introduced last time. In the end, we’ll have connected the properties of this quantum walk to the degrees of a network by exploiting its relationship with the stochastic walk.

This is pretty cool considering how tricky these quantum walks can be to study, as we’ll see. As the parts of the world that we model using quantum mechanics get bigger and have more complicated structures, like biological network, we need all the help in understanding quantum walks that we can get. I better start then!

Previously, we introduced a stochastic and quantum walk, generated by the similar matrices $S$ and $Q$ respectively. The first describes the uniform escape stochastic walk who’s steady state tells us so much about the degrees of a network. The second is the related quantum walk we’re going to solve in this article.

Both walks follow from a graph and all we learnt last time is summarized by the following diagram

where

• $G$ is a simple graph that specifies

• $A$ the adjacency matrix (generator of a quantum walk), which subtracted from

• $D$ the diagonal matrix of the degrees gives

• $L$ the symmetric Laplacian (generator of stochastic and quantum walks), which when normalized by $D$ returns both

• $S$ the generator of the uniform escape stochastic walk and

• $Q$ the quantum walk generator to which it is similar!

Now we remember where we are, next I’ll talk you through the mathematics of the uniform escape stochastic walk $S$ and how it connects to the degrees of the nodes in the long-time limit. Then I’ll show you how this helps us solve aspects of the quantum walk generated by $Q$.

The uniform escape stochastic walk generated by $S$ is popular because it has a really useful **stationary state**.

To recap from part 20 in the series, a stationary state of a stochastic walk is one that does not change in time. From the master equation $\frac{d}{d t} \psi(t) = -S \psi(t)$ the stationary state must be an eigenvector $\pi_0^i$ of $S$ with eigenvalue $\epsilon_0 = 0$.
A fantastic pair of theorems hold:
• There is always a unique (up to multiplication by a positive number) positive eigenvector $\pi_0$ (abbreviated as $\pi$) of $S$ with eigenvalue $\epsilon_0 = 0$, i.e., a **unique stationary state** $\pi$.
• Regardless of the initial state $\psi(0)$, the stationary state $\pi$ is obtained in the long-time limit $ \lim_{t \rightarrow \infty} \psi(t) = \pi$.

To find this unique stationary state, consider the Laplacian $L$, which is both infinitesimal stochastic and symmetric. Among other things, this means the rows of $L$ sum to zero

$\displaystyle{ \sum_j L_{i j} = 0 }$

which means the all ones vector $\mathbf{1}$ is an eigenvector of $L$ with zero eigenvalue

$L \mathbf{1} = 0$

Inserting the identity $I = D^{-1} D$ into this equation we then find $D \mathbf{1}$ is a zero eigenvector of $S$

$L \mathbf{1} = ( L D^{-1} ) ( D \mathbf{1} ) = S ( D \mathbf{1} ) = 0$

Therefore we just need to normalize this to get the long-time stationary state of the walk

$\pi = \frac{D \mathbf{1}}{\sum_i D_{i i}}$

Each element $\langle i , \pi \rangle$ of this state, the long-time probability of finding a walker at node $i$, is proportional to the degree $D_{i i}$ of node $i$!

We can check this holds for the following graph

We find that $\pi$ is

$\left( \begin{matrix} 1/6 \\ 1/6 \\ 1/4 \\ 1/4 \\ 1/6 \end{matrix} \right)$

which implies long-time probability $1/6$ for nodes $1$, $2$ and $5$, and $1/4$ for nodes $3$ and $4$. Comparing this to the original graph, this exactly reflects the arrangement of degrees, as we knew it must. Math works!

Next up is the quantum walk generated by $Q$. Not a lot is known about quantum walks on networks of arbitrary geometry, but below we’ll see some analytical results are obtained by exploiting the similarity of $S$ and $Q$.

Where to start? Well, let’s start from the bottom, what quantum physicists call the **ground state**. In contrast to stochastic walks, for a quantum walk every eigenvector $\phi_i^k$ of $Q$ is a stationary state of the quantum walk (in puzzle 5, at the bottom of this page, I ask you to prove this). The stationary state $\phi_0$ is of particular interest physically and mathematically. Physically, since eigenvectors of the $Q$ correspond to states of well-defined energy equal to the associated eigenvalue, $\phi_0$ is the state of lowest energy $\epsilon_0 = 0$, hence the name ground state (in puzzle 3 we ask you to prove that all eigenvalues of $Q$ are non-negative, so zero really does correspond to the ground state).

Mathematically, the relationship between eigenvectors implied by the similarity of $S$ and $Q$ means $\phi_0 \propto D^{-1/2} \pi \propto D^{1/2} \mathbf{1}$. So, if in the ground state, the probability of being measured to be at node $i$ is $| \langle i , \phi_0 \rangle |^2 \propto | \langle i , D^{1/2} \rangle |^2 = D_{i i}$. Amazingly, this probability is proportional to the degree and so is exactly the same as $\langle i , \pi \rangle$, the probability in the stationary state $\pi$ of the stochastic walk.

A zero energy quantum walk $Q$ leads to exactly the same distribution of the walker over the nodes as in the long-time limit of the uniform escape stochastic walk $S$.

The normally classical notion of degree distribution plays a role in quantum walks!

This is already pretty exciting. But what else can we say? If you are someone who feels faint at the sight of quantum mechanics, well done for getting this far, but be prepared for what’s coming next.

What if the walker starts in some other initial state? Is there some quantum walk analogue of the unique long-time state of a stochastic walk?

In fact, the quantum walk in general does not converge to a stationary state. But there is a probability distribution that can be thought to characterize the quantum walk in the same way as the long-time state characterizes the stochastic walk. It’s the **long-time average probability vector** $P$.

This standout should appear OK on the blog, sorry for its current appearance. - Tomi

If you didn't know the time that had passed since the beginning of a quantum walk, then the best estimate for the probability of your measuring the walker to be at node $i$ would be the long-time average probability
$$ \displaystyle{ \langle i , P \rangle = \lim_{T \rightarrow \infty} \frac{1}{T} \int_0^T | \psi_i (t) |^2 d t } $$
There’s a bit that we can do to simplify this expression. As always, lets start with the trick of inserting the decomposition $Q= \sum_k \epsilon_k \Phi_k $ into $ \psi(t) = e^{-Q t} \psi(0) $ to get $ \psi(t) = \sum_k e^{-\epsilon_k t} \Phi_k \psi(0) $ and thus
$$ \displaystyle{ \langle i , P \rangle = \lim_{T \rightarrow \infty} \frac{1}{T} \int_0^T | \sum_k e^{-i \epsilon_k t} \langle i, \Phi_k \psi (0) \rangle |^2 d t } $$
Due to the integral over all time the interferences between terms corresponding to different eigenvalues average to zero, leaving
$$ \langle i , P \rangle = \sum_k | \langle i, \Phi_k \psi(0) \rangle |^2 $$
The long-time average probability is then the sum of terms contributed by the projections of the initial state onto each eigenspace.

So we have a distribution that characterizes a quantum walk for a general initial state but it’s a complicated beast. What can we say about it?

Our best hope of understanding the long-time average probability is through the term $| \langle i, \Phi_0 \psi (0) \rangle |^2$ associated with the zero energy eigenspace, since we know everything about this space.

For example, we know the zero energy eigenspace is one-dimensional and spanned by the eigenvector $\phi_0$. This means that the projector is just the usual outer product

$\Phi_0 = | \phi_0 \rangle \langle \phi_0 | = \phi_0 \phi_0^\dagger$

where we have normalized $\phi_0$ according to the inner product $\langle \phi_0, \phi_0\rangle = 1$. (If you’re wondering why I’m using all these angled brackets, well, it’s a type of notation named after Dirac that is adored by quantum physicists.)

The zero eigenspace contribution to the long-time average probability then breaks nicely into two

$| \langle i, \Phi_0 \psi (0) \rangle |^2 = | \langle i, \phi_0\rangle \langle \phi_0, \psi (0) \rangle |^2 = | \langle i, \phi_0\rangle |^2 | \langle \phi_0 , \psi (0) \rangle |^2 = \langle i , \pi \rangle | \langle \phi_0 , \psi (0) \rangle |^2$

This is just the product of two probabilities!

First the probability $\langle i , \pi \rangle$ for a quantum state in the zero energy eigenspace to be at node $i$ (as we found above) and second the probability $| \langle \phi_0, \psi (0)\rangle |^2$ of being in this eigenspace to begin with (in quantum mechanics the probability of measuring the system to have an energy is the modulus squared of the projection of the state onto the associated eigenspace, which for the one dimensional zero energy eigenspace means just the inner product with the ground state.)

This is all we need to say something interesting about the long-time average probability for all states. We’ve basically shown that we can break the long-time probability vector $P$ into a sum of two normalized probability vectors

$P = (1- \eta) \pi + \eta \Omega$

the first $\pi$ being the degree dependent stochastic stationary state associated with the zero energy eigenspace and the second associated with the higher energy eigenspaces $\Omega$, with

$\displaystyle{ \langle i , \Omega \rangle = \frac{ \sum_{k\neq 0} | \langle i, \Phi_k \psi (0) \rangle |^2 }{ \eta} }$

The weight of each term is governed by the parameter

$\eta = 1 - | \langle \phi_0, \psi (0)\rangle |^2$

which you could think of as the **quantumness** of the result. This is unity minus the probability of the walker being in the zero energy eigenspace, or equivalently the probability of the walker being outside the zero energy eigenspace.

So even though we don’t know anything about $\Omega$ we know its importance is controlled by a parameter $\eta$ that governs how close the long-time average distribution $P$ of the quantum walk is to the corresponding stochastic stationary distribution $\pi$. What do we mean by close? Find out for yourself:

There are several occasions on which I wish to start a line with `<b>`

. This causes an error. As a temporary work around, on each occasion I have added “UGH - A BUG ” to the start of the line. - Tomi

UGH - A BUG **Puzzle 1.** Show, using a triangle inequality, that the trace distance between the two characteristic stochastic and quantum distributions $\{ \langle i , P \rangle \}_i$ and $\{ \langle i , \pi \rangle \}_i$ is upper-bounded by $2 \eta$.

Can we say anything physical about when the quantumness $\eta$ is big or small?

Because the eigenvalues of $Q$ have a physical interpretation in terms of energy, the answer is yes. The quantumness $\eta$ is the probability of being outside the zero energy state. Call the next lowest eigenvalue $\Delta = \min_{k \neq 0} \epsilon_k$ the energy gap. If the quantum walk is not in the zero energy eigenspace then it must be in an eigenspace of energy greater or equal to $\Delta$. Therefore the expected energy $E$ of the quantum walker must bound the quantumness $E \ge \eta \Delta$.

This tells us that a quantum walk with a low energy is similar to a stochastic walk in the long-time limit (we already knew this exactly in the zero energy limit).

So little is known about quantum walks on networks of arbitrary geometry, that we were very pleased to find this result. It says there is a special case in which the walk is characterized by the degree distribution of the network and gives us a clear physical parameter that bounds how far the walk is from this special case.

Also, in finding it we learnt that the difficulties of the initial state dependence, enhanced by the lack of convergence to a stationary state, could be overcome for a quantum walk, and that the relationships between quantum and stochastic walks extend beyond those with shared generators.

That’s all for the latest bit of idea sharing at the interface between stochastic and quantum systems.

I hope I’ve piqued your interest about quantum walks. There’s so much still left to work out about this topic, and your help is needed!

Other questions we have include: What holds analytically about the form of the quantum correction? Numerically it is known that the so-called quantum correction $\Omega$ tends to enhance the probability of being found on nodes of low degree compared to $\pi$, can someone explain why? What happens if a small amount of stochastic noise is added to a quantum walk? Or a lot of noise?

It’s difficult to know who is best placed to answer these questions: experts in quantum physics, graph theory, complex networks or stochastic processes? I suspect it’ll take a bit of help from everyone.

To close, the ISI team recently attended (in fact helped organize) a workshop at IQC on the topic of quantum complex networks. Needless to say, there were talks on papers related to quantum mechanics and networks!

Some researchers at the workshop gave exciting talks based on numerical examinations of what happens if a quantum walk is used instead of a stochastic walk to rank the nodes of a network:

• Giuseppe Davide Paparo and Miguel Angel Martín-Delgado, Google in a Quantum Network, *Sci. Rep.* **2** (2012), 444.

• Eduardo Sánchez-Burillo, Jordi Duch, Jesús Gómez-Gardenes and David Zueco, Quantum Navigation and Ranking in Complex Networks, *Sci. Rep.* **2** (2012), 605.

Others attending the workshop have numerically examined what happens when using quantum computers to represent the stationary state of a stochastic process:

• Silvano Garnerone, Paolo Zanardi and Daniel A. Lidar, Adiabatic quantum algorithm for search engine ranking, *Phys. Rev. Lett.* **108** (2012), 230506.

It was a fun workshop and we plan to organize/attend more in the future.

A couple of textbooks with comprehensive sections on non-negative matrices and continuous-time stochastic processes are:

• Peter Lancaster and Miron Tismenetsky, *The Theory of Matrices: with Applications*, 2nd Ed., Academic Press, San Diego, 1985.

• James R. Norris, *Markov Chains*, Cambridge University Press, Cambridge, 1997.

There is, of course, the book that arose from the Azimuth network theory series, which considers several relationships between quantum and stochastic processes on networks:

• John Baez and Jacob Biamonte, *A Course on Quantum Techniques for Stochastic Mechanics*, 2012.

Another couple on complex networks are:

• Mark Newman, *Networks: An Introduction*, Oxford University Press, Oxford, 2010.

• Ernesto Estrada, *The Structure of Complex Networks: Theory and Applications*, Oxford University Press, Oxford, 2011. Note that the first chapter is available free online.

Sadly I didn’t have space to show proofs of all the theorems I used. So here are a few puzzles that guide you to doing the proofs for yourself:

UGH - A BUG **Puzzle 2.** (For the hard core) Prove there is always a unique positive eigenvector for a stochastic walk generated by $S$. You’ll need the assumption that the graph $G$ is connected. It’s not simple, and you’ll probably need help from a book, perhaps one of those above by Lancaster and Tismenetsky, and Norris.

UGH - A BUG **Puzzle 3.** Show that the eigenvalues of $S$ (and therefore $Q$) are non-negative i.e. $\epsilon_k \ge 0$. A good way to start this proof is to apply the Perron-Frobenius theorem to the non-negative matrix $M = - S + I \max_i S_{i i}$. This means $M$ has a positive eigenvalue $r$ equal to its spectral radius ($r = \max_k | \lambda_k |$ where $\{ \lambda_k \}_k$ are the eigenvalues of $M$), and the associated eigenvector $v$ is positive. Since $S = - M + I \max_i S_{i i}$, it follows that $S$ shares the eigenvectors of $M$ and the associated eigenvalues are related by inverted translation $\epsilon_k = - \lambda_k + \max_i S_{i i}$.

UGH - A BUG **Puzzle 4.** Prove that regardless of the initial state $\psi(0)$, the zero eigenvector $\pi$ is obtained in the long-time limit $\lim_{t \rightarrow \infty} \psi(t) = \pi$ of the walk generated by $S$. This breaks down into two parts:

UGH - A BUG **(a)** Using the approach from puzzle 5, to show that $S v = \epsilon_v v$, the positivity of $v$ and the infinitesimal stochastic property $\sum_i S_{i j} = 0$ imply that $\epsilon_v = \epsilon_0 = 0$ and thus $v = \pi$ is actually the unique zero eigenvector and stationary state of $S$ (its uniqueness follows from puzzle 4, you don’t need to re-prove it).

UGH - A BUG **(b)** By inserting the decomposition $S = \sum_k \epsilon_k \Pi_k$ into $e^{-S t}$ and using the result of puzzle 5, complete the proof.

(Though I ask you to use the diagonalizability of $S$, the main results still hold if the generator is irreducible but not diagonalizable.)

Here are a couple of extra puzzles for those of you interested in quantum mechanics:

UGH - A BUG **Puzzle 5.** In quantum mechanics, probabilities are given by the moduli squared of amplitudes, so multiplying a state by a number of modulus unity has no physical effect. By inserting $Q= \sum_k \epsilon_k \Phi_k$ into the quantum evolution matrix $e^{-Q t}$ show that if $\psi(0) = \phi_i^k$ then $\psi(t) = e^{ - i \epsilon_k t} \psi(0)$, hence $\phi_i^k$ is a stationary state as probabilities don’t change in time.

UGH - A BUG **Puzzle 6.** By expanding the initial state $\psi(0)$ in terms of the complete orthogonal basis vectors $\{ \phi_k^i \}_i$, show that for a quantum walk $\psi(t)$ never converges to a stationary state unless it began in one.