Continuous-time quantum-walk spatial search on the Bollobás scale-free network

Abstract

The scale-free property emerges in various real-world networks and is an essential property that characterizes the dynamics or features of such networks. In this work, we investigate the effect of this scale-free property on a quantum information processing task of finding a marked node in the network, known as the quantum spatial search. We analyze the quantum spatial search algorithm using a continuous-time quantum walk on the Bollob\'as network, and we evaluate the time $T$ to localize the quantum walker on the marked node starting from an unbiased initial state. Our main finding is that $T$ is determined by the global structure around the marked node, while some local information of the marked node, such as the degree, does not identify $T$. We discuss this by examining the correlation between $T$ and some centrality measures of the network, and we show that the closeness centrality of the marked node is highly correlated with $T$. We also characterize the distribution of $T$ by marking different nodes in the network, which displays a multimode log-normal distribution. Especially on the Bollob\'as network, $T$ is a few orders of magnitude shorter depending on whether the marked node is adjacent to the largest degree hub node. However, as $T$ depends on the property of the marked node, one requires some amount of prior knowledge about such a property of the marked node in order to identify the optimal time to measure the quantum walker and achieve a fast search. These results indicate that the existence of the hub node in the scale-free network plays a crucial role in the quantum spatial search.