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.19214

Gate-Based and Annealing-Based Quantum Algorithms for the Maximum K-Plex Problem

Xiaofan Li, Gao Cong, Rui Zhou

Published Sep 23, 2025• 0 citations
arXivHTMLPDF

Abstract

The $ k $-plex model, which allows each vertex to miss connections with up to $ k $ neighbors, serves as a relaxation of the clique. Its adaptability makes it more suitable for analyzing real-world graphs where noise and imperfect data are common and the ideal clique model is often impractical. The problem of identifying the maximum $ k $-plex (MKP, which is NP-hard) is gaining attention in fields such as social network analysis, community detection, terrorist network identification, and graph clustering. Recent works 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 \geq 3 $, where $ n $ denotes the vertex number. This paper investigates the MKP using two quantum models: gate-based model and annealing-based model. Two gate-based algorithms, qTKP and qMKP, are proposed to achieve $ O^*(1.42^n) $ time complexity. qTKP integrates quantum search with graph encoding, degree counting, degree comparison, and size determination to find a $ k $-plex of a given size; qMKP uses binary search to progressively identify the maximum solution. Furthermore, by reformulating MKP as a quadratic unconstrained binary optimization problem, we propose qaMKP, the first annealing-based approximation algorithm, which utilizes qubit resources more efficiently than gate-based algorithms. To validate the practical performance, proof-of-principle experiments were conducted using the latest IBM gate-based quantum simulator and D-Wave adiabatic quantum computer. This work holds potential to be applied to a wide range of clique relaxations, e.g., $ n $-clan and $ n $-club.

DOI
10.48550/arxiv.2509.19214

Related papers

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

Finding Maximum Cliques on a Quantum Annealer

Guillaume Chapuis, Hristo N. Djidjev, Georg Hahn +1 more

This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

ACM International Conference on Computing Frontiers (CF)•May 15, 2017•31 citations

An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem

Alessandro Gherardi, Alberto Leporati

Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.

arXiv:2406.07587•Jun 11, 2024•0 citations

Quantum Algorithm for Maximum Biclique Problem

Xiaofan Li, Prasenjit Mitra, Rui Zhou +1 more

Identifying a biclique with the maximum number of edges bears considerable implications for numerous fields of application, such as detecting anomalies in E-commerce transactions, discerning protein-protein interactions in biology, and refining the efficacy of social network recommendation algorithms. However, the inherent NP-hardness of this problem significantly complicates the matter. The prohibitive time complexity of existing algorithms is the primary bottleneck constraining the application scenarios. Aiming to address this challenge, we present an unprecedented exploration of a quantum computing approach. Efficient quantum algorithms, as a crucial future direction for handling NP-hard problems, are presently under intensive investigation, of which the potential has already been proven in practical arenas such as cybersecurity. However, in the field of quantum algorithms for graph databases, little work has been done due to the challenges presented by the quantum representation of complex graph topologies. In this study, we delve into the intricacies of encoding a bipartite graph on a quantum computer. Given a bipartite graph with n vertices, we propose a ground-breaking algorithm qMBS with time complexity O^*(2^(n/2)), illustrating a quadratic speed-up in terms of complexity compared to the state-of-the-art. Furthermore, we detail two variants tailored for the maximum vertex biclique problem and the maximum balanced biclique problem. To corroborate the practical performance and efficacy of our proposed algorithms, we have conducted proof-of-principle experiments utilizing IBM quantum simulators, of which the results provide a substantial validation of our approach to the extent possible to date.

arXiv:2309.04503•Sep 8, 2023•0 citations

Finding Maximum Cliques on the D-Wave Quantum Annealer

Guillaume Chapuis, Hristo N. Djidjev, Georg Hahn +1 more

This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08649•Jan 26, 2018•5 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
The kkk-plex model, which allows each vertex to miss connections with up to kkk neighbors, serves as a relaxation of the clique. Its adaptability makes it more suitable for analyzing real-world graphs where noise and imperfect data are common and the ideal clique model is often impractical. The problem of identifying the maximum kkk-plex (MKP, which is NP-hard) is gaining attention in fields such as social network analysis, community detection, terrorist network identification, and graph clustering. Recent works have focused on optimizing the time complexity of MKP algorithms. The state-of-the-art has reduced the complexity from a trivial O∗(2n)O^*(2^n)O∗(2n) to O∗(ckn)O^*(c_k^n)O∗(ckn​), with ck>1.94c_k > 1.94ck​>1.94 for k≥3k \geq 3k≥3, where nnn denotes the vertex number. This paper investigates the MKP using two quantum models: gate-based model and annealing-based model. Two gate-based algorithms, qTKP and qMKP, are proposed to achieve O∗(1.42n)O^*(1.42^n)O∗(1.42n) time complexity. qTKP integrates quantum search with graph encoding, degree counting, degree comparison, and size determination to find a kkk-plex of a given size; qMKP uses binary search to progressively identify the maximum solution. Furthermore, by reformulating MKP as a quadratic unconstrained binary optimization problem, we propose qaMKP, the first annealing-based approximation algorithm, which utilizes qubit resources more efficiently than gate-based algorithms. To validate the practical performance, proof-of-principle experiments were conducted using the latest IBM gate-based quantum simulator and D-Wave adiabatic quantum computer. This work holds potential to be applied to a wide range of clique relaxations, e.g., nnn-clan and nnn-club.
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.
This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.
Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.
Identifying a biclique with the maximum number of edges bears considerable implications for numerous fields of application, such as detecting anomalies in E-commerce transactions, discerning protein-protein interactions in biology, and refining the efficacy of social network recommendation algorithms. However, the inherent NP-hardness of this problem significantly complicates the matter. The prohibitive time complexity of existing algorithms is the primary bottleneck constraining the application scenarios. Aiming to address this challenge, we present an unprecedented exploration of a quantum computing approach. Efficient quantum algorithms, as a crucial future direction for handling NP-hard problems, are presently under intensive investigation, of which the potential has already been proven in practical arenas such as cybersecurity. However, in the field of quantum algorithms for graph databases, little work has been done due to the challenges presented by the quantum representation of complex graph topologies. In this study, we delve into the intricacies of encoding a bipartite graph on a quantum computer. Given a bipartite graph with n vertices, we propose a ground-breaking algorithm qMBS with time complexity O^*(2^(n/2)), illustrating a quadratic speed-up in terms of complexity compared to the state-of-the-art. Furthermore, we detail two variants tailored for the maximum vertex biclique problem and the maximum balanced biclique problem. To corroborate the practical performance and efficacy of our proposed algorithms, we have conducted proof-of-principle experiments utilizing IBM quantum simulators, of which the results provide a substantial validation of our approach to the extent possible to date.
This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.
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.