A Computational Review of The Maximum Clique Problem: Classical vs. Quantum - Kassim, Shawal (University of the Witwatersrand, Johannesburg, 2025)
The Maximum Clique Problem (MCP) is a fundamental combinatorial optimization problem with wide-ranging applications. Addressing the MCP involves identifying the largest complete subset of vertices in a network graph, a task known to be NP-hard and computationally intensive. With the emergence of quantum computing (QC), there’s growing interest in leveraging quantum algorithms (QAs) to tackle combinatorial problems more efficiently. This research report aims to compare classical methods, such as Branch and Bound (B&B), Dynamic Programming (DP) and Nuclear Norm Minimization (NNM), against quantum methods, including the Variational Quantum Eigensolver (VQE), Quantum Approximation Optimization Algorithm (QAOA) and Grover’s Algorithm (GA), for solving the MCP. Specifically, we investigate whether quantum methods exhibit a computational speedup or offer improvements in solution quality compared to their classical counterparts. Our analysis utilizes IBM’s noisy quantum computers (QCs) for implementing and evaluating the performance of the quantum algorithms. By conducting a comparative study, we seek to gain insights into possible computational advantages of QCs in addressing combinatorial problems such as the MCP.
A dissertation submitted in fulfilment of the requirements for the degree of Master of Science with Masters in Computational and Applied Mathematics, to the Faculty of Science, School of Computer Science and Applied Mathematics, University of the Witwatersrand, Johannesburg, 2025
Keywords: Optimisation; Maximum Clique Problem; Quantum Computing; Graph Theory; Classical Computing; UCTD; SDG-8: Decent work and economic growth; SDG-4: Quality education