Using Error-Correcting Codes to Encode Colors in the Graph Community Detection Problem
Kaur, Jasleen
Community detection, the problem of partitioning a graph into densely connected groups, is a fundamental task in network analysis with applications which span social science, biology, and computer science. Maximizing the modularity objective, the dominant quality metric for community partitions, is NP-complete, motivating the use of quantum computing approaches such as the Quantum Approximate Optimization Algorithm (QAOA). A critical design choice in any QAOA formulation is how community membership is encoded in qubits. The studied approach, one-hot encoding, assigns K qubits per node for K communities, but suffers from high qubit overhead, complex constraint enforcement, and zero tolerance to measurement errors (Hamming distance of 2 between valid codewords). This thesis proposes and investigates the use of Hamming error-correcting codes as an alternative encoding for community membership in QAOA-based community detection. In the Hamming encoding, each node's community label is represented as a Hamming(7,4) or Hamming(8,4) codeword, a 7- or 8-bit string with structured parity redundancy that enables single-bit error correction via syndrome decoding after measurement. A modularity penalty Hamiltonian and a parity penalty Hamiltonian derived from the Hamming parity check matrix are constructed, and a complete QAOA pipeline including syndrome-based post-measurement decoding is implemented. A standard binary encoding (log2 K bits per node) is included as a third comparison point. The three encodings are systematically compared in both classical optimization (COBYLA for one-hot and binary; simulated annealing for Hamming) and QAOA quantum simulation (Qiskit Aer), in synthetic clique chain graphs (6–48 nodes) and three real-world benchmarks: Zachary's Karate Club, the Les Misérables co-appearance network, and the Davis Southern Women bipartite graph. Experiments are evaluated on feasibility and solution correctness rather than runtime, using a three-tier classification (completed, partial, failed). The results show that one-hot encoding at K=2 with COBYLA is the strongest classical approach overall, achieving correct partitions on synthetic graphs up to 24 nodes and on two real-world benchmarks (Karate Club and Davis Southern Women). Hamming encoding with simulated annealing also produces correct partitions on the Karate Club graph through a fundamentally different optimization mechanism, demonstrating that structured redundancy can improve classical optimization quality. In the QAOA setting, qubit count dominates feasibility: binary encoding (fewest qubits) extends the simulation frontier farthest, one-hot K=2 matches it via the XY mixer's structural constraint preservation, and Hamming encoding reaches the feasibility boundary earliest due to its 7 qubit per node overhead. However, the Hamming encoding's fixed cost of 7 qubits per node (supporting up to 16 communities) makes it more qubit-efficient than one-hot for K > 7. The thesis concludes that the Hamming formulation is not universally more efficient than one-hot encoding, but offers distinct advantages in regimes: classical optimization on well-structured graphs, multi-community problems where K is large. The principal direction for future work is to benchmark the Hamming-encoded QAOA on larger quantum hardware under physical noise and scale classical simulations to larger graphs to assess the encoding's practical advantages.
•Jan 1, 2026•0 citations