A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem
Christoph Roch (Ludwig Maximilians University)
David Winderl (Ludwig Maximilians University)
Claudia Linnhoff-Popien (Ludwig Maximilians University)
S. Feld (TU Delft - Quantum Circuit Architectures and Technology, TU Delft - Quantum & Computer Engineering)
More Info
expand_more
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.
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.