ABSTRACT Modularity maximization for community detection can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implemented with the Quantum Approximate Optimization Algorithm (QAOA). However, directly encoding the full modularity matrix yields a dense Hamiltonian with two‐qubit interactions, resulting in circuits that are too deep for simulators and near‐term quantum hardware. This work introduces a set of modularity‐preserving Hamiltonian encodings designed to reduce circuit complexity while retaining the structural information needed for community detection. The proposed methods include magnitude sparsification, top‐ filtering, energy‐based sparsification, low‐rank spectral projection, and penalty‐augmented formulations, adapting classical approximation strategies into more efficient quantum cost operators. The methods are evaluated on real social graphs and compared with the Louvain algorithm and the full modularity encoding. Results, averaged over multiple random seeds with confidence intervals, show that energy‐based and top‐ encodings achieve the best accuracy–runtime trade‐off, significantly reducing circuit complexity while maintaining competitive partition quality. Low‐rank and magnitude‐based sparsification preserve higher accuracy but are more noise‐sensitive, while penalty‐based formulations exhibit higher variability. Scalability experiments on 16‐, 20‐, and 24‐qubit encodings confirm these trends, and simulations under depolarizing noise indicate that energy‐based and top‐ methods remain among the most robust.
ABSTRACT Modularity maximization for community detection can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implemented with the Quantum Approximate Optimization Algorithm (QAOA). However, directly encoding the full modularity matrix yields a dense Hamiltonian with two‐qubit interactions, resulting in circuits that are too deep for simulators and near‐term quantum hardware. This work introduces a set of modularity‐preserving Hamiltonian encodings designed to reduce circuit complexity while retaining the structural information needed for community detection. The proposed methods include magnitude sparsification, top‐ filtering, energy‐based sparsification, low‐rank spectral projection, and penalty‐augmented formulations, adapting classical approximation strategies into more efficient quantum cost operators. The methods are evaluated on real social graphs and compared with the Louvain algorithm and the full modularity encoding. Results, averaged over multiple random seeds with confidence intervals, show that energy‐based and top‐ encodings achieve the best accuracy–runtime trade‐off, significantly reducing circuit complexity while maintaining competitive partition quality. Low‐rank and magnitude‐based sparsification preserve higher accuracy but are more noise‐sensitive, while penalty‐based formulations exhibit higher variability. Scalability experiments on 16‐, 20‐, and 24‐qubit encodings confirm these trends, and simulations under depolarizing noise indicate that energy‐based and top‐ methods remain among the most robust.
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.
We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structures. We implement a multi-level algorithm that iteratively refines community assignments by alternating between QUBO problem setup and QHD-based optimization. Benchmarking shows our method achieves up to 5.49% better modularity scores while requiring less computational time compared to classical optimization approaches. This work demonstrates the potential of hybrid quantum-inspired solutions for advancing community detection in largescale graph data.
Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.