Finding maximum independent set based on multi-stage simulated quantum adiabatic evolution

Xi Li, Shouwei Hu, Zhihao Liu and Wenjie Liu

Physica A: Statistical Mechanics and its Applications, 2024, vol. 651, issue C

Abstract: The ubiquitous nature of the maximum independent set (MIS) problem across diverse fields, including biology and chip design, presents a significant challenge. Recently, quantum algorithms have been recognized for their increased potential in addressing combinatorial optimization problems, including the MIS problem. Several quantum systems, including optical quantum circuits and Rydberg atomic systems, have been designed specifically for the MIS problem. However, elucidating the precise nature of instances that pose challenges for quantum algorithms constitutes a formidable task. In an effort to comprehend this issue, we endeavor to delineate the conditions under which instances become hard to solve by analyzing the Hamiltonian of the k-independent set (k-IS). Furthermore, we present two multi-stage strategies grounded in the simulated quantum adiabatic evolution (SQAE) of Kerr-nonlinear parametric oscillator (KPO) system for identifying the MIS in instances deemed hard to solve. More specifically, we present the algorithm leveraging SQAE of the KPO system for approximating the MIS. Our investigation of the SQAE algorithm reveals that optimal solutions are unattainable under two distinct conditions: (1) when the number of solutions is exponentially smaller to the problem’s scale, and (2) when the counts of non-optimal independent sets (IS) with m overlaps between the optimal k-IS (k>m) is exponentially smaller relative to the problem’s scale. With these two distinctive features, we propose two multi-stage SQAE strategies tailored for hard-to-solve instances. In the first approach, the SQAE algorithm is executed multiple times to identify a set of candidate vertices for the MIS. For each vertex or combinations of vertices in this set, we extract the subgraphs induced by the vertices not adjacent to them. Subsequently, the SQAE algorithm is applied to the subgraph to obtain the (k−1)-IS. In the second multi-stage strategy, we consider each vertex vi in the given graph, generating the subgraph induced by the vertices not adjacent to vi. The SQAE algorithm is then employed to find the (k−1)-IS of the subgraph. Experimental results demonstrate that both multi-stage strategies significantly enhance the performance of the SQAE algorithm for hard-to-solve instances.

Keywords: Quantum heuristic algorithm; Simulated quantum adiabatic evolution; Maximum independent set problem; Kerr-nonlinear parametric oscillator systems (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437124005107
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:651:y:2024:i:c:s0378437124005107

DOI: 10.1016/j.physa.2024.130001

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().