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.
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.
We introduce a qubit- and gate-efficient higher-order unconstrained binary optimization (HUBO) encoding for graph partitioning problems requiring label-count minimization. This widely applicable class of problems includes minimum graph coloring, minimum \textit{k}-cut, and community detection. To the best of our knowledge, this is the first work to address the optimization versions of these problems in a quantum setting, rather than only their decision counterparts. Our construction encodes each vertex variable in a number of bits logarithmic in the number of available labels---the information-theoretic minimum---and employs a novel lexicographic penalty system that implicitly minimizes partition count without requiring dedicated indicator variables. We derive provably sufficient conditions on all penalty coefficients, including those arising from Rosenberg quadratization, guaranteeing feasibility and optimality of the lowest-energy solution. Analogous conditions are derived for a one-hot encoding to enable controlled comparison. We also show that our encoding reduces two-qubit gate count per layer of the quantum approximate optimization algorithm (QAOA). Benchmarking on a quantum annealer demonstrates that our logarithmic encoding greatly improves solution quality and time-to-solution for minimum graph coloring relative to one-hot encoding, with greater advantage as problem size increases.
Quantum computation promises to revolutionize information processing by exploiting superposition and entanglement, enabling applications such as quantum simulation, combinatorial optimization, and secure quantum communication. Beyond individual processors, the quantum internet aims to connect quantum nodes through entanglement distribution, enabling distributed computation. However, quantum states are fragile: environmental interactions, imperfect gate operations, and measurement errors can quickly degrade encoded information. Reliable quantum computation therefore requires carefully designed quantum error-correcting codes and fault-tolerant protocols. Unlike classical redundancy schemes, quantum error correction must preserve delicate phase relationships and relies on indirect error detection through syndrome extraction with ancillary qubits, enabling error identification without collapsing encoded states. Topological codes, in particular, emerged early as the preferred choice for many architectures due to their planar structure, local interactions, and natural support for fault-tolerant logical operations. Color codes, for instance, allow transversal implementation of all Clifford gates, whereas non-Clifford operations require magic-state injection. More recent constructions, including quantum low-density parity-check codes, offer higher encoding rates and reduced resource overhead, but require long-range qubit connectivity and more complex protocols. Despite experimental progress, several challenges remain. Many platforms exhibit biased noise, motivating codes that exploit channel asymmetry. Real-time decoding remains a critical bottleneck, as fault-tolerant computation requires low-latency processing of rapidly generated syndrome data. Fault-tolerant logical state initialization also remains resource-intensive and scales poorly with code distance. Addressing these challenges, this thesis develops a unified framework spanning theory and experiment. It provides precise performance analysis of quantum error-correcting codes in the low physical error-rate regime, introduces codes tailored to biased noise, develops fast low-complexity decoding algorithms for real-time operation, and presents modular and efficient protocols for fault-tolerant state preparation of CSS codes. The latter is demonstrated experimentally through the preparation of a logical zero state of the Golay code on the Quantinuum H2 trapped-ion quantum computer.
Abstract The syndrome decoding problem is known to be NP-complete. The goal of the decoder is to find an error of low weight that corresponds to a given syndrome obtained from a parity-check matrix. We use the quantum approximate optimization algorithm (QAOA) to address the syndrome decoding problem with elegantly-designed reward Hamiltonians based on both generator and check matrices for classical and quantum codes.We evaluate the level-4 check-based QAOA decoding of the [7,4,3] Hamming code, as well as the level-4 generator-based QAOA decoding of the [[5,1,3]] quantum code.Remarkably, the simulation results demonstrate that the decoding performances match those of the maximum likelihood decoding. Moreover, we explore the possibility of enhancing QAOA by introducing additional redundant clauses to a combinatorial optimization problem while keeping the number of qubits unchanged. Finally, we study QAOA decoding of degenerate quantum codes.Typically, conventional decoders aim to find a unique error of minimum weight that matches a given syndrome. However, our observations reveal that QAOA has the intriguing ability to identify degenerate errors of comparable weight, providing multiple potential solutions that match the given syndrome with comparable probabilities.This is illustrated through simulations of the generator-based QAOA decoding of the [[9,1,3]] Shor code on specific error syndromes.
This thesis explores quantum computing for combinatorial optimization through the Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via the Gurobi solver. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with degree and subtour constraints embedded using quadratic penalties. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound solvers outperform it in both solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap grows with problem size, reflecting sensitivity to variational parameter tuning, penalty scaling, and hardware noise. Among classical optimizers for QAOA, COBYLA offers the most effective tradeoff between efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
Building reliable quantum computers requires protecting fragile quantum states from inevitable environmental noise and operational errors. While quantum error correction codes like the Steane [[7,1,3]] code provide elegant theoretical solutions, their practical success hinges critically on how we measure errors - a process called syndrome extraction. The challenge lies in the ancilla qubits used for measurement: when they fail, errors can cascade across the entire quantum system, destroying the very information we're trying to protect. We address this fundamental problem by implementing and comparing three sophisticated syndrome measurement strategies: Shor's cat-state approach, which distributes measurements across multiple entangled ancillas achieving 85-92% preparation success; Steane's encoded-ancilla method using complete error-corrected logical qubits reaching 97.8% syndrome fidelity; and a flexible unified framework that adapts strategies based on hardware capabilities. Through extensive simulations using IBM's Qiskit platform spanning randomized benchmarking and T-heavy circuits, we demonstrate that intelligent ancilla management improves error suppression by up to 2.4× compared to standard approaches. Our implementations achieve logical error rates as low as 5.1×10−5 under realistic noise conditions with physical error rates of 10−3, while maintaining near-unity logical fidelity (0.99997) even for deep circuits. The threshold analysis reveals robust performance across distance-3 to distance-13 codes with characteristic threshold curves showing exponential error suppression below the critical physical error rate. These results provide immediately deployable tools for near-term quantum devices and establish practical design principles for scaling toward fault-tolerant quantum computers.
Quantum computing holds the potential to efficiently solve certain problems believed to be intractable for classical computers. Realizing this potential, however, requires substantial physical resources, including large qubit counts, sufficient connectivity, and long coherence times. As current quantum devices are still far from this regime, the efficient compilation of quantum algorithms into hardware-compatible instructions remains a central challenge in quantum computing, especially for near-term applications. A representative example of such applications is combinatorial optimization, where exponentially large search spaces motivate quantum algorithms that leverage interference to approximate solutions more efficiently than classical heuristics, even at modest system sizes. Two prominent paradigms in this context are quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA): Quantum annealing realizes optimization via continuous-time quantum dynamics implemented on analog hardware, while QAOA is a variational, gate-based approach that builds parameterized quantum circuits from problem-specific Hamiltonians. Both paradigms require compilation strategies tailored to the constraints of their respective hardware architectures. Most existing compilation strategies are problem-agnostic and therefore broadly applicable, yet often suboptimal for specific tasks. This thesis uses the graph coloring problem as a case study to investigate a problem-driven approach to quantum compilation, where structural features of the problem class are exploited to design tailored compilation schemes that offer improved efficiency and scalability for the targeted application. To address hardware connectivity constraints, the presented approaches adopt the parity framework, which encodes long-range interactions into single-qubit terms. This thesis develops two novel problem-driven compilation methods for the graph coloring problem, the Bandwidth-Optimized LHZ layout and the 2D-Twine circuit. The former leverages bandwidth minimization to optimize parity encodings for analog quantum annealers, while the latter constructs QAOA unitaries for gate-based optimization using parallelized Parity Twine circuits. Both approaches are benchmarked against general-purpose methods and demonstrate substantial improvements in qubit usage or circuit complexity. These results illustrate the advantages of incorporating problem structure into the compilation process and provide a proof-of-concept for the effectiveness of problem-driven compilation strategies.