科研之友
微信
新浪微博
Facebook
分享链接
摘要
Google Page Rank是对网络节点重要性进行排名的常见算法,而最近提出与之对应的量子排序算法,可提高排名准确性.量子排序算法基于量子随机行走,使用Lindblad主方程描述,直接求解需要计算O(N4)复杂度的Kronecker乘积,当网络节点数N增至150以上时,耗费极大的存储空间和运算时间.本文展示一种自主开发的高效量子排序求解器,运用Runge-Kutta方法将存储空间降为O(N2),并使用Tensor Flow进行GPU并行计算,降低运算时间.使用RTX 2060 GPU进行量子排序,求解6000个节点的Erd?s-Rényi图网络需5.5 GB内存和223 s.求解1000个节点Erd?s-Rényi图排序,本求解器需226 MB和3.6 s,与目前流行的Mathematica求解器QSWalk相比,仅为QSWalk求解同样问题所需内存的0.2%及用时的0.05%.将本求解器应用于包括922个主要机场的美国航线网络的机场排序,以及2186个节点的粘合树上的量子随机行走.这种用于大规模量子排序和量子随机行走的高效求解器将极大推动相关量子信息领域的研究.
- 单位
