A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem

Christoph Roch*, David Winderl, Claudia Linnhoff-Popien, Sebastian Feld

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

The Stable Marriage Problem (SMP) describes the problem, of finding a stable matching between two equally sized sets of elements (e.g., males and females) given an ordering of preferences for each element. A matching is stable, when there does not exist any match of a male and female which both prefer each other to their current partner under the matching. Finding such a matching of maximum cardinality, when ties and incomplete preference lists are allowed, is called MAX-SMTI and is an NP-hard variation of the SMP. In this work a Quadratic Unconstrained Binary Optimization (QUBO) formulation for MAX-SMTI is introduced and solved both with D-Wave Systems quantum annealing hardware and by their classical meta-heuristic QBSolv. Both approaches are reviewed against existing state-of-the-art approximation algorithms for MAX-SMTI. Additionally, the proposed QUBO problem can also be used to count stable matchings in SMP instances, which is proven to be a #P-complete problem. The results show, that the proposed (quantum) methods can compete with the classical ones regarding the solution quality and might be a relevant alternative, when quantum hardware scales with respect to the number of qubits and their connectivity.

Original languageEnglish
Title of host publicationInnovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings
EditorsFrank Phillipson, Gerald Eichler, Christian Erfurth, Günter Fahrnberger
PublisherSpringer Science and Business Media Deutschland GmbH
Pages294-307
Number of pages14
ISBN (Print)9783031066672
DOIs
Publication statusPublished - 2022
Event22nd International Conference on Innovations for Community Services, I4CS 2022 - Delft, Netherlands
Duration: 13 Jun 202215 Jun 2022

Publication series

NameCommunications in Computer and Information Science
Volume1585 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference22nd International Conference on Innovations for Community Services, I4CS 2022
Country/TerritoryNetherlands
CityDelft
Period13/06/2215/06/22

Keywords

  • D-wave systems
  • Heuristic
  • MAX-SMTI
  • Optimization
  • Quantum annealing
  • Stable marriage problem

Fingerprint

Dive into the research topics of 'A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem'. Together they form a unique fingerprint.

Cite this