A Computational Review of The Maximum Clique Problem: Classical vs. Quantum

Abstract

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.