Muskan Saha, Bikash K. Behera
Colouring of graphs is a fundamental aspect of graph theory with numerous applications in computer science, including scheduling, map coloring, and network design. Despite existing methods for determining graph colorability, there is a notable absence of quantum algorithms specifically aimed at both assessing a graph's colorability and performing the coloring task itself. This study presents a novel quantum algorithm leveraging the principle of quantum entanglement to perform 2- and 3-vertex coloring of graphs. The algorithm synthesizes basic quantum gates into quantum circuits that first ascertain whether a given graph is colorable with 2 or 3 colors, followed by executing the necessary operations to effectuate the coloring process. Our findings demonstrate the feasibility of employing quantum resources to tackle graph coloring problems, which could significantly enhance efficiency in computer science-related tasks that require graph colorability analysis. The results emphasize the potential of quantum computing to transform approaches in solving complex problems traditionally addressed by classical algorithms.
@article{72aafda1-3be4-4104-9dae-9dddd20db2b6,
title={Quantum Algorithms for Colouring of Graphs},
author={Muskan Saha and Bikash K. Behera},
year={2018},
language={en}
}TY - JOUR TI - Quantum Algorithms for Colouring of Graphs AU - Muskan Saha AU - Bikash K. Behera PY - 2018 LA - en ER -
Deepak Malhotra
This work discusses the essential components of a rigorous auditing process aimed at enhancing metallurgical plant performance. The objective is to id
Robert A. Francis
This document serves as a comprehensive introduction to the metallurgy of steel and its alloys, focusing on various aspects of iron and steel manufact
Hao Cui, Corby G Anderson
This study provides an up-to-date review of recycling of printed circuit boards (PCBs), specifically in hydrometallurgical treatment. Waste printed ci
Santhana Krishnan, Nor Syahidah Zulkapli
Fast industrialization has increased the demand for heavy metals, while high-grade ore natural reserves are diminishing. Therefore, alternative source
C.N. Mpinga, J.J. Eksteen
Platinum Group Metals (PGMs), often with associated gold, have very few occurrences where they are present in an ore deposit at economically extractab
This paper addresses the challenge of assessing the feasibility of wind power plant projects at sites with insufficient or no local historic wind data