TensorFlow Solver for Quantum PageRank in Large-Scale Networks

• URL: http://arxiv.org/abs/2003.04930v1
• Date: Tue, 10 Mar 2020 18:58:15 GMT
• Title: TensorFlow Solver for Quantum PageRank in Large-Scale Networks
• Authors: Hao Tang, Tian-Shen He, Ruo-Xi Shi, Yan-Yan Zhu, Marcus Lee, Tian-Yu Wang, Xian-Min Jin
• Abstract summary: We present an efficient solver for quantum PageRank using the Runge-Kutta method to reduce the matrix dimension to O(N2) and employing parallel computing. Compared with the previous quantum PageRank solver, our solver dramatically reduces the required memory and time to only 1% and 0.2%, respectively, making it practical to work in a normal computer with a memory of 4-8 GB in no more than 100 seconds.
• Score: 12.937513443750804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Google PageRank is a prevalent and useful 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(N^4) 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(N^2) and employing TensorFlow to conduct GPU parallel computing. We demonstrate its performance in solving quantum PageRank for the USA major airline network with up to 922 nodes. Compared with the previous quantum PageRank solver, our solver dramatically reduces the required memory and time to only 1% and 0.2%, respectively, making it practical to work in a normal computer with a memory of 4-8 GB in no more than 100 seconds. This efficient solver for large-scale quantum PageRank and quantum stochastic walks would greatly facilitate studies of quantum information in real-life applications.

Related papers

• Quantum versatility in PageRank [6.797840514031587]
  arbitrary phase rotations (APR) have been introduced in the underlying Szegedy's quantum walk of quantum PageRank algorithm. We study the role APR plays in quantum PageRank and discover the resulting versatility from quantumness. Our results present the quantum-enabled perspective for PageRanking and shed light on the design and application of practical quantum PageRank algorithms.
  arXiv  Detail & Related papers  (2024-11-20T08:14:27Z)
• Discrete-Time Open Quantum Walks for Vertex Ranking in Graphs [0.0]
  This article presents a new quantum PageRank algorithm on graphs using discrete-time open quantum walks. Google's PageRank is an essential algorithm for arranging the web pages on the World Wide Web in classical computation.
  arXiv  Detail & Related papers  (2024-04-23T06:15:17Z)
• Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine [0.0]
  The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk.
  arXiv  Detail & Related papers  (2024-01-03T06:00:23Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Generalized Quantum Google PageRank Algorithm with Arbitrary Phase Rotations [0.0]
  We present a modification of the quantum PageRank introducing arbitrary phase rotations (APR) in the underlying Szegedy's quantum walk. We have analyzed the behavior of the new algorithms in a small generic graph, observing that a decrease of the phase reduces the standard deviation of the instantaneous PageRank. We have found that one of our new algorithms whose PageRank distribution resembles the classical one, has a stability similar to the original quantum algorithm.
  arXiv  Detail & Related papers  (2022-09-27T15:15:54Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Spatial search by continuous-time quantum walks on renormalized Internet networks [0.0]
  We study spatial search with continuous-time quantum walks on real-world complex networks. We infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network.
  arXiv  Detail & Related papers  (2022-05-04T15:46:14Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.