Title
A Quantum Annealing Approach for Solving Hard Variants of the Stable Marriage Problem
Author
Roch, Christoph (Ludwig Maximilians University)
Winderl, David (Ludwig Maximilians University)
Linnhoff-Popien, Claudia (Ludwig Maximilians University)
Feld, S. (TU Delft Quantum & Computer Engineering; TU Delft Quantum Circuit Architectures and Technology) 
Contributor
Phillipson, Frank (editor)
Eichler, Gerald (editor)
Erfurth, Christian (editor)
Fahrnberger, Günter (editor)
Department
Quantum & Computer Engineering
Date
2022
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.
Subject
D-wave systems
Heuristic
MAX-SMTI
Optimization
Quantum annealing
Stable marriage problem
To reference this document use:
http://resolver.tudelft.nl/uuid:89f54fdb-511f-42da-b581-b68157d7431a
DOI
https://doi.org/10.1007/978-3-031-06668-9_21
Publisher
Springer
Embargo date
2023-07-01
ISBN
9783031066672
Source
Innovations for Community Services - 22nd International Conference, I4CS 2022, Proceedings
Event
22nd International Conference on Innovations for Community Services, I4CS 2022, 2022-06-13 → 2022-06-15, Delft, Netherlands
Series
Communications in Computer and Information Science, 1865-0929, 1585 CCIS
Bibliographical note
Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
Part of collection
Institutional Repository
Document type
conference paper
Rights
© 2022 Christoph Roch, David Winderl, Claudia Linnhoff-Popien, S. Feld