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

• URL: http://arxiv.org/abs/2509.01261v1
• Date: Mon, 01 Sep 2025 08:50:54 GMT
• Title: Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
• Authors: Wenmin Han, Shiqi Zheng, Peian Chen, Yukun Wang,
• Abstract summary: The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph.<n>It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields.<n>This paper proposes an improved algorithm that dynamically tracks the maximum clique size.
• Score: 6.528817049577178
• License: http://creativecommons.org/licenses/by/4.0/
• 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\'an'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(1)$ 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.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
  In bipartite graph analysis, enumeration of $s$-biplexes is a fundamental problem.<n>In real-world data engineering, finding all $s-biplexes is neither necessary nor computationally affordable.<n>We propose MVBP, that breaks the simple $2n enumeration algorithm.<n>FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.
  arXiv  Detail & Related papers  (2024-09-27T06:23:29Z)
• A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
  A $k$-defective clique of an un branching graph $G$ induces a nearly complete graph with a maximum of $k$ missing edges. The maximum $k$-defective clique problem, which asks for the largest $k$-defective clique from the given graph, is important in many applications, such as social and biological network analysis.
  arXiv  Detail & Related papers  (2024-07-23T15:40:35Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Dynamic algorithms for k-center on graphs [3.568439282784197]
  We give the first efficient algorithms for the $k$-center problem on dynamic graphs undergoing edge updates. We show a reduction that leads to a fully dynamic $(2+epsilon)$-approximation algorithm for the $k$-center problem.
  arXiv  Detail & Related papers  (2023-07-28T13:50:57Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  The maximum $k$-plex problem is important but computationally challenging in applications such as graph mining and community detection. We present an exact algorithm parameterized by $g_k(G)$, which has the worst-case running time in the size of the input graph and exponential in $g_k(G)$. We further extend our discussion to an even smaller parameter $cg_k(G)$, the gap between the community-degeneracy bound and the size of the maximum $k$-plex.
  arXiv  Detail & Related papers  (2023-06-23T01:28:24Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
  We present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs) We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps.
  arXiv  Detail & Related papers  (2022-12-29T19:07:39Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.