The Azimuth Project
Blog - quantum network theory (part 1)

This page is a blog article in progress, written by Tomi Johnson. Part 2 is found here. To see discussion of this article while it was being written, visit the Azimuth Forum. To read the final polished version, go to the Azimuth Blog.

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 in which 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.

I make a couple of references to part 2. Currently I don’t add any hyperlinks to the text, as I wouldn’t know where to link to. Let me know if I should do anything different. - Tomi

To begin studying quantum complex networks, we found a revealing toy model. Let me tell you about it. Like all good stories, it has a beginning, a middle and an end. In this part, I’ll tell you the beginning and the middle. I’ll introduce the stochastic walk describing the randomly clicking web surfer mentioned above and a corresponding quantum walk. In part 2 the story ends with the bounding of the difference between the two walks in terms of the energy of the walker.

But for now I’ll start by introducing you to 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, arXiv:1305.6078 (2013).

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 pair of articles.

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.

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.

This standout should appear OK on the blog, sorry for its current appearance. - 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.

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

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!

What next?

Sadly, this is where we’ll finish for now.

We have all the ingredients necessary to study the walks generated by the normalized Laplacians and exploit the relationship between them.

Next time, in part 2, 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.

In other news

Before I leave you, let me tell you about a workshop the ISI team recently attended (in fact helped organize) at IQC on the topic of quantum computation and 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!