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

摘要

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