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.
arXiv comment25 pages, 18 figures. arXiv admin note: text overlap with arXiv:1805.10224 by other authors
References in corpus (22)
- Community detection in graphs
- Quantum Computing in the NISQ era and beyond
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Uncovering the overlapping community structure of complex networks in nature and society
- Elementary gates for quantum computation
- Tight bounds on quantum searching
- Grover Algorithm with zero theoretical failure rate
- An example of the difference between quantum and classical random walks
- The General Quantum Interference Principle and the Duality Computer
- Fixed-point quantum search with an optimal number of queries
- Dynamic Local Search for the Maximum Clique Problem
- Phase matching in quantum searching
- Optimal Layout Synthesis for Quantum Computing
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- Solving large Maximum Clique problems on a quantum annealer
- On the Quantum Query Complexity of Detecting Triangles in Graphs
- Quantum walk algorithm for element distinctness
- Finding Small and Large k-Clique Instances on a Quantum Computer
- A Query-based Quantum Eigensolver
- Quantum Algorithms for the Triangle Problem
- Quantum Algorithm for Triangle Finding in Sparse Graphs