The Azimuth Project
Blog - quantum complex networks

This blog article in progress, written by Tomi Johnson, has had its name changed and has been split into two parts. See blog - quantum network theory (part 1) and blog - quantum network theory (part 2). To see discussion of the pair of articles while they are being written, visit the Azimuth Forum.

UGH A BUG! guest post by Tomi Johnson

If you were to randomly click a hyperlink on this web page and keep doing so on each page that followed, where would you end up?

As an esteemed user of Azimuth, I’d like to think you browse more intelligently, but the above is the question Google asks when deciding how to rank the world’s web pages.

Recently, together with the team (Mauro Faccin, Jacob Biamonte and Piotr Migdał) at the ISI Foundation in Turin, we attended a workshop where several of the attendees were asking a similar question with a twist. “What if you, the web surfer, behaved quantum mechanically?”

Now don’t panic! I have no reason to think you might enter a superposition of locations or tunnel through a wall. This merely forms part of a recent drive towards understanding the role that network science can play in quantum physics.

As we’ll find, playing with quantum networks is fun. It could also become a necessity. The size of natural systems in which quantum effects have been identified has grown steadily over the past few years. For example, attention has recently turned to explaining the remarkable efficiency of light-harvesting complexes, comprising tens of molecules and thousands of atoms, using quantum mechanics. If this expansion continues, perhaps quantum physicists will have to embrace the concepts of complex networks.

To begin studying quantum complex networks, we found a revealing toy model. Let me tell you about it. Like all good stories, it starts with a graph, this time representing the internet!

If this taster gets you interested, there are more details available online at:

• Mauro Faccin, Tomi Johnson, Jacob Biamonte, Sabre Kais and Piotr Migdał, Degree distribution in quantum walks on complex networks.

We’ll be working through Sec II.A and Sec II.B of this paper but no further. We’ll end by bounding the difference between a stochastic walk (like the randomly clicking web surfer mentioned above) and a corresponding quantum walk, in terms of the energy of the walker.

What does the internet look like from above?

As we all know, the idea of the internet is to connect computers to each other. What do these connections look like when abstracted as a network, with each computer a node and each connection an edge?

The internet on a local scale, such as in your house or office, might look something like this

Local network

with several devices connected to a central hub. Each hub connects to other hubs, and so the internet on a slightly larger scale might look something like this

Regional network

What about the full global, not local, structure of the internet? To answer this question, researchers have developed representations of the whole internet, such as this one

Global network

While such representations might be awe inspiring, how can we make any sense of them? (Or are they merely excellent desktop wallpapers and new-age artworks?)

In terms of complex network theory, there’s actually a lot that can be said that is not immediately obvious from the above representation.

For example, we find something very interesting if we plot the number of web pages with different incoming links (called degree) on a log-log axis. What is found for the African web is the following

Power law degree distribution

This shows that very few pages are linked to by a very large number others, while a very large number of pages receive very few links. More precisely, what this shows is a power law distribution, the signature of which is a straight line on a log-log axis.

In fact, power law distributions arise in a diverse number of real world networks, human-built networks such as the internet and naturally occurring networks. It is often discussed alongside the concept of the preferential attachment; highly connected nodes seem to accumulate connections more quickly. We all know of a successful blog whose success had led to an increased presence and more success. That’s an example of preferential attachment.

It’s clear then that degree is an important concept in network theory, and its distribution across the nodes a useful characteristic of a network. Degree gives one indication of how important a node is in a network.

And this is where stochastic walks come in. Google, who are in the business of ranking the importance of nodes (web pages) in a network (the web), use (up to a small modification) the idealized model of a stochastic walker (web surfer) who randomly hops to connected nodes (follows one of the links on a page). This is called the uniform escape model, since the total rate of leaving any node is set to be the same for all nodes. Leaving the walker to wander for a long while, Google then takes the probability of the walker being on a node to rank the importance of that node. In the case that the network is undirected (all links are reciprocated) this long-time probability, and therefore the rank of the node, is proportional to the degree of the node.

So node degrees and the uniform escape model play an important role in the fields of complex networks and stochastic walks. But can they tell us anything about the much more poorly understood topics of quantum networks and quantum walks? In fact, yes, and demonstrating that to you is the purpose of this post.

Before we move on to the interesting bit, the math, it’s worth just listing a few properties of quantum walks that make them hard to analyze, and explaining why they are poorly understood. These are the difficulties we will show how to overcome below.

There are several occasions on which I wish to start a line with <b> or <i>. 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

No convergence. In a stochastic walk, if you leave the walker to wander for a long time, eventually the probability of finding a walker at a node converges to a constant value. In a quantum walk, this doesn’t happen, so the walk can’t be characterized so easily by its long-time properties.

Dependence on initial states. In some stochastic walks the long-time properties of the walk are independent of the initial state. It is possible to characterize the stochastic walk without referring to the initialization of the walker. Such a characterization is not so easy in quantum walks, since their evolution always depends on the initialization of the walker. Is it even possible then to say something useful that applies to all initializations?

Stochastic and quantum generators differ. Those of you familiar with the network theory series know that some generators produce both stochastic and quantum walks (see part 16 for more details). However, most stochastic walk generators, including that for the uniform escape model, do not generate quantum walks and vice versa. How do we then compare stochastic and quantum walks when their generators differ?

With the task outlined, let’s get started!

Graphs and walks

In the next couple of sections I’m going to explain the diagram below to you. If you’ve been following the network theory series, in particular part 20, you’ll find parts of it familiar. But as it’s been a while since the last post covering this topic, let’s start with the basics.

Diagram outlining the main concepts

A simple graph GG can be used to define both stochastic and quantum walks. A simple graph is something like this

Illustration of a simple graph

where there is at most one edge between any two nodes, there are no edges from a node to itself and all edges are undirected. To avoid complications, let’s stick to simple graphs with a finite number nn of nodes. Let’s also assume you can get from every node to every other node via some combination of edges i.e. the graph is connected.

In the particular example above the graph represents a network of n=5n = 5 nodes, where nodes 3 and 4 have degree (number of edges) 3, and nodes 1, 2 and 5 have degree 2.

Every simple graph defines a matrix AA, called the adjacency matrix. For a network with nn nodes, this matrix is of size n×nn \times n, and each element A ijA_{i j} is unity if there is an edge between nodes ii and jj, and zero otherwise (let’s use this basis for the rest of this post). For the graph drawn above the adjacency matrix is

(0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0) \left( \begin{matrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{matrix} \right)

By construction, every adjacency matrix is symmetric A=A TA =A^T (the TT means the transposition of the elements in the node basis) and further, because each AA is real, it is self-adjoint A=A A=A^\dagger (the \dagger means conjugate transpose).

This is nice, since (as seen in parts 16 and 20) a self-adjoint matrix generates a continuous-time quantum walk.

There are three occasions on which I was using the +-- {: .standout} command. Since this is not possible for a blog article, I have tried to achieve the same effect using style property of the div element. Presuming that the paragraphs inside this element will automatically be placed inside a p element, and the equations dealt with, this should look ok. Of course, at the moment it looks horrible. If anyone has a better idea, please let me know and I will implement. - Tomi

To recap from the series, a quantum walk is an evolution arising from a quantum walker moving on a network. A state of a quantum walk is represented by a size $n$ complex column vector $\psi$. Each element $\langle i , \psi \rangle$ of this vector is the so-called amplitude associated with node $i$ and the probability of the walker being found on that node (if measured) is the modulus of the amplitude squared $|\langle i , \psi \rangle|^2$. Here $i$ is the standard basis vector with a single non-zero $i$-th entry equal to unity, and $\langle u , v \rangle = u^\dagger v$ is the usual inner vector product. A quantum walk evolves in time according to the Schrödinger equation $$ \displaystyle{ \frac{d}{d t} \psi(t)= - i H \psi(t) } $$

where $H$ is called the Hamiltonian. If the initial state is $\psi(0)$ then the solution is written as

$$ \psi(t) = \exp(- i t H) \psi(0) $$ The probabilities $\{ | \langle i , \psi (t) \rangle |^2 \}_i$ are guaranteed to be correctly normalized when the Hamiltonian $H$ is self-adjoint.

There are other matrices that are defined by the graph. Perhaps the most familiar is the Laplacian, which has recently been a topic on this blog (see parts 15, 16 and 20 of the series, and this recent post).

The Laplacian LL is the n×nn \times n matrix L=DAL = D - A, where the degree matrix DD is an n×nn \times n diagonal matrix with elements given by the degrees

D ii= jA ij \displaystyle{ D_{i i}=\sum_{j} A_{i j} }

For the graph drawn above the degree matrix and Laplacian are

(2 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 3 0 0 0 0 0 2)and(2 1 0 1 0 1 2 1 0 0 0 1 3 1 1 1 0 1 3 1 0 0 1 1 2) \left( \begin{matrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{matrix} \right) \qquad \mathrm{and} \qquad \left( \begin{matrix} 2 & -1 & 0 & -1 & 0 \\ -1 & 2 & -1 & 0 & 0 \\ 0 & -1 & 3 & -1 & -1 \\ -1 & 0 & -1 & 3 & -1 \\ 0 & 0 & -1 & -1 & 2 \end{matrix} \right)

The Laplacian is self-adjoint and generates a quantum walk.

The Laplacian has another property; it is infinitesimal stochastic. This means that its off diagonal elements are non-positive and its columns sum to zero. This is interesting because an infinitesimal stochastic matrix generates a continuous-time stochastic walk.

To recap from the series, a stochastic walk is an evolution arising from a stochastic walker moving on a network. A state of a stochastic walk is represented by a size $n$ non-negative column vector $\psi$. Each element $\langle i , \psi \rangle$ of this vector is the probability of the walker being found on node $i$. A stochastic walk evolves in time according to the master equation $$ \displaystyle{ \frac{d}{d t} \psi(t)= - H \psi(t) } $$ where $H$ is called the stochastic Hamiltonian. If the initial state is $\psi(0)$ then the solution is written $$ \psi(t) = \exp(- t H) \psi(0) $$ The probabilities $\{ \langle i , \psi (t) \rangle \}_i$ are guaranteed to be non-negative and correctly normalized when the stochastic Hamiltonian $H$ is infinitesimal stochastic.

So far, I have just presented what has been covered on Azimuth previously. However, to analyze the important uniform escape model we need to go beyond the class of (Dirichlet) generators that produce both quantum and stochastic walks. Further, we have to somehow find a related quantum walk. We’ll see below that both tasks are achieved by considering the normalized Laplacians: one generating the uniform escape stochastic walk and the other a related quantum walk.

Normalized Laplacians

The two normalized Laplacians are

• the asymmetric normalized Laplacian S=LD 1S = L D^{-1} (that generates the uniform escape SStochastic walk) and

• the symmetric normalized Laplacian Q=D 1/2LD 1/2Q = D^{-1/2} L D^{-1/2} (that generates a QQuantum walk).

For the graph drawn above the asymmetric normalized Laplacian SS is

(1 1/2 0 1/3 0 1/2 1 1/3 0 0 0 1/2 1 1/3 1/2 1/2 0 1/3 1 1/2 0 0 1/3 1/3 1) \left( \begin{matrix} 1 & -1/2 & 0 & -1/3 & 0 \\ -1/2 & 1 & -1/3 & 0 & 0 \\ 0 & -1/2 & 1 & -1/3 & -1/2 \\ -1/2 & 0 & -1/3 & 1 & -1/2 \\ 0 & 0 & -1/3 & -1/3 & 1 \end{matrix} \right)

The identical diagonal elements indicates that the total rates of leaving each node are identical, and the equality within each column of the other non-zero elements indicates that the walker is equally likely to hop to any node connected to its current node. This is the uniform escape model!

For the same graph the symmetric normalized Laplacian QQ is

(1 1/2 0 1/6 0 1/2 1 1/6 0 0 0 1/6 1 1/3 1/6 1/6 0 1/3 1 1/6 0 0 1/6 1/6 1) \left( \begin{matrix} 1 & -1/2 & 0 & -1/\sqrt{6} & 0 \\ -1/2 & 1 & -1/\sqrt{6} & 0 & 0 \\ 0 & -1/\sqrt{6} & 1 & -1/3 & -1/\sqrt{6} \\ -1/\sqrt{6} & 0 & -1/3 & 1 & -1/\sqrt{6} \\ 0 & 0 & -1/\sqrt{6} & -1/\sqrt{6} & 1 \end{matrix} \right)

That the diagonal elements are identical in the quantum case indicates that all nodes are of equal energy, this is type of quantum walk usually considered.

UGH - A BUG Puzzle 1. Show that in general SS is infinitesimal stochastic but not self-adjoint.

UGH - A BUG Puzzle 2. Show that in general QQ is self-adjoint but not infinitesimal stochastic.

So a graph defines two matrices: one SS that generates a stochastic walk, and one QQ that generates a quantum walk. The natural question to ask is whether these walks are related. The answer is that they are!

Underpinning this relationship is the mathematic property that SS and QQ are similar. They are related by the following similarity transformation

S=D 1/2QD 1/2 S = D^{1/2} Q D^{-1/2}

which means that any eigenvector ϕ k i\phi_k^i of QQ associated to eigenvalue ϵ k\epsilon_k implies that π k iD 1/2ϕ k i\pi_k^i \propto D^{1/2} \phi_k^i is an eigenvector of SS associated to the same eigenvalue. To show this, insert identity I=D 1/2D 1/2I = D^{-1/2} D^{1/2} into

Qϕ k i=ϵ kϕ k i Q \phi_k^i = \epsilon_k \phi_k^i

and multiply from the left with D 1/2 D^{1/2} to obtain

(D 1/2QD 1/2)(D 1/2ϕ k i) =ϵ k(D 1/2ϕ k i) Sπ k i =ϵ kπ k i \begin{aligned} (D^{1/2} Q D^{-1/2} ) (D^{1/2} \phi_k^i ) &= \epsilon_k ( D^{1/2} \phi_k^i ) \\ S \pi_k^i &= \epsilon_k \pi_k^i \end{aligned}

The same works in the opposite direction. Any eigenvector π k i\pi_k^i of SS implies an eigenvector ϕ k iD 1/2π k i\phi_k^i \propto D^{-1/2} \pi_k^i of QQ associated to the same eigenvalue ϵ k\epsilon_k.

The mathematics is also particularly nice because QQ is self-adjoint. A self-adjoint matrix is diagonalizable, and has real eigenvalues and orthogonal eigenvectors.

As a result, the symmetric normalized Laplacian can be decomposed as

Q= kϵ kΦ k Q = \sum_k \epsilon_k \Phi_k

where ϵ k\epsilon_k is real and Φ k\Phi_k are orthogonal projectors. Each Φ k\Phi_k acts as identity only on vectors in the space spanned by {ϕ k i} i\{ \phi_k^i \}_i and as zero on all others, such that Φ kΦ l=δ klΦ k\Phi_k \Phi_l = \delta_{k l} \Phi_k.

Multiplying from the left by D 1/2 D^{1/2} and the right by D 1/2 D^{-1/2} results in a similar decomposition for SS

S= kϵ kΠ k S = \sum_k \epsilon_k \Pi_k

with orthogonal projectos Π k=D 1/2Φ kD 1/2\Pi_k = D^{1/2} \Phi_k D^{-1/2} .

We now have all the ingredients necessary to study the walks generated by the normalized Laplacians and discover the relationship between them. I promised above that I would explain the following diagram

Diagram outlining the main concepts (again)

Let’s summarize what it represents now:

GG is a simple graph that specifies

AA the adjacency matrix (generator of a quantum walk), which subtracted from

DD the diagonal matrix of the degrees gives

LL the symmetric Laplacian (generator of stochastic and quantum walks), which when normalized by DD returns both

SS the generator of the uniform escape stochastic walk and

QQ the quantum walk generator to which it is similar!

If this has only warmed you up, next I’ll talk you through the mathematics of the uniform escape stochastic walk SS 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 QQ.

Stochastic walk

The uniform escape stochastic walk generated by SS 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 LL, which is both infinitesimal stochastic and symmetric. Among other things, this means the rows of LL sum to zero

jL ij=0 \displaystyle{ \sum_j L_{i j} = 0 }

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

L1=0 L \mathbf{1} = 0

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

L1=(LD 1)(D1)=S(D1)=0 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

π=D1 iD ii \pi = \frac{D \mathbf{1}}{\sum_i D_{i i}}

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

We can check this holds for the graph drawn above, where π\pi is

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

which implies long-time probability 1/61/6 for nodes 11, 22 and 55, and 1/41/4 for nodes 33 and 44. Comparing this to the original graph

Illustration of a simple graph

this exactly reflects the arrangement of degrees, as we knew it must. Math works!

Quantum walk

Next up is the quantum walk generated by QQ. 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 SS and QQ.

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 ϕ i k\phi_i^k of QQ is a stationary state of the quantum walk (in puzzle 7, at the bottom of this page, I ask you to prove this). The stationary state ϕ 0\phi_0 is of particular interest physically and mathematically. Physically, since eigenvectors of the QQ correspond to states of well-defined energy equal to the associated eigenvalue, ϕ 0\phi_0 is the state of lowest energy ϵ 0=0\epsilon_0 = 0, hence the name ground state (in puzzle 5 we ask you to prove that all eigenvalues of QQ are non-negative, so zero really does correspond to the ground state).

Mathematically, the relationship between eigenvectors implied by the similarity of SS and QQ means ϕ 0D 1/2πD 1/21 \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 ii is |i,ϕ 0| 2|i,D 1/2| 2=D ii| \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 i,π\langle i , \pi \rangle, the probability in the stationary state π\pi of the stochastic walk.

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

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 PP.

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 ii would be the long-time average probability

i,P=lim T1T 0 T|ψ i(t)| 2dt \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= kϵ kΦ kQ= \sum_k \epsilon_k \Phi_k into ψ(t)=e Qtψ(0) \psi(t) = e^{-Q t} \psi(0) to get ψ(t)= ke ϵ ktΦ kψ(0) \psi(t) = \sum_k e^{-\epsilon_k t} \Phi_k \psi(0) and thus

i,P=lim T1T 0 T| ke iϵ kti,Φ kψ(0)| 2dt \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

i,P= k|i,Φ kψ(0)| 2 \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 |i,Φ 0ψ(0)| 2| \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 ϕ 0\phi_0. This means that the projector is just the usual outer product

Φ 0=|ϕ 0ϕ 0|=ϕ 0ϕ 0 \Phi_0 = | \phi_0 \rangle \langle \phi_0 | = \phi_0 \phi_0^\dagger

where we have normalized ϕ 0\phi_0 according to the inner product ϕ 0,ϕ 0=1\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

|i,Φ 0ψ(0)| 2=|i,ϕ 0ϕ 0,ψ(0)| 2=|i,ϕ 0| 2|ϕ 0,ψ(0)| 2=i,π|ϕ 0,ψ(0)| 2 | \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 i,π\langle i , \pi \rangle for a quantum state in the zero energy eigenspace to be at node ii (as we found above) and second the probability |ϕ 0,ψ(0)| 2| \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 PP into a sum of two normalized probability vectors

P=(1η)π+ηΩ 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

i,Ω= k0|i,Φ kψ(0)| 2η \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

η=1|ϕ 0,ψ(0)| 2 \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 PP of the quantum walk is to the corresponding stochastic stationary distribution π\pi. What do we mean by close? Find out for yourself:

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

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

Because the eigenvalues of QQ 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 Δ=min k0ϵ k\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 EE of the quantum walker must bound the quantumness EηΔ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.

What next?

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.

In other news

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:

TODO Should we add their full names?

• G. D. Paparo and M. A. Martin-Delgado, Google in a Quantum Network, Sci. Rep. 2 (2012), 444.

• E. Sánchez-Burillo, J. Duch, J. Gómez-Gardenes and D. 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:

• S. Garnerone, P. Zanardi and D. 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.

Background reading

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.

Puzzles for the enthusiastic

Stochastic walks and stationary states

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 4. (For the hard core) Prove there is always a unique positive eigenvector for a stochastic walk generated by SS. You’ll need the assumption that the graph GG 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 5. Show that the eigenvalues of SS (and therefore QQ) are non-negative i.e. ϵ k0\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+Imax iS iiM = - S + I \max_i S_{i i}. This means MM has a positive eigenvalue rr equal to its spectral radius (r=max k|λ k|r = \max_k | \lambda_k | where {λ k} k\{ \lambda_k \}_k are the eigenvalues of MM), and the associated eigenvector vv is positive. Since S=M+Imax iS iiS = - M + I \max_i S_{i i}, it follows that SS shares the eigenvectors of MM and the associated eigenvalues are related by inverted translation ϵ k=λ k+max iS ii\epsilon_k = - \lambda_k + \max_i S_{i i}.

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

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

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

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

Quantum walks

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

UGH - A BUG Puzzle 7. 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= kϵ kΦ kQ= \sum_k \epsilon_k \Phi_k into the quantum evolution matrix e Qt e^{-Q t} show that if ψ(0)=ϕ i k\psi(0) = \phi_i^k then ψ(t)=e iϵ ktψ(0) \psi(t) = e^{ - i \epsilon_k t} \psi(0) , hence ϕ i k\phi_i^k is a stationary state as probabilities don’t change in time.

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