solQHealer: Quantum Procedures for Rendering Infeasible Solutions Feasible: A Proof of Concept with the Maximum Independent Set Problem and 3-SAT

Samuel Deleplanque (), Luis Pérez Armas and Stefan Creemers ()
Additional contact information
Samuel Deleplanque: ACOUSTIQUE - IEMN - Acoustique - IEMN - IEMN - Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 - Centrale Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique - UPHF - Université Polytechnique Hauts-de-France - JUNIA - JUNIA - UCL - Université catholique de Lille, JUNIA - JUNIA - UCL - Université catholique de Lille, UCL - Université catholique de Lille
Luis Pérez Armas: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - ULCO - Université du Littoral Côte d'Opale - Université de Lille - CNRS - Centre National de la Recherche Scientifique, IÉSEG School Of Management [Puteaux]
Stefan Creemers: UCL - Université Catholique de Louvain = Catholic University of Louvain, LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - ULCO - Université du Littoral Côte d'Opale - Université de Lille - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization has been the subject of active debate. Although current analog quantum machines do not guarantee optimality, operating instead as heuristic solvers, the technology is evolving rapidly. Beyond performance alone, this emerging technologies offers fundamentally new approaches to problem-solving that are not readily accessible to classical exact methods particularly in dynamic environments or online optimization settings. This paper focuses on one such approaches: Reverse Quantum Annealing (RQA). Unlike classical exact methods, RQA allows the optimization process to begin from an initial infeasible solution by embedding it directly into the qubits' initial state. We leverage this capability by formulating problem constraints as penalty terms within Quadratic Unconstrained Binary Optimization (QUBO) models, thereby preserving infeasible solutions within the quantum search space. We propose iterative strategies that apply RQA in three distinct modes to rapidly repair infeasible solutions. These methods are evaluated on two well-known NP-hard problems: the Maximum Independent Set (MIS) and the 3-SAT problem. Our results demonstrate the effectiveness of RQA in steering infeasible configurations toward feasibility, offering B Samuel Deleplanque

Keywords: Quantum optimization; Maximum Independent Set; 3-SAT; Reverse Quantum Annealing; Reverse Quantum Annealing Quantum optimization Maximum Independent Set 3-SAT (search for similar items in EconPapers)
Date: 2025-08-06
New Economics Papers: this item is included in nep-inv
Note: View the original document on HAL open archive server: https://lilloa.hal.science/hal-05204085v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Journal of Heuristics, 2025, 31 (3), ⟨10.1007/s10732-025-09564-3⟩

Downloads: (external link)
https://lilloa.hal.science/hal-05204085v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-05204085

DOI: 10.1007/s10732-025-09564-3

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().