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

Conference paper (2022)

Authors

Christoph Roch Ludwig Maximilians University
David Winderl Ludwig Maximilians University
Claudia Linnhoff-Popien Ludwig Maximilians University
S. Feld Quantum Circuit Architectures and Technology - EEMCS , Quantum & Computer Engineering
Research Group
Quantum Circuit Architectures and Technology (EEMCS) (TU Delft)
Copyright: © 2022 Christoph Roch, David Winderl, Claudia Linnhoff-Popien, S. Feld
DOI: https://doi.org/10.1007/978-3-031-06668-9_21
Optimization Heuristic D-wave systems MAX-SMTI Quantum annealing Stable marriage problem
More Info
expand_more

Published Date

2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Quantum & Computer Engineering

Research Group

Quantum Circuit Architectures and Technology

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.