Quantum Approaches to NP-Hard Problems in Network Science: Community Detection Using the Potts Model

Community detection is a key problem in network science, where the goal is to identify groups of nodes that are more densely connected internally than with the rest of the network.In this thesis, we address the community detection problem by reformulating it within the framework of statistical physics using the q-state Potts model. The adjacency matrix of the graph is used to encode the structure of the network into the Hamiltonian, inspired by the formulation introduced by Reichardt and Bornholdt in their article "Statistical Mechanics of Community Detection." In this framework, each node of the graph is assigned a state (i.e., a community label), and the Hamiltonian penalizes or favors interactions between nodes depending on whether they belong to the same community. We encode community assignments as low-energy configurations of the Potts model Hamiltonian and employ a simulated annealing algorithm to minimize the system’s energy and identify the optimal number of communities in various networks. In the next step, we map the Potts model to a quantum formulation using Pauli matrices. To address the exponential growth of the Hilbert space with system size, we implement tensor network methods to represent quantum states efficiently. This task remains computationally challenging, especially for large or complex graphs, as the problem is NP-hard.