Circuit Design Of Clique Problem And Its Implementation On NISQ Using Combinatorial Approach Of Classical-Quantum Hybrid Model

Clique problem has several applications in computer vision, automatic test pattern generation, predicting protein structures, and many kinds of such pattern search. In this paper, a generalized algorithm for the k-Clique problem has been newly proposed using a classical-quantum hybrid approach, which can also be extended as a generalized algorithm for maximum clique problem. The complexity of the proposed algorithm has been reduced to $O(\sqrt{2^{k*log_2n}})$ than the classical algorithm with complexity $O(2^n)$ for a k sized clique in an n node graph. The algorithm automatically generates the circuit for any given undirected and unweighted graph, which makes the approach generalized in nature. The experimental result of the generic algorithm has been implemented in the $IBMQ\_Qasm\_Simulator$. The generated circuit can also be mapped in Noisy Intermediate-Scale Quantum (NISQ) devices(IBM QX architecture).