Implementation of Grover’s Algorithm to Solve the Maximum Clique Problem
Andrew Haverly, Sonia Martín López · 2021
The maximum clique of an undirected graph is the largest subgraph in which an edge exists between every vertex. The maximum clique problem presents itself in various fields and finding a tractable algorithm to solve the problem is important. This paper introduces an oracle to solve the maximum clique problem using Grover’s quantum algorithm. This approach potentially solves the maximum clique problem in $O\left( {\left| V \right|\sqrt {{2^{\left| V \right|}}} } \right)$ time complexity rather than the current classical time complexity of O(2|V|) of the best known algorithm, where |V| is the number of vertices in the graph. The full circuit implementation is presented using the open-source Qiskit environment [1]. The paper also analyzes the growth of the hardware resources requirements with the number of vertices in the targeted graph.