F. Gemeinhardt, R. Wille, M. Wimmer: Quantum k-community detection: algorithm proposals and cross-architectural evaluation, in Quantum Information Processing 20, Article number 302, 2021. Doi: 10.1007/s11128-021-03239-1
Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore’s law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available.