Modularity‐Preserving Hamiltonian Compression for QAOA‐Based Community Detection

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 (𝑛2 ) 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.