气候变化领域集成服务门户(CCPortal): TensorFlow solver for quantum PageRank in large-scale networks

CCPortal

DOI	10.1016/j.scib.2020.09.009
	TensorFlow solver for quantum PageRank in large-scale networks
	Tang H.; Shi R.; He T.-S.; Zhu Y.-Y.; Wang T.-Y.; Lee M.; Jin X.-M.
发表日期	2021
ISSN	20959273
起始页码	120
结束页码	126
卷号	66 期号:2
英文摘要	Google PageRank is a prevalent algorithm for ranking the significance of nodes or websites in a network, and a recent quantum counterpart for PageRank algorithm has been raised to suggest a higher accuracy of ranking comparing to Google PageRank. The quantum PageRank 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(N4) dimension and requires severely large memory and time when the number of nodes N in a network increases above 150. Here, we present an efficient solver for quantum PageRank by using the Runge-Kutta method to reduce the matrix dimension to O(N2) and employing TensorFlow to conduct GPU parallel computing. We demonstrate its performance in solving quantum stochastic walks on Erdös-Rényi graphs using an RTX 2060 GPU. The 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 s. Compared 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 PageRank for the USA major airline network with up to 922 nodes, and to quantum stochastic walk on a glued tree of 2186 nodes. This efficient solver for large-scale quantum PageRank and quantum stochastic walks would greatly facilitate studies of quantum information in real-life applications. © 2020 Science China Press
关键词	Lindblad master equation Quantum PageRank Quantum stochastic walk Runge-Kutta method TensorFlow GPU parallel computing
英文关键词	Graph structures; Quantum optics; Runge Kutta methods; Stochastic systems; GPU parallel computing; Kronecker product; Large-scale network; Lindblad master equation; Of quantum-information; PageRank algorithm; Quantum counterpart; Real-life applications; Quantum efficiency
语种	英语
来源期刊	Science Bulletin
文献类型	期刊论文
条目标识符	http://gcip.llas.ac.cn/handle/2XKMVOVA/207567
作者单位	Center for Integrated Quantum Information Technologies (IQIT), School of Physics and Astronomy and State Key Laboratory of Advanced Optical Communication Systems and Networks, Shanghai Jiao Tong University, Shanghai, 200240, China; CAS Center for Excellence and Synergetic Innovation Center in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei, 230026, China; School of Physical Science, University of Chinese Academy of Sciences, Beijing, 100049, China; Department of Physics, Cambridge University, Cambridge, CB3 0HE, United Kingdom
推荐引用方式 GB/T 7714	Tang H.,Shi R.,He T.-S.,et al. TensorFlow solver for quantum PageRank in large-scale networks[J],2021,66(2).
APA	Tang H..,Shi R..,He T.-S..,Zhu Y.-Y..,Wang T.-Y..,...&Jin X.-M..(2021).TensorFlow solver for quantum PageRank in large-scale networks.Science Bulletin,66(2).
MLA	Tang H.,et al."TensorFlow solver for quantum PageRank in large-scale networks".Science Bulletin 66.2(2021).