Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation

Abstract

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 large-scale graph data.

DAC 2025

References in corpus (16)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Escaping free-energy minima
• Quantum Machine Learning
• Hierarchical organization of modularity in metabolic networks
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Community detection in networks: A user guide
• Clustering and Community Detection in Directed Networks: A Survey
• Sketching as a Tool for Numerical Linear Algebra
• Community Discovery in Dynamic Networks: a Survey
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• Quantum-inspired algorithms in practice
• Different approaches to community detection
• Quantum-Annealing-Inspired Algorithms for Track Reconstruction at High-Energy Colliders
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding