Circuit design for clique problem and its implementation on quantum computer

Abstract

Abstract Finding cliques in a graph has a wide range of applications due to its pattern matching ability. The k‐clique problem, a subset of the clique problem, determines whether or not an arbitrary network has a clique of size k. Modern‐day applications include a variation of the k‐clique problem that lists all cliques of size k. However, the quantum implementation of such a variation of the k‐clique problem has not been addressed yet. In this work, apart from the theoretical solution of such a k‐clique problem, practical quantum‐gate‐based implementation has been addressed using Grover's algorithm. In a classical‐quantum hybrid architecture, this approach is extended to build the circuit for the maximum clique problem. Our technique is generalised since the program automatically builds the circuit for any given undirected and unweighted graph and any chosen k. For a small k with regard to a big graph, the proposed solution to addressing the k‐clique issue has shown a reduction in qubit cost and circuit depth when compared to the state‐of‐the‐art approach. A framework is also presented for mapping the automated generated circuit for clique problems to quantum devices. Using IBM's Qiskit, an analysis of the experimental results is demonstrated.

Keywords

• Grover's algorithm
• k‐clique problem
• maximum clique problem
• NISQ devices
• quantum circuit synthesis