2020/04/30 by Arpita Sanyal, Arpita Sanyal Bhaduri, Amit Saha +3
Computer Science · Mathematics · #Algorithm #Clique #Clique graph #Clique problem #Combinatorics #Computer science #Discrete mathematics #Graph #Graph power #Line graph #Mathematics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum circuit #Quantum computer #Quantum mechanics #Quantum network #Quantum-Dot Cellular Automata #Simplex graph #Steiner tree problem #Theoretical computer science #cs.DS
paper · pdf · doi:10.1049/qtc2.12029
published as IET Quantum Communication, 2021 · 25 pages, 18 figures. arXiv admin note: text overlap with arXiv:1805.10224 by other authors
openalex created_date 2021/02/01 · arxiv created 2021/07/07 · openalex publication_date 2021/12/09 · arxiv updated 2022/02/23 · openalex updated_date 2026/08/05
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.