Solving the General Planar Graph Coloring Problem Using Grover’s Algorithm


Authors : Lenish Pandey; Swayam Chaulagain; Madhav Khanal; Pratyush BHattrai; Sampada Wagle; Sooraj Sahani

Volume/Issue : Volume 8 - 2023, Issue 12 - December

Google Scholar : http://tinyurl.com/4wsxvad4

Scribd : http://tinyurl.com/5cza3zmp

DOI : https://doi.org/10.5281/zenodo.10629676

Abstract : In this paper, we discuss the structure and implementations of the planar graph-coloring problem (PGCP). We briefly look at well-known classical algorithms used to solve the PGCP but primarily focus on the quantum computational angle. Grover’s search is a well-known quantum algorithm that offers a quadratic advantage relative to its classical counterparts. We inspect its application to the PGCP and build a corresponding quantum circuit. We take a specific case of specialists in Nepalese hospitals and optimize their placements.

In this paper, we discuss the structure and implementations of the planar graph-coloring problem (PGCP). We briefly look at well-known classical algorithms used to solve the PGCP but primarily focus on the quantum computational angle. Grover’s search is a well-known quantum algorithm that offers a quadratic advantage relative to its classical counterparts. We inspect its application to the PGCP and build a corresponding quantum circuit. We take a specific case of specialists in Nepalese hospitals and optimize their placements.

Video Explanation for Published paper

Never miss an update from Papermashup

Get notified about the latest tutorials and downloads.

Subscribe by Email

Get alerts directly into your inbox after each post and stay updated.
Subscribe
OR

Subscribe by RSS

Add our RSS to your feedreader to get regular updates from us.
Subscribe