QUBO Modeling for a Spectrum of Domination Problems

Haoqian Pan and Changhong Lu

Journal of Mathematics, 2025, vol. 2025, 1-12

Abstract: As quantum computing advances, the application of quantum algorithms to address combinatorial optimization problems on quantum computers has emerged as a pivotal area of research. The quadratic unconstrained binary optimization (QUBO) acts as an intermediary, facilitating the translation of combinatorial optimization problems into a quantum computing context, thereby constituting an essential foundation for this field of inquiry. Within the realm of combinatorial optimization, the domination problem (DP) is pertinent to a myriad of real-world applications, including, but not limited to, the strategic placement of fire stations and the analysis of social network structures. Furthermore, the DP encompasses a multitude of variants, exemplified by the independent DP, total DP, and k-domination, among others. However, a dearth of research exists within the quantum computing community regarding these variant problems. One plausible explanation for this gap is the absence of comprehensive QUBO modeling research pertaining to these issues. This paper delves into the methodologies of QUBO modeling for both the canonical DP and its diverse variants. For the classic DP, we have refined the existing QUBO modeling methods, addressing the issue of incomplete modeling. Additionally, we have optimized the variable representation of the slack terms in the penalty items of DP. At the same time, we introduce novel QUBO modeling methods for a spectrum of DP variants, marking a pioneering effort in this domain. Our contributions are anticipated to expedite the integration of DP into the burgeoning quantum computing landscape.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/jmath/2025/3201094.pdf (application/pdf)
http://downloads.hindawi.com/journals/jmath/2025/3201094.xml (application/xml)

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:hin:jjmath:3201094

DOI: 10.1155/jom/3201094

Access Statistics for this article

More articles in Journal of Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().