2020/06/29 by Elijah Pelofske, Georg Hahn, Hristo Djidjev · 21 citations
Computer Science · Engineering · Physics and Astronomy · #Clique #Clique problem #Complexity and Algorithms in Graphs #Cover (algebra) #Pruning #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum computer #Radiation Effects in Electronics #Reduction (mathematics) #Set (abstract data type) #Vertex (graph theory) #Vertex cover #cs.DM #cs.ET #quant-ph
paper · pdf · doi:10.1007/s11265-020-01550-1
published in Journal of Signal Processing Systems 93(4), 405-420 (Springer Science+Business Media) · arXiv admin note: text overlap with arXiv:1904.00051
openalex publication_date 2020/06/29 · arxiv created 2020/09/10 · openalex created_date 2020/09/21 · arxiv updated 2022/03/01 · openalex updated_date 2026/08/05
NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp's 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. The framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.