Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
arXiv:2407.20452 · doi:10.1103/m6nc-ypl7
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.
References in corpus (24)
- Quantum algorithm for solving linear systems of equations
- Higher-order organization of complex networks
- The physics of higher-order interactions in complex systems
- Dynamics on higher-order networks: A review
- Quantum Data Fitting
- The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
- What are higher-order networks?
- Explosive higher-order Kuramoto dynamics on simplicial complexes
- Preconditioned quantum linear system algorithm
- Topological Signal Processing over Simplicial Complexes
- Quantum algorithms and the finite element method
- GEMPIC: Geometric ElectroMagnetic Particle-In-Cell Methods
- Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
- Quantum Navigation and Ranking in Complex Networks
- Adiabatic quantum algorithm for search engine ranking
- The Simplex Tree: an Efficient Data Structure for General Simplicial Complexes
- Complex Quantum Networks: a Topical Review
- Analyzing Prospects for Quantum Advantage in Topological Data Analysis
- Simplicial Convolutional Filters
- Quantum Regularized Least Squares
- Circuit complexity of quantum access models for encoding classical data
- Finding Small and Large k-Clique Instances on a Quantum Computer
- Representation of the Fermionic Boundary Operator
- Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis