Quantum algorithms for ranking nodes of network

LU Binhan; HAN Yongjian; WU Yuchun; LI Ye; AN Ningbo; DOU Menghan; ZHAO Dongyi; GUO Guoping

doi:10.3969/j.issn.0253-2778.2020.12.008

PDF( 1296 KB)

Open Access JUSTC Research Article

Quantum algorithms for ranking nodes of network

1.
CAS Key Laboratory of Quantum Information, School of Physics, University of Science and Technology of China, Hefei 230026 China
2.
CAS Center For Excellence in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China
3.
Origin Quantum Computing Technology Company Limited, Hefei 230026, China

Funds: This work is supported by the National Key Research and Development Program of China (973 Program) ( No. 2016YFA0301700) and the Anhui Initiative in Quantum Information Technologies (No. AHY080000).

Cite this:

https://doi.org/10.3969/j.issn.0253-2778.2020.12.008

More Information

Author Bio:
Lu Binhan is a postgraduate student under the supervision of Prof. Wu Yuchun at University of Science and Technology of China(USTC) . He receive his B. S. degree in Applied Physics from Jinan University(JNU) in 2019. He mainly focuses on the optimization of quantum algorithm compilation.
Corresponding author: Guo Guoping is professor and doctoral supervisor of University of Science and Technology of China, deputy director of Key Laboratory of Quantum Information of Chinese Academy of Sciences, vice president of Institute of Microelectronics of University of Science and Technology of China, and research leader of semiconductor quantum dot quantum chip of University of Science and Technology of China. Chief scientist of National Key Basic Research and Development Program Class A ( Super 973 ), winner of national fund for Distinguished Young Scholars. Founder and chief scientist of Origin Quantum Computing Technology Co. , Ltd. .
Received Date: 18 October 2020
Accepted Date: 02 November 2020
Publish Date: 30 December 2020

Abstract Full text PDF

Abstract

Abstract

Ranking the node of a network is one of the central problems in a complex network. Here, An improved SpringRank method was proposed that builds an adaptive physical model with variable-spring connected between nodes and a novel penalty function. By minimizing the penalty function, the method can rank the nodes of a directed and weighted complex network. To decrease the computation complexity which increases too fast with the number of nodes, quantum algorithms were used to speed up the process of minimizing the penalty functions. The convexity enables us to find the minimum by solving a linear system. When the linear system has the properties of sparsity and a small conditional number, we use the HHL algorithm to find the minimum of the penalty function by solving the linear equation. And we use the QITE algorithm to find the minimum by updating the parameters iteratively when the linear system doesn’ t have those properties. Lastly, using the quantum simulator QPanda, we implemented the algorithms for several networks and gave the right ranking results.

Abstract

Ranking the node of a network is one of the central problems in a complex network. Here, An improved SpringRank method was proposed that builds an adaptive physical model with variable-spring connected between nodes and a novel penalty function. By minimizing the penalty function, the method can rank the nodes of a directed and weighted complex network. To decrease the computation complexity which increases too fast with the number of nodes, quantum algorithms were used to speed up the process of minimizing the penalty functions. The convexity enables us to find the minimum by solving a linear system. When the linear system has the properties of sparsity and a small conditional number, we use the HHL algorithm to find the minimum of the penalty function by solving the linear equation. And we use the QITE algorithm to find the minimum by updating the parameters iteratively when the linear system doesn’ t have those properties. Lastly, using the quantum simulator QPanda, we implemented the algorithms for several networks and gave the right ranking results.