TensorFlow solver for quantum Page Rank in large-scale networks

作     者：Hao Tang Ruoxi Shi Tian-Shen He Yan-Yan Zhu Tian-Yu Wang Marcus Lee Xian-Min Jin 唐豪;时若曦;何天深;朱炎炎;王天宇;Marcus Lee;金贤敏

作者机构：Center for Integrated Quantum Information Technologies(IQIT)School of Physics and Astronomy and State Key Laboratory of Advanced Optical Communication Systems and NetworksShanghai Jiao Tong UniversityShanghai 200240China CAS Center for Excellence and Synergetic Innovation Center in Quantum Information and Quantum PhysicsUniversity of Science and Technology of ChinaHefei 230026China School of Physical ScienceUniversity of Chinese Academy of SciencesBeijing 100049China Department of PhysicsCambridge UniversityCambridge CB30HEUK 

出 版 物：《Science Bulletin》 (科学通报（英文版）)

年 卷 期：2021年第66卷第2期

页      面：120-126,M0003页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Key R&D Program of China(2019YFA0308700,and 2017YFA0303700) the National Natural Science Foundation of China(61734005,11761141014,11690033) the Science and Technology Commission of Shanghai Municipality(STCSM)(17JC1400403) the Shanghai Municipal Education Commission(SMEC)(2019SHZDZX01,2017-01-07-0002-E00049) supported by the National Natural Science Foundation of China(11904229) China Postdoctoral Science Foundation(2019T120334) 

主　　题：Quantum stochastic walk Quantum PageRank Lindblad master equation TensorFlow GPU parallel computing Runge-Kutta method 

摘      要：Google Page Rank is a prevalent algorithm for ranking the significance of nodes or websites in a network,and a recent quantum counterpart for Page Rank algorithm has been raised to suggest a higher accuracy of ranking comparing to Google Page *** quantum Page Rank algorithm is essentially based on quantum stochastic walks and can be expressed using Lindblad master equation,which,however,needs to solve the Kronecker products of an O(N^(4))dimension and requires severely large memory and time when the number of nodes N in a network increases above ***,we present an efficient solver for quantum Page Rank by using the Runge-Kutta method to reduce the matrix dimension to O(N^(2))and employing Tensor Flow to conduct GPU parallel *** demonstrate its performance in solving quantum stochastic walks on Erdos-Rényi graphs using an RTX 2060 *** test on the graph of 6000 nodes requires a memory of 5.5 GB and time of 223 s,and that on the graph of 1000 nodes requires 226 MB and 3.6 *** with QSWalk,a currently prevalent Mathematica solver,our solver for the same graph of 1000 nodes reduces the required memory and time to only 0.2%and 0.05%.We apply the solver to quantum Page Rank for the USA major airline network with up to 922 nodes,and to quantum stochastic walk on a glued tree of 2186 *** efficient solver for large-scale quantum Page Rank and quantum stochastic walks would greatly facilitate studies of quantum information in real-life applications.