The maximum clique in an undirected graph is the largest subset of a set of graph's vertices where each pair of elements in the subset is connected. In this paper I would like to propose an algorithm for quantum computers that finds a maximum clique in an arbitrary undirected graph. An algorithm has O(|V|2|V|/2) worst case time complexity and O(2|V|/2) best case time complexity. Algorithm's space complexity for each case is O(|V|). An algorithm is based on a version of Grover's quantum algorithm for finding element in an unsorted list in which there can be an unknown number of solutions.
In the Maximum Clique Problem, the objective is to find a clique whose size is maximum among all the cliques of an arbitrary undirected and unweighted graph. Maximum Clique Problem resembles with minimum vertex cover problem, independent set problem. As it is an NP-hard problem, no polynomial time algorithms can be found. As these problems have several important practical applications such as information retrieval, community detection in network, spatial data mining etc, it is of great interest to try to synthesis the circuit of Maximum Clique Problem. In classical computing any brute-force solution to the Maximum Clique Problem requires an exponential increase of time with the size of the problem (i.e., with time complexity of
O(2n)). In this paper, Maximum Clique Problem has been solved using combinatorial approach of Grover's search algorithm. An algorithm has been proposed that auto-generates the circuit for any given undirected and unweighted graph which makes the approach generalized in nature for Maximum Clique Problem. Computational speed up is achieved by using our approach with the help of quantum mechanical effect that is quantum superposition. We have simulated the proposed circuit using IBM's QISkit platform and verified its correctness.
Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution.
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.
In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement
Gˉ of any graph
G, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph
H, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only
O(N) number of qubits with respect to the number of vertices
N, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only
O(N) qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.