Fast Optimization of Hamiltonian for Constrained Community Detection

Wei Li, Yi-Lun Du, Nan Su +3 more

Sana Akbar, Sri Khetwat Saritha

Qiushi Gu, Zhuoyu Wen, Jing Liu

Jinglei Cheng, Ruilin Zhou, Yuhang Gan +2 more

We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structures. We implement a multi-level algorithm that iteratively refines community assignments by alternating between QUBO problem setup and QHD-based optimization. Benchmarking shows our method achieves up to 5.49% better modularity scores while requiring less computational time compared to classical optimization approaches. This work demonstrates the potential of hybrid quantum-inspired solutions for advancing community detection in largescale graph data.

Danilo Cavaliere, Giuseppe Fenza, Vincenzo Loia

ABSTRACT Modularity maximization for community detection can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implemented with the Quantum Approximate Optimization Algorithm (QAOA). However, directly encoding the full modularity matrix yields a dense Hamiltonian with two‐qubit interactions, resulting in circuits that are too deep for simulators and near‐term quantum hardware. This work introduces a set of modularity‐preserving Hamiltonian encodings designed to reduce circuit complexity while retaining the structural information needed for community detection. The proposed methods include magnitude sparsification, top‐ filtering, energy‐based sparsification, low‐rank spectral projection, and penalty‐augmented formulations, adapting classical approximation strategies into more efficient quantum cost operators. The methods are evaluated on real social graphs and compared with the Louvain algorithm and the full modularity encoding. Results, averaged over multiple random seeds with confidence intervals, show that energy‐based and top‐ encodings achieve the best accuracy–runtime trade‐off, significantly reducing circuit complexity while maintaining competitive partition quality. Low‐rank and magnitude‐based sparsification preserve higher accuracy but are more noise‐sensitive, while penalty‐based formulations exhibit higher variability. Scalability experiments on 16‐, 20‐, and 24‐qubit encodings confirm these trends, and simulations under depolarizing noise indicate that energy‐based and top‐ methods remain among the most robust.

Ehsan Zahedinejad, Daniel Crawford, Clemens P. J. Adolphs +1 more

Signed graphs serve as a primary tool for modelling social networks. They can represent relationships between individuals (i.e., nodes) with the use of signed edges. Finding communities in a signed graph is of great importance in many areas, for example, targeted advertisement. We propose an algorithm to detect multiple communities in a signed graph. Our method reduces the multi-community detection problem to a quadratic binary unconstrained optimization problem and uses state-of-the-art quantum or classical optimizers to find an optimal assignment of each individual to a specific community.