Maximum Clique Problem (MCP) is one of the most important NP-hard problems in the area of soft computing and it has many real world applications in numerous fields ranging from coding theory to the determination of the structure of a protein molecule. Different heuristic, Meta heuristic and hybrid solution approaches have been applied to obtain the solution. In this paper, we demonstrate a Quantum-inspired Evolutionary Algorithm (QEA) to solve MCP. We have used one dimensional arrays of Q-bits called Q-bit individuals to produce binary individuals. After production of binary individuals, we have repaired and improved them. Here, Q-gate is the main variation operator applied on Q-bit individuals. Our algorithm was tested on DIMACS benchmark graphs and 40 of them were tested. The results obtained here are extremely encouraging. For almost all of the datasets, we get the optimal results reported on DIMACS benchmark and also compared our results with other related works. For some cases we get better results than other works.
Maximum Clique Problem (MCP) is one of the most important NP-hard problems in the area of soft computing and it has many real world applications in numerous fields ranging from coding theory to the determination of the structure of a protein molecule. Different heuristic, Meta heuristic and hybrid solution approaches have been applied to obtain the solution. In this paper, we demonstrate a Quantum-inspired Evolutionary Algorithm (QEA) to solve MCP. We have used one dimensional arrays of Q-bits called Q-bit individuals to produce binary individuals. After production of binary individuals, we have repaired and improved them. Here, Q-gate is the main variation operator applied on Q-bit individuals. Our algorithm was tested on DIMACS benchmark graphs and 40 of them were tested. The results obtained here are extremely encouraging. For almost all of the datasets, we get the optimal results reported on DIMACS benchmark and also compared our results with other related works. For some cases we get better results than other works.
Graph Coloring Problem (GCP) bears an enormous significance to the researchers in the field of soft computing. In this paper, we demonstrate a Quantum-Inspired Evolutionary Algorithm (QEA) to solve GCP. We use two dimensional arrays of Q-bits called Q-bit individual to produce binary individual. Q-gate operation is applied as a variation operator on Q-bit individuals. In traditional evolutionary algorithm (EA) for GCP, k-coloring approach is used and the EA is run several times for decreasing value of k until lowest possible k is reached. In our QEA, we start with the number of colors equal to the theoretical upper bound of the chromatic number, which is maximum out-degree + 1, and during evolution some colors are made unused to reduce the number of color in each generation. As a result, solution is found in a single run. We test 36 datasets from DIMACS benchmark and compare the result with several recent works. For five datasets, our algorithm obtains better solution than other. Keywords—quantum-inspired evolutionary algorithm (QEA), graph coloring problem (GCP), combinatorial optimization, Qbit representation, Q-gate.
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.
Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.
In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search space. In the operator, first, the Q-bits of each individual in the population are updated based on the personal best measurement of that individual and the best measurement of current generation. Then, a restriction is applied to each Q-bit to prevent the premature convergence of its values. The results of experiments on the 0-1 knapsack and NK-landscapes problems show that NQEA performs better than a classical genetic algorithm, CGA, and two quantum-inspired evolutionary algorithms, QEA and vQEA, in terms of convergence speed and accuracy.
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 improved algorithm that dynamically tracks the maximum clique size by encoding prior constraints on the vertex count—derived from Turán's theorem and complete graph properties—into global variables through quantum circuit pre-detection. The algorithm further synergizes with Grover's search to optimize the solution space. Our auxiliary-qubit encoding scheme dynamically tracks clique sizes during quantum search, eliminating iterative measurements, achieving MCP solution with $O\left ( \sqrt{2^{n } } \right ) $ Grover iterations and $O\left ( 1 \right ) $ measurements. This represents an n-fold improvement over state-of-the-art Grover-based methods, which require O(n2n) iterations and O(n) measurements for n-vertex graphs. We validate algorithmic correctness through simulations on IBM's Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
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.