Growing Random Graphs with Quantum Rules

The intrinsic randomness of quantum physics can be exploited to generate “truly random” numbers. If a system is prepared in a superposition of basis states, a measurement outcome in that basis is intrinsically random. Such genuine randomness, which cannot be achieved with only classical means, has an important role in several fields such as cryptography [16] and simulations [14].

In this work we harness quantum randomness for generating random graphs. Our motivation is that a large variety of real systems, from natural to socioeconomic phenomena [18], protein-protein interactions [20], the brain [17], the internet [22], financial trading [19], and many other dynamical systems can be described by random graphs. Moreover, the random collapse of the wave function of the quantum walker that is built into our models is reminiscent of the spontaneous collapse theories in quantum mechanics [12].

Although there are various ways to construct such discrete structures [6, 11], for most of them it is difficult to certify randomness based solely on the observed random graph states [13]. On the other hand, the intrinsic randomness that emerges from measuring a quantum system in superposition of states can be used to give guarantees on the randomness of a graph. Quantum walks on graphs are well-known [2] and already lend themselves to many applications, including search algorithms [9], element distinctness [3] and isomorphism tests [7], discretization of differentiable surfaces [4, 5] and cryptography [21]. Quantum walks are a natural choice in our models, and can be seen as the quantum counterpart of classic random walks which have been defined on all kinds of grids, in continuous and discrete time [10].

Here we propose an original application of Quantum Walks on graphs to the problem of random graph generation. In our models, the quantum system is given by one or more quantum walkers that evolve continuously on the graph. Then, a measurement operation or a spontaneous collapse of the walker guides the evolution of the graph’s adjacency matrix over time.

We will present two models. The first can grow random trees and is based on a single quantum walk, while the second can grow general graphs and is based on two walkers.

The manuscript is organized as follows: we will first present our two models in sections II and III. Then we will present a few numerical experiments where we grow random graphs and analyze various metrics and how they depend on the average collapse time.

To support the numerical explorations in this manuscript and to promote reproducibility, we have developed an open source python library [15].

We first look at the degree distribution. For each degree $k$ we compute the fraction $d(k)$ of nodes on the graph that has $k$ connections. By studying the degree distribution, we can get an indication of whether our models generate scale-free networks i.e. whose degree distribution follows a power-law $d(k)=k^{-\alpha}$. We compute the average degree distribution for the first model, with 1000 and 100 nodes. We find that the degree distribution seems to converge, for large $\tau$, to a power law, as shown in Fig. 5.

Next we turn to the diameter of the graphs. To compute the diameter of a graph we compute the maximum value of the shortest path between every pair of edges. As we can see in Fig. 6, the diameter dependence on time depend on the number of walkers and is maximal for $0.1<\tau<1$.

We observe an interesting phenomenon when we compute the fraction of nodes that live on the edge of the graphs. We define this as the “leaf fraction”, i.e. the fraction of nodes with only one neighbor. As can be seen in Fig. 7, the leaf fraction decreases with $\tau$ until it becomes stable from around $\tau\approx 1$. This effect seems to be independent of the size of the graphs, and we conjecture that is a universal property of this model.

Finally, we compute the average clustering coefficient. The local clustering coefficient of a node is a measure of how much its neighbors are linked to each other. It is a coefficient introduced by Watts and Strogatz in [23] to find whether a graph exhibits the small-world property.

To define the clustering coefficient, we need to define what is the neighborhood of a node in a graph. The neighborhood $N_{i}$ of a node $i$ is defined as the set of all its neighbors. Let $G=(V,E)$ be a graph of $n$ nodes with $V=[\![1,n]\!]$ and $E$ the set of couples $(i,j)$ if there’s a link between the nodes $i$ and $j$. Then we define the local clustering coefficient of the node $i$ which has $n_{i}$ neighbors as $C_{i}=\frac{2|\left\{(j,k)\;j,k\in N_{i},(j,k)\in E\right\}|}{n_{i}(n_{i}-1)}$ for an undirected graph. Finally, we obtain the graph’s average clustering coefficient : $C=\frac{1}{n}\sum_{i=1}^{n}C_{i}$. We can notice that the clustering coefficient decreases rapidly for large $\tau$ and seems to be independent on the number of walkers, with the only exception of the single-walker model.

We have presented two new models for growing random graphs, that are driven by the continuous evolution of quantum walkers and by spontaneous collapses of their wave function. We have numerical evidence that the random graphs that result from these models display a power-law degree of distribution, which indicates a scale-free structure.

We also have found two interesting phenomena in the average graph diameter and in the fraction of nodes that live on the edge. An average collapse time of $\tau\approx 1$ seems to play a special role, while for $\tau\gg 1$ it seems to lead the measures to relax to an asymptotic value. In particular, the leaf fraction is a quantity that seems to give us information about the bulk of a graph from its surface, which is reminiscent of the holographic principle. We suspect that around $\tau\approx 1$ there could occur a first order phase transition, as Fig. 6 seems to suggest.

We note that as the wave function of the quantum walker can interfere with itself, the continuous-time quantum walk does not tend to a limiting distribution (which instead is characteristic of classical random walks). This might result in fundamental differences between classical and quantum models that are not possible to reconcile. Moreover, we note that as the off-diagonal elements of the adjacency matrix are never negative, the Hamiltonian that it represents is “stoquastic” [8] and therefore the evolution of the walker should not be exponentially hard to compute. Because of this, it could be that even if these growth models were not reproducible by classical random walk models, they could be reside in an efficient class of computational complexity.

Among the directions of future work one could introduce an additional degree of freedom in terms of a quantum coin, similarly to what is done in discrete-time quantum walks. Another possible perspective is to explore the possibility to perform quantum search algorithms over growing random graphs, for example by combining multiple walkers where e.g. two of them are in charge of growing the graph and a third performs the search while preserving its unitarity. Our hope is that this will produce “optimized” random graphs for the objective that the walker is searching for.