<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T01:26:00Z</responseDate><request verb="GetRecord" identifier="oai:macsphere.mcmaster.ca:11375/33145" metadataPrefix="dim">https://prod-ms-be.lib.mcmaster.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:macsphere.mcmaster.ca:11375/33145</identifier><datestamp>2026-05-15T07:10:07Z</datestamp><setSpec>com_11375_271</setSpec><setSpec>col_11375_272</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Anand, Christopher Kumar</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author">Kaur, Jasleen</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="department">Computational Engineering and Science</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2026-05-14T12:26:18Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2026</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/11375/33145</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://doi.org/10.71548/9</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">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.</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="sponsorship">IBM Centre for Advanced Studies</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="degreetype">Thesis</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="degree">Master of Science (MSc)</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Attribution-NonCommercial-ShareAlike 4.0 International</dim:field>
   <dim:field mdschema="dc" element="rights" qualifier="uri">http://creativecommons.org/licenses/by-nc-sa/4.0/</dim:field>
   <dim:field mdschema="dc" element="subject">Community Detection</dim:field>
   <dim:field mdschema="dc" element="subject">Quantum Computing</dim:field>
   <dim:field mdschema="dc" element="title">Using Error-Correcting Codes to Encode Colors in the Graph Community Detection Problem</dim:field>
   <dim:field mdschema="dc" element="type">Thesis</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim></metadata></record></GetRecord></OAI-PMH>