Generalized Quantum Google PageRank Algorithm with Arbitrary Phase Rotations

• URL: http://arxiv.org/abs/2209.13451v1
• Date: Tue, 27 Sep 2022 15:15:54 GMT
• Title: Generalized Quantum Google PageRank Algorithm with Arbitrary Phase Rotations
• Authors: Sergio A. Ortega, Miguel A. Martin-Delgado
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantization of the PageRank algorithm is a promising tool for a future quantum internet. Here we present a modification of the quantum PageRank introducing arbitrary phase rotations (APR) in the underlying Szegedy's quantum walk. We define three different APR schemes with only one phase as a degree of freedom. 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, so the nodes of the network can be distinguished better. However, the algorithm takes more time to converge, so the phase can not be decreased arbitrarily. With these results we choose a concrete value for the phase to later apply the algorithm to complex scale-free graphs. In these networks, the original quantum PageRank is able to break the degeneracy of the residual nodes and detect secondary hubs that the classical algorithm suppresses. Nevertheless, not all of the detected secondary hubs are real according to the PageRank's definition. Some APR schemes can overcome this problem, restoring the degeneration of the residual nodes and highlighting the truly secondary hubs of the networks. Finally, we have studied the stability of the new algorithms. The original quantum algorithm was known to be more stable than the classical. 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.

Related papers

• 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)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutsch's algorithm is the first quantum algorithm to show the advantage over the classical algorithm. We propose a new quantum algorithm with indefinite causal order to solve this problem.
  arXiv  Detail & Related papers  (2023-05-09T13:04:28Z)
• An adaptive Bayesian quantum algorithm for phase estimation [0.0]
  We present a coherence-based phase-estimation algorithm which can achieve the optimal quadratic scaling in the mean absolute error and the mean squared error. In the presence of noise, our algorithm produces errors that approach the theoretical lower bound.
  arXiv  Detail & Related papers  (2023-03-02T19:00:01Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• TensorFlow Solver for Quantum PageRank in Large-Scale Networks [12.937513443750804]
  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.
  arXiv  Detail & Related papers  (2020-03-10T18:58:15Z)

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.