Circuit Design for k-Coloring Problem and Its Implementation in Any Dimensional Quantum System

Abstract

With the evolution of quantum computing, researchers nowadays tend to incline to find solutions to NP-complete problems using quantum algorithms to gain asymptotic advantage. In this paper, we solve k-coloring problem (NP-complete problem) using Grover’s algorithm in any dimensional quantum system or any d-ary quantum system for the first time to the best of our knowledge, where d≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d \ge 2$$\end{document}. Till date, k-coloring problem has been implemented only in binary and ternary quantum systems, hence, we abide to d=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d=2$$\end{document} or d=3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d=3$$\end{document}, that is for binary and ternary quantum systems for comparing our proposed work with the state-of-the-art techniques. Our comparator-based approach has reduced the qubit cost, compared to the state-of-the-art binary quantum systems (Saha et al. in IEEE Int Symp Smart Electron Syst 1:17–22, 2020). Further in this paper, with the help of newly proposed ternary comparator, a substantial reduction in quantum gate count for the ternary oracle circuit of the k-coloring problem than the previous approaches has been obtained. Later, this proposed comparator-based approach helps to generalize the implementation of the k-coloring problem in any dimensional quantum system. An end-to-end automated framework has been put forward for implementing the k-coloring problem for any undirected and unweighted graph on any available near-term quantum devices or Noisy Intermediate-Scale Quantum (NISQ) devices or multi-valued quantum simulator, which helps in generalizing our approach.