Ardelean SM, Udrescu M. Graph coloring using the reduced quantum genetic algorithm.
PeerJ Comput Sci 2022;
8:e836. [PMID:
35111921 PMCID:
PMC8771768 DOI:
10.7717/peerj-cs.836]
[Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/27/2021] [Accepted: 12/07/2021] [Indexed: 06/14/2023]
Abstract
Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N1/2). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number (i.e., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.
Collapse