Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers

• URL: http://arxiv.org/abs/2407.20452v3
• Date: Tue, 29 Oct 2024 00:13:19 GMT
• Title: Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
• Authors: Caesnan M. G. Leditto, Angus Southwell, Behnam Tonekaboni, Muhammad Usman, Kavan Modi,
• Abstract summary: HodgeRank generalizes ranking algorithms to rank alternatives based on real-world (often incomplete) data using graphs and discrete exterior calculus. We develop a quantum algorithm that approximates the HodgeRank solution with complexity independent of dimension.
• Score: 0.5490714603843316
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: HodgeRank generalizes ranking algorithms, e.g. Google PageRank, to rank alternatives based on real-world (often incomplete) data using graphs and discrete exterior calculus. It analyzes multipartite interactions on high-dimensional networks with a complexity that scales exponentially with dimension. We develop a quantum algorithm that approximates the HodgeRank solution with complexity independent of dimension. Our algorithm extracts relevant information from the state such as the ranking consistency, which achieves a superpolynomial speedup over similar classical methods.

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)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• 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)
• Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
  We introduce a quantum-control-inspired method for the characterization of variational quantum circuits using the rank of the dynamical Lie algebra. A promising connection is found between the Lie rank, the accuracy of calculated energies, and the requisite depth to attain target states via a given circuit architecture.
  arXiv  Detail & Related papers  (2022-09-28T20:24:53Z)
• Quantum density peak clustering [5.8010446129208155]
  We introduce a quantum version of the density peak clustering algorithm, built upon a quantum routine for minimum finding. We prove a quantum speedup for a decision version of density peak clustering depending on the structure of the dataset.
  arXiv  Detail & Related papers  (2022-07-21T15:58:40Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Quantum Ensemble for Classification [2.064612766965483]
  A powerful way to improve performance in machine learning is to construct an ensemble that combines the predictions of multiple models. We propose a new quantum algorithm that exploits quantum superposition, entanglement and interference to build an ensemble of classification models.
  arXiv  Detail & Related papers  (2020-07-02T11:26:54Z)
• 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.