20.500.12556/DiRROS-23885 Quantum computing and the stable set problem Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In this paper, we solve the stable set problem using the D-Wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show its optimal value equals the graph's stability number for specific penalty values. However, D-Wave's quantum annealer is a heuristic, so the solutions may be far from the optimum and may not represent stable sets. To address these, we introduce a post-processing procedure that identifies samples that could lead to improved solutions. Additionally, we propose a partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the partitioning method successfully extends our approach to medium-size instances. stable set problem quantum annealing graph partitioning D-Wave kvantno žarenje problem deljenja grafa problem največje neodvisne množice D-Wave true false true Taylor & Francis Group Angleški jezik Slovenski jezik © 2025 The Author(s) Neznano 2025-10-17 03:49:21 2025-11-13 13:13:02 2025-11-14 03:41:04 0000-00-00 00:00:00 2025 0 0 Nasl. z nasl. zaslona; Opis vira z dne 16. 10. 2025; str. 837-870 iss. 4 Vol. 40 2025 0000-00-00 Zaloznikova VTisku NiDoloceno 2025-05-22 2025-03-12 2025-05-21 51 Y506-0494 10.1080/10556788.2025.2490639 253384707 https://www.tandfonline.com/doi/full/10.1080/10556788.2025.2490639 1 80b83861-aafb-11f0-9bb7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=35432 RAZ_Krpan_Aljaz_2025.pdf RAZ_Krpan_Aljaz_2025.pdf 1 FFA08541E4615E24ADFBC1D222DDDF75 8e64b834ce40333b3ef23415c5140a29e9ef53014ba71975609db11f55495906 137706ff-c08a-11f0-94a7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=35878 Rudolfovo – Znanstveno in tehnološko središče Novo mesto 0 0 0