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

Samuel Deleplanque (), Luis Fernando Pérez Armas () and Stefan Creemers ()
Additional contact information
Samuel Deleplanque: Univ. Lille, CNRS, Centrale Lille, Junia, Univ. Polytechnique Hauts-de-France, UMR 8520 - IEMN
Luis Fernando Pérez Armas: IESEG School of Management, Univ. Lille, CNRS, UMR 9221 - LEM - Lille Economie Management
Stefan Creemers: Center for Operations Research and Econometrics (CORE), Université catholique de Louvain

Journal of Heuristics, 2025, vol. 31, issue 3, No 5, 28 pages

Abstract: 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 promising potential for real-time applications where problem data may change suddenly and solutions must be repaired swiftly.

Keywords: Reverse Quantum Annealing; Quantum optimization; Maximum Independent Set; 3-SAT (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09564-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:31:y:2025:i:3:d:10.1007_s10732-025-09564-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09564-3

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().