Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.01261

Efficient Maximum Clique Detection via Grover’s Algorithm with Real-time Global Size Tracking

Wenmin Han, Shiqi Zheng, Peian Chen, Yukun Wang

Published Jan 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $\boldsymbol{n}$-fold improvement over state-of-the-art Grover-based methods, which require $O(n\sqrt{2^n})$ 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.

DOI
10.21203/rs.3.rs-7478238/v1

Related papers

Efficient quantum detection of maximum clique via hybrid heuristic and global information encoding

Wenmin Han, Shiqi Zheng, Peian Chen +1 more

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.

Journal of Physics A Mathematical and Theoretical•May 13, 2026•0 citations

Implementation of Grover’s Algorithm to Solve the Maximum Clique Problem

Andrew Haverly, Sonia Martín López

The maximum clique of an undirected graph is the largest subgraph in which an edge exists between every vertex. The maximum clique problem presents itself in various fields and finding a tractable algorithm to solve the problem is important. This paper introduces an oracle to solve the maximum clique problem using Grover’s quantum algorithm. This approach potentially solves the maximum clique problem in $O\left( {\left| V \right|\sqrt {{2^{\left| V \right|}}} } \right)$ time complexity rather than the current classical time complexity of O(2|V|) of the best known algorithm, where |V| is the number of vertices in the graph. The full circuit implementation is presented using the open-source Qiskit environment [1]. The paper also analyzes the growth of the hardware resources requirements with the number of vertices in the targeted graph.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2021•16 citations

Circuit Synthesis of Maximum Clique Problem using Combinatorial Approach of Classical-Quantum Hybrid Model.

Arpita Sanyal, Amit Saha, Banani Saha +1 more

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(2^n)$). 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.

•Mar 10, 2020•0 citations

Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

Yu. A. Biriukov, R. D. Morozov, I. V. Dyakonov +1 more

This paper addresses the problem of finding the densest $k$-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.

quant-pharXiv:2604.27782•May 1, 2026•0 citations

Quantum Algorithms for the Maximum K-Plex Problem

Xiaofan Li, Gao Cong, Rui Hong Zhou

The k-plex model, which allows each vertex to miss connections with up to$k$neighbors, serves as a relaxation of the clique model. Its adaptability makes it more suitable for analyzing graphs from real-world applications, where noise and imperfect data are common and the stringent clique model is often impractical. The challenge of identifying maximum k-plex (MKP, an NP-hard problem) is gaining attention in fields such as social network analysis, community detection, terrorist network identification, and graph clustering. Recent research efforts have focused on optimizing the time complexity of MKP algorithms. The state-of-the-art has reduced the complexity from a trivial$O^{*}(2^{n})$to$O^{*}(c_{k}^{n})$, with$c_{k} > 1.94$for$k$> 3, where$n$denotes the number of vertices. In this paper, we demonstrate that MKP can be solved in$O^{*}(1.42^{n})$and propose the first two quantum algorithms, qTKP and qMKP, to achieve this complexity. qTKP employs quantum search integrated with graph encoding, degree count, degree comparison, and size determination to find a k-plex of a given size; qMKP uses a binary search to progressively identify the maximum solution. To validate the practical performance and effectiveness of our algorithms, proof-of-principle experiments were conducted using the latest IBM quantum simulator currently available. This work holds potential to be applied to a wide range of clique relaxations, e.g., n-clan and n-club.

IEEE International Conference on Data Engineering (ICDE)•May 13, 2024•2 citations

Quantum speedup in solving the maximal-clique problem

Weng-Long Chang, Qi Yu, Zhaokai Li +3 more

The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph $G$ with $n$ vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, $O(\sqrt{{2}^{n}})$ and $O({n}^{2})$. With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph $G$ with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

arXiv:1803.11356•Physical Review A•Mar 29, 2018•17 citations
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(2n)O\left ( \sqrt{2^{n } } \right ) O(2n​) Grover iterations and O(1)O\left ( 1 \right ) O(1) measurements. This represents an n\boldsymbol{n}n-fold improvement over state-of-the-art Grover-based methods, which require O(n2n)O(n\sqrt{2^n})O(n2n​) iterations and O(n)O(n)O(n) measurements for nnn-vertex graphs. We validate algorithmic correctness through simulations on IBM's Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
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.
The maximum clique of an undirected graph is the largest subgraph in which an edge exists between every vertex. The maximum clique problem presents itself in various fields and finding a tractable algorithm to solve the problem is important. This paper introduces an oracle to solve the maximum clique problem using Grover’s quantum algorithm. This approach potentially solves the maximum clique problem in O(∣V∣2∣V∣)O\left( {\left| V \right|\sqrt {{2^{\left| V \right|}}} } \right)O(∣V∣2∣V∣​) time complexity rather than the current classical time complexity of O(2|V|) of the best known algorithm, where |V| is the number of vertices in the graph. The full circuit implementation is presented using the open-source Qiskit environment [1]. The paper also analyzes the growth of the hardware resources requirements with the number of vertices in the targeted graph.
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)O(2^n)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.
This paper addresses the problem of finding the densest kkk-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
The k-plex model, which allows each vertex to miss connections with up tokkkneighbors, serves as a relaxation of the clique model. Its adaptability makes it more suitable for analyzing graphs from real-world applications, where noise and imperfect data are common and the stringent clique model is often impractical. The challenge of identifying maximum k-plex (MKP, an NP-hard problem) is gaining attention in fields such as social network analysis, community detection, terrorist network identification, and graph clustering. Recent research efforts have focused on optimizing the time complexity of MKP algorithms. The state-of-the-art has reduced the complexity from a trivialO∗(2n)O^{*}(2^{n})O∗(2n)toO∗(ckn)O^{*}(c_{k}^{n})O∗(ckn​), withck>1.94c_{k} > 1.94ck​>1.94forkkk> 3, wherennndenotes the number of vertices. In this paper, we demonstrate that MKP can be solved inO∗(1.42n)O^{*}(1.42^{n})O∗(1.42n)and propose the first two quantum algorithms, qTKP and qMKP, to achieve this complexity. qTKP employs quantum search integrated with graph encoding, degree count, degree comparison, and size determination to find a k-plex of a given size; qMKP uses a binary search to progressively identify the maximum solution. To validate the practical performance and effectiveness of our algorithms, proof-of-principle experiments were conducted using the latest IBM quantum simulator currently available. This work holds potential to be applied to a wide range of clique relaxations, e.g., n-clan and n-club.
The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph GGG with nnn vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(2n)O(\sqrt{{2}^{n}})O(2n​) and O(n2)O({n}^{2})O(n2). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph GGG with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.