Resolving degeneracies in Google search via quantum stochastic walks

• URL: http://arxiv.org/abs/2207.11429v2
• Date: Tue, 16 Jan 2024 16:37:56 GMT
• Title: Resolving degeneracies in Google search via quantum stochastic walks
• Authors: Colin Benjamin, Naini Dudhe
• Abstract summary: The PageRank algorithm is the backbone of Google search, ranking web pages according to relevance and recency. We employ quantum walks (QSWs) to improve the classical PageRank (CPR) algorithm based on classical continuous time walks. For some networks, the two QSW schemes obtain a convergence time lower than CPR and an almost degeneracy-free ranking compared to CPR.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The Internet is one of the most valuable technologies invented to date. Among them, Google is the most widely used search engine. The PageRank algorithm is the backbone of Google search, ranking web pages according to relevance and recency. We employ quantum stochastic walks (QSWs) to improve the classical PageRank (CPR) algorithm based on classical continuous time random walks. We implement QSW via two schemes: only incoherence and dephasing with incoherence. PageRank using QSW with only incoherence or QSW with dephasing and incoherence best resolves degeneracies that are unresolvable via CPR and with a convergence time comparable to that for CPR, which is generally the minimum. For some networks, the two QSW schemes obtain a convergence time lower than CPR and an almost degeneracy-free ranking compared to CPR.

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)
• Variational Quantum PageRank [0.0]
  PageRank is a graph-based algorithm that ranks pages based on how many other pages link to them. This work develops a variational quantum version of the PageRank algorithm and compares the performance of the two algorithms.
  arXiv  Detail & Related papers  (2023-04-19T23:49:32Z)
• 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)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  We propose a new algorithm selector leveraging special forests, combining the strengths of both approaches while alleviating their weaknesses. HARRIS' decisions are based on a forest model, whose trees are created based on optimized on a hybrid ranking and regression loss function.
  arXiv  Detail & Related papers  (2022-10-31T14:06:11Z)
• 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)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• 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.