Centrality measure based on continuous-time quantum walks and experimental realization

Network centrality has important implications well beyond its role in physical and information transport analysis; as such, various quantum-walk-based algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuous-time quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scale-free and Erdős-Rényi networks. As a proof of concept, the algorithm is detailed on a four-vertex star graph and physically implemented via linear optics, using spatial and polarization degrees of freedoms of single photons. This paper reports a successful physical demonstration of a quantum centrality algorithm.

Figure 1

Four-vertex star graph.

Figure 2

CTQW probability at vertex 0 (solid black curve) and vertices 1, 2, and 3 (dashed red curve) on a four-vertex star graph. The initial state is an equal superposition of all vertex states. Dotted horizontal lines show the respective long-time averaged probabilities of the respective vertices, with the vertical blue line denoting one period ($T=\pi /\sqrt{3}$).

Figure 3

Left: Randomly generated Erdős-Rényi graph $G(20,0.3)$. Right: Normalized vertex centrality values for vertex $j$ on $G(20,0.3)$. Measures shown are the degree centrality, PageRank, eigenvector centrality, CTQW centrality, and RWC centrality.

Figure 4

The average CTQW centrality measure compared to classical centrality measures for vertices in an ensemble of 200 Erdős-Rényi graphs (left) and 200 scale-free graphs (right). The Erdős-Rényi graphs have parameters $N=100$, $p=0.3$. The scale-free networks are constructed via the Barabási-Albert algorithm with $N=100$ and $m=2$ edges added at every generation. The shaded areas represent one standard deviation from the average centralities, and the top five ranked vertices are shown by the symbols.

Figure 5

Charts showing the agreement between the CTQW centrality ranking and (a) the PageRank and (b) the eigenvector centrality ranking for an ensemble of 100 Erdős-Rényi and 100 scale-free graphs. Each bar represents the unordered set containing the $n$ most central vertices as determined by the PageRank and CTQW measures, while the vertical axis gives the average fraction of matching vertices between the two sets. Error bars indicate the Agresti-Coull 95% confidence interval.

Figure 6

The quantum circuit for implementing the $4\times 4$ unitary transformation $U$ on a two-qubit system.

Figure 7

Conceptual experimental setup, with three controlled unitary transformations, $\mathbb{L}$, $\mathbb{S}$, and $\mathbb{R}$. Red lines represent the optical modes (beams) of single photons. (a) Realization of $\mathbb{L}$ ($\mathbb{R}$) as a transformation on two spatial modes and two polarization modes of single photons. The spatial mode works as the control qubit and the $2\times 2$ unitary transformation $L$ ($R$) and $L^{\prime }$ ($R^{\prime }$) applied to the polarizations of the photons in different modes can be realized by a set of wave plates. A phase shifter is used to keep the global phase unchanged during the transformation. (b) Realization of $\mathbb{S}$. The polarization is the control qubit. After the first HWP at ${45}^{\circ }$ and a BD, the horizontally polarized photons in both spatial modes are propagating in the same spatial mode (the middle one) and then the transformation $S$ is applied by using an HWP at $\theta /2$ in the middle mode. Meanwhile, the vertically polarized photons in upper or lower modes are not affected, and after the second BD they are still propagating in upper or low modes. The other HWPs are all set to ${45}^{\circ }$; they are used to flip the polarizations and to change the propagating modes of photons after they pass through the BD.

Figure 8

Practical experimental setup with consideration of both compensation of optical delay between different spatial modes and simplification. BBO, $\beta$-barium-borate; BD, beam displacer; HWP, half-wave plate; IF, interference filter; PBS, polarizing beam splitter; QWP, quarter-wave plate.

Figure 9

Photon probability distributions after eight unitary transformations. Red bars represent experimental results. Blue borders represent theoretical predictions. Errors are estimated via propagated Poissonian statistics. A small additional uncertainty may be present in the measurement of nodes 0 and 1 due to the photon's representing the two states with different polarizations but inhibiting the same spatial mode.