基于自适应物理模型的量子网络排序算法  

Quantum algorithms for ranking nodes of network

作　　者：卢斌汉 韩永建 吴玉椿[1,2] 李叶 安宁波[3] 窦猛汉 赵东一 郭国平 Lu Binhan;Han Yongjian;Wu Yuchun;Li Ye;An Ningbo;Dou Menghan;Zhao Dongyi;Guo Guoping(CAS Key Laboratory of Quantum Information,School of Physics,University of Science and Technology of China,Hefei 230026 China;CAS Center For Excellence in Quantum Information and Quantum Physics,University of Science and Technology of China,Hefei 230026,China;Origin Quantum Computing Technology Company Limited,Hefei 230026,China)

机构地区：[1]中国科学技术大学物理学院中科院量子信息重点实验室,安徽合肥230026 [2]中国科学技术大学中科院量子信息与量子科技创新研究院,安徽合肥230026 [3]合肥本源量子计算科技有限责任公司,安徽合肥230026

出　　处：《中国科学技术大学学报》2020年第12期1507-1515,共9页JUSTC

基　　金：the National Key Research and Development Program of China(973 Program)(No.2016YFA0301700);the Anhui Initiative in Quantum Information Technologies(No.AHY080000).

摘　　要：对网络节点进行排序是复杂网络分析的核心问题之一.提出了一种改进的SpringRank算法.该算法基于一个把节点之间连接视为静止长度可变的弹簧的自适应物理模型,并基于此定义一个新型罚函数.通过最小化罚函数,该算法可以对有向和加权复杂网络的节点进行排序.为了避免经典算法中计算复杂度随着节点数量的增加而过快增加的情况,使用量子算法加速罚函数最小化过程.罚函数的凸性使我们能够通过求解线性系统的方式找到最小值.当线性系统具有稀疏且条件数较小的性质时,使用量子线性求解器HHL算法找到罚函数的最小值.如果线性系统没有这两个性质,则使用量子虚时演化QITE算法通过迭代方法找到最小值.最后,使用量子模拟器QPanda对多个网络用所提出的两种求最小值算法进行了节点排序测试,实验结果显示两种算法都能给出正确的排序结果.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.

关 键 词：网络节点排序 自适应物理模型 最小化罚函数 量子线性方程求解器 量子虚时演化 

分 类 号：TP3-05[自动化与计算机技术—计算机科学与技术] TP399