Header menu link for other important links
X
Circuit Design for K-coloring Problem and its Implementation on Near-Term Quantum Devices
Published in Institute of Electrical and Electronics Engineers Inc.
2020
Pages: 17 - 22
Abstract
Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-The-Art. An end-To-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach. © 2020 IEEE.