Scaling of Quantum Walks on Complex Networks

German Alamilla Peralta

Fei Yan, Wen Liang, Fangyan Dong

This chapter delineates potential research areas and challenges within the application domains of quantum walks and complex networks. These aspects entail the optimization of quantum walk computations on large-scale complex networks, the application of quantum walks across diverse types of complex networks, the exploration of quantitative relationships between quantum walk measurement outcomes and the statistical characteristics of complex networks, quantum walk algorithms for mining combined individuals within complex networks, and the requirement for a “dual-track” approach in the design of quantum walk algorithms on complex networks.

Ernesto Estrada, José Antonio de la Peña, Naomichi Hatano

Pranay Naredi, J. Bharathi Kannan, M. S. Santhanam

Zhengyi Wang, Feng Gao, Yuan Xu +2 more

Abstract Critical node identification is the precondition for exploring complex networks, which is a graph‐based optimal search problem in principle. Classical methods, hindered by limited parallel processing capabilities, often grapple with high computational demands and inefficiency. Recent studies have leveraged quantum walk (QW) to tackle such challenges. However, existing QW‐based approaches are constrained by graph structures and prone to recurrent traversal issues. Being different, a novel forward discrete‐time quantum walk (F‐DTQW) method is proposed, which can traverse without redundant visits by prohibiting reverse and lateral propagations. The proposed method significantly enhances the efficiency of critical node identification and is applicable to arbitrary complex networks. The proposed method is validated on typical complex networks such as small‐world, scale‐free, and directed networks, and calculates the transition probability of nodes, corresponding to the centrality measurement index of transition connectivity (TC), which expands from the betweenness centrality (BC) index. The time complexity of F‐DTQW is also analyzed, which is reduced from O ( N 3 ) to O ( N 2 ) compared to the classical method.

Anurag Kumar Singh, Binshumesh Sachan

Some interesting findings can be achieved by modeling and visualizing networks which can include complex networks and large scale networks to name a few. These networks have been analyzed with the help of classical stochastic walks before. So, here in our proposed work, we provide the quantum version of the walk which basically involves making use of properties found in quantum computing. These properties can include such as quantum interference, no-cloning theorem, and restriction on intermediate measurement. In this proposed work, we present quantum circuit designs for discrete time random walk algorithms that operate on various networks.To demonstrate our ideas we have considered two different types of networks, the star network and an extended version of the star network.Though there exist a few research works related to quantum approach for random walk on networks, to the best of our knowledge, the ideas and approach we present here are unique. These ideas which we have discussed can be extended to more complex networks and systems as well. As an application of quantum walk we have shown, how results got after performing quantum walk can be used to identify critical nodes in such networks. Therefore, we have also provided some analysis of complex networks. Identification of critical nodes is important for robustness and survivability of the network.