A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours

A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours Prem Shanker Dwivedi, Amit Biswas, Indu Dohare This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7196567/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Graph colouring with minimum colours is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph colouring problem with the minimum number of colours. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for exponential speed up on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum-classical method for solving the graph colouring problem with guaranteed correctness. The proposed method is inspired by Grover’s quantum search algorithm, the Clifford circuit, and the classical binary search algorithm. Here, Grover’s algorithm helps to achieve a quadratic speed up, Clifford circuit helps to mitigate the errors, and binary search helps to find the chromatic number with guaranteed correctness in polynomial time. We also conducted several experiments to evaluate the proposed method's performance and correctness, and the experimental results corroborate our claims regarding the proposed method. Additionally, a mathematical analysis is performed to assess its time and qubit complexities, and to compare its efficiency with existing methods. Graph colouring Quantum algorithm NP-complete Chromatic number Classical algorithm Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7196567","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":529306609,"identity":"d4c6ad8f-4b05-49f8-87df-914c7cc6df4b","order_by":0,"name":"Prem Shanker Dwivedi","email":"","orcid":"","institution":"Motilal Nehru National Institute of Technology Allahabad","correspondingAuthor":false,"prefix":"","firstName":"Prem","middleName":"Shanker","lastName":"Dwivedi","suffix":""},{"id":529306610,"identity":"649be858-8b98-4f81-ba29-9607170bee93","order_by":1,"name":"Amit Biswas","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABBklEQVRIiWNgGAWjYFACxgZmBgMQg/nw45//bEAijQcIaGlshmhhSzMGYrAhBLQwMDZDaB4DaQa2w2AmXi380w63Py4oqEvs7z9gYFzAc95ubfthoC01NtG4tEjcTmxsnmFwOHHGjYSExzMkbidvO5MI1HIsLbcBlx6QFh6DA7kNNxgOGPAY3E42OwDUwthwGKcWeYiWutz55w82SPAknEs2O/8QvxYDiBbm3A0HkhmkeQ4csDO7QcAWQ6CW2UC/1G+8kcZmOLMhOcHsBtCWBDx+kbud/uBzwZ86Y7nz5z8/+NhgZ292Pv3hgw81Nri9jw4SwSoTiFUOAvakKB4Fo2AUjIKRAQBxv2xSnUWOKgAAAABJRU5ErkJggg==","orcid":"","institution":"Motilal Nehru National Institute of Technology Allahabad","correspondingAuthor":true,"prefix":"","firstName":"Amit","middleName":"","lastName":"Biswas","suffix":""},{"id":529306611,"identity":"4da7ebb0-1302-452c-addb-09c2d9db9077","order_by":2,"name":"Indu Dohare","email":"","orcid":"","institution":"Motilal Nehru National Institute of Technology Allahabad","correspondingAuthor":false,"prefix":"","firstName":"Indu","middleName":"","lastName":"Dohare","suffix":""}],"badges":[],"createdAt":"2025-07-23 12:53:16","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7196567/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7196567/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":93805357,"identity":"16b96204-6439-4c61-bcf0-5e2e7dc4ee44","added_by":"auto","created_at":"2025-10-17 18:00:23","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":4895,"visible":true,"origin":"","legend":"","description":"","filename":"9b67e4bf27384cb6b0378db02a209022.json","url":"https://assets-eu.researchsquare.com/files/rs-7196567/v1/980412c881f14c892b1d5235.json"},{"id":94988172,"identity":"de4eed08-e404-4a97-b2ac-73ed193d7ee3","added_by":"auto","created_at":"2025-11-03 07:05:52","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":485946,"visible":true,"origin":"","legend":"","description":"","filename":"Manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7196567/v1_covered_c879d49c-a28f-41e7-ac2e-b424520cefe6.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Graph colouring, Quantum algorithm, NP-complete, Chromatic number, Classical algorithm","lastPublishedDoi":"10.21203/rs.3.rs-7196567/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7196567/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Graph colouring with minimum colours is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph colouring problem with the minimum number of colours. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for exponential speed up on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum-classical method for solving the graph colouring problem with guaranteed correctness. The proposed method is inspired by Grover’s quantum search algorithm, the Clifford circuit, and the classical binary search algorithm. Here, Grover’s algorithm helps to achieve a quadratic speed up, Clifford circuit helps to mitigate the errors, and binary search helps to find the chromatic number with guaranteed correctness in polynomial time. We also conducted several experiments to evaluate the proposed method's performance and correctness, and the experimental results corroborate our claims regarding the proposed method. Additionally, a mathematical analysis is performed to assess its time and qubit complexities, and to compare its efficiency with existing methods.","manuscriptTitle":"A Quantum-Classical Approach to Solve the Graph Colouring Problem with Minimum Colours","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-10-17 18:00:18","doi":"10.21203/rs.3.rs-7196567/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"9730cb4f-1d88-4cf4-89ad-075afdaae522","owner":[],"postedDate":"October 17th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-11-01T18:08:29+00:00","versionOfRecord":[],"versionCreatedAt":"2025-10-17 18:00:18","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7196567","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7196567","identity":"rs-7196567","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}