Open AccessGraph coloring using the reduced quantum genetic algorithm
Author(s) -
Sebastian Mihai Ardelean,
Mihai Udrescu
Publication year - 2022
Publication title -
peerj. computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.806
H-Index - 24
ISSN - 2376-5992
DOI - 10.7717/peerj-cs.836
Subject(s) - graph coloring , computer science , quantum computer , heuristics , algorithm , genetic algorithm , quantum algorithm , quantum , graph , theoretical computer science , physics , quantum mechanics , machine learning , operating system
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(N 1/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.