Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing

• URL: http://arxiv.org/abs/2301.05146v1
• Date: Thu, 12 Jan 2023 17:01:44 GMT
• Title: Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing
• Authors: Sven Fiergolla, Kevin Goergen, Patrick Neises, Petra Wolf
• Abstract summary: The framework of diversity of solutions is a young and thriving topic in the field of artificial intelligence. We use a quantum annealer to solve the Kemeny Rank Aggregation problem and to compute a representative set of solutions. We describe how KRA instances can be solved by a quantum annealer and provide an implementation as well as experimental evaluations.
• Score: 1.0323063834827415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Kemeny Rank Aggregation (KRA) problem is a well-studied problem in the field of Social Choice with a variety of applications in many different areas like databases and search engines. Intuitively, given a set of votes over a set of candidates, the problem asks to find an aggregated ranking of candidates that minimizes the overall dissatisfaction concerning the votes. Recently, a diverse version of KRA was considered which asks for a sufficiently diverse set of sufficiently good solutions. The framework of diversity of solutions is a young and thriving topic in the field of artificial intelligence. The main idea is to provide the user with not just one, but with a set of different solutions, enabling her to pick a sufficiently good solution that satisfies additional subjective criteria that are hard or impossible to model. In this work, we use a quantum annealer to solve the KRA problem and to compute a representative set of solutions. Quantum annealing is a meta search heuristic that does not only show promising runtime behavior on currently existing prototypes but also samples the solutions space in an inherently different way, making use of quantum effects. We describe how KRA instances can be solved by a quantum annealer and provide an implementation as well as experimental evaluations. As existing quantum annealers are still restricted in their number of qubits, we further implement two different data reduction rules that can split an instance into a set of smaller instances. In our evaluation, we compare classical heuristics that allow to sample multiple solutions such as simulated annealing and local search with quantum annealing performed on a physical quantum annealer. We compare runtime, quality of solution, and diversity of solutions, with and without applying preceding data reduction rules.

Related papers

• Quantum Algorithms for Drone Mission Planning [0.0]
  Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. We investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods.
  arXiv  Detail & Related papers  (2024-09-27T10:58:25Z)
• Validation and benchmarking of quantum annealing technology [0.0]
  This thesis focuses on the problem of benchmarking and validating quantum annealers. We propose two algorithms for solving real-world problems and test how they perform on the current generation of quantum annealers.
  arXiv  Detail & Related papers  (2023-12-06T14:56:45Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
  arXiv  Detail & Related papers  (2023-10-18T17:59:45Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Multi-Label Quantification [78.83284164605473]
  Quantification, variously called "labelled prevalence estimation" or "learning to quantify", is the supervised learning task of generating predictors of the relative frequencies of the classes of interest in unsupervised data samples. We propose methods for inferring estimators of class prevalence values that strive to leverage the dependencies among the classes of interest in order to predict their relative frequencies more accurately.
  arXiv  Detail & Related papers  (2022-11-15T11:29:59Z)
• Quantum-Assisted Greedy Algorithms [1.5049442691806054]
  We show how to leverage quantum annealers (QAs) to better select candidates in greedy algorithms. We use QAs that sample from the ground state of problem-dependent Hamiltonians at cryogenic temperatures.
  arXiv  Detail & Related papers  (2022-08-03T13:09:17Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Sampling diverse near-optimal solutions via algorithmic quantum annealing [0.3506539188356145]
  One of the main open problems is the lack of ergodicity, or mode collapse, for typical Monte Carlo solvers. Here, we introduce a new diversity measure for quantifying the number of independent approximate solutions for NP-hard optimization problems.
  arXiv  Detail & Related papers  (2021-10-20T13:33:37Z)
• Diversity metric for evaluation of quantum annealing [1.0499611180329802]
  It is not known how well quantum solvers sample the configuration space in comparison to their classical counterparts. We use time-to-diversity as a metric for evaluation of meta-heuristics solvers. This suggests that a portfolio solver that combines quantum and classical solutions may win over all solvers.
  arXiv  Detail & Related papers  (2021-10-19T18:37:01Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)

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.