Journal of University of Science and Technology of China ›› 2020, Vol. 50 ›› Issue (12): 1507-1515.DOI: 10.3969/j.issn.0253-2778.2020.12.008

• Research Article • Previous Articles     Next Articles

Quantum algorithms for ranking nodes of network

  

  1. 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
  • Received:2020-10-18 Accepted:2020-11-02 Online:2020-12-30 Published:2021-03-04
  • Contact: 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. .
  • About author: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.
  • Supported by:

    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).

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.

Key words: network ranking, adaptive physical model, penalty function minimizing, quantum linear

CLC Number: