Circuit Design for Clique Problem and Its Implementation on Quantum Computer
arXiv:2004.10596 · doi:10.1049/qtc2.12029
Abstract
Finding cliques in a graph has several applications for its pattern matching ability. -clique problem, a special case of clique problem, determines whether an arbitrary graph contains a clique of size , has already been addressed in quantum domain. A variant of -clique problem that lists all cliques of size , has also popular modern-day applications. Albeit, the implementation of such variant of -clique problem in quantum setting still remains untouched. In this paper, apart from theoretical solution of such -clique problem, practical quantum gate-based implementation has been addressed using Grover's algorithm. This approach is further extended to design circuit for the maximum clique problem in classical-quantum hybrid architecture. The algorithm automatically generates the circuit for any given undirected and unweighted graph and any given , which makes our approach generalized in nature. The proposed approach of solving -clique problem has exhibited a reduction of qubit cost and circuit depth as compared to the state-of-the-art approach, for a small with respect to a large graph. A framework that can map the automated generated circuit for clique problem to quantum devices is also proposed. An analysis of the experimental results is demonstrated using IBM's Qiskit.
25 pages, 18 figures. arXiv admin note: text overlap with arXiv:1805.10224 by other authors
References in corpus (8)
- Uncovering the overlapping community structure of complex networks in nature and society
- Fixed-point quantum search with an optimal number of queries
- Optimal Layout Synthesis for Quantum Computing
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- On the Quantum Query Complexity of Detecting Triangles in Graphs
- Finding Small and Large k-Clique Instances on a Quantum Computer
- A Query-based Quantum Eigensolver
- Quantum Algorithms for the Triangle Problem