Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Using Error-Correcting Codes to Encode Colors in the Graph Community Detection Problem

Jasleen Kaur

Published Jan 1, 2026• 0 citations
Publisher

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.

DOI
10.71548/9

Related papers

Community detection by simulated bifurcation

Wei Li, Yi-Lun Du, Nan Su +3 more

Community detection, also known as graph partitioning, is a well-known NP-hard combinatorial optimization problem with applications in diverse fields such as complex network theory, transportation, and smart power grids. The problem's solution space grows drastically with the number of vertices and subgroups, making efficient algorithms crucial. In recent years, quantum computing has emerged as a promising approach to tackling NP-hard problems. This study explores the use of a quantum-inspired algorithm, Simulated Bifurcation (SB), for community detection. Modularity is employed as both the objective function and a metric to evaluate the solutions. The community detection problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling seamless integration with the SB algorithm. Experimental results demonstrate that SB effectively identifies community structures in benchmark networks such as Zachary's Karate Club and the IEEE 33-bus system. Remarkably, SB achieved the highest modularity, matching the performance of Fujitsu's Digital Annealer, while surpassing results obtained from two quantum machines, D-Wave and IBM. These findings highlight the potential of Simulated Bifurcation as a powerful tool for solving community detection problems.

arXiv:2501.00075•Dec 30, 2024•2 citations

Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

Tristan Zaborniak, Prashanti Priya Angara, Vikram Khipple Mulligan +2 more

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.

quant-pharXiv:2604.21123•Apr 24, 2026•1 citation

Design, decoding, and fault-tolerant implementation of quantum error-correcting codes

Diego Forlivesi

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.

•Jun 29, 2026•0 citations

Syndrome decoding by quantum approximate optimization

Ching–Yi Lai, Kao-Yueh Kuo, Bo-Jyun Liao

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.

arXiv:2207.05942•Quantum Information Processing•Nov 1, 2024•9 citations

NISQ-Ready Community Detection Based on Separation-Node Identification

Jonas Stein, Dominik Ott, Jonas Nüßlein +3 more

The analysis of network structure is essential to many scientific areas ranging from biology to sociology. As the computational task of clustering these networks into partitions, i.e., solving the community detection problem, is generally NP-hard, heuristic solutions are indispensable. The exploration of expedient heuristics has led to the development of particularly promising approaches in the emerging technology of quantum computing. Motivated by the substantial hardware demands for all established quantum community detection approaches, we introduce a novel QUBO-based approach that only needs number-of-nodes qubits and is represented by a QUBO matrix as sparse as the input graph’s adjacency matrix. The substantial improvement in the sparsity of the QUBO matrix, which is typically very dense in related work, is achieved through the novel concept of separation nodes. Instead of assigning every node to a community directly, this approach relies on the identification of a separation-node set, which, upon its removal from the graph, yields a set of connected components, representing the core components of the communities. Employing a greedy heuristic to assign the nodes from the separation-node sets to the identified community cores, subsequent experimental results yield a proof of concept by achieving an up to 95% optimal solution quality on three established real-world benchmark datasets. This work hence displays a promising approach to NISQ-ready quantum community detection, catalyzing the application of quantum computers for the network structure analysis of large-scale, real-world problem instances.

arXiv:2212.14717•Mathematics•Jul 28, 2023•5 citations

Quantum k-community detection: algorithm proposals and cross-architectural evaluation

Felix Gemeinhardt, Robert Wille, Manuel Wimmer

Abstract Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore’s law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available.Reproducibility:Our code and data are publicly available (Github in Quantum Modularization. https://github.com/jku-win se/quantum_modularization 2021).

Quantum Information Processing•Sep 1, 2021•17 citations
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, also known as graph partitioning, is a well-known NP-hard combinatorial optimization problem with applications in diverse fields such as complex network theory, transportation, and smart power grids. The problem's solution space grows drastically with the number of vertices and subgroups, making efficient algorithms crucial. In recent years, quantum computing has emerged as a promising approach to tackling NP-hard problems. This study explores the use of a quantum-inspired algorithm, Simulated Bifurcation (SB), for community detection. Modularity is employed as both the objective function and a metric to evaluate the solutions. The community detection problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling seamless integration with the SB algorithm. Experimental results demonstrate that SB effectively identifies community structures in benchmark networks such as Zachary's Karate Club and the IEEE 33-bus system. Remarkably, SB achieved the highest modularity, matching the performance of Fujitsu's Digital Annealer, while surpassing results obtained from two quantum machines, D-Wave and IBM. These findings highlight the potential of Simulated Bifurcation as a powerful tool for solving community detection problems.
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.
The analysis of network structure is essential to many scientific areas ranging from biology to sociology. As the computational task of clustering these networks into partitions, i.e., solving the community detection problem, is generally NP-hard, heuristic solutions are indispensable. The exploration of expedient heuristics has led to the development of particularly promising approaches in the emerging technology of quantum computing. Motivated by the substantial hardware demands for all established quantum community detection approaches, we introduce a novel QUBO-based approach that only needs number-of-nodes qubits and is represented by a QUBO matrix as sparse as the input graph’s adjacency matrix. The substantial improvement in the sparsity of the QUBO matrix, which is typically very dense in related work, is achieved through the novel concept of separation nodes. Instead of assigning every node to a community directly, this approach relies on the identification of a separation-node set, which, upon its removal from the graph, yields a set of connected components, representing the core components of the communities. Employing a greedy heuristic to assign the nodes from the separation-node sets to the identified community cores, subsequent experimental results yield a proof of concept by achieving an up to 95% optimal solution quality on three established real-world benchmark datasets. This work hence displays a promising approach to NISQ-ready quantum community detection, catalyzing the application of quantum computers for the network structure analysis of large-scale, real-world problem instances.
Abstract Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore’s law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available.Reproducibility:Our code and data are publicly available (Github in Quantum Modularization. https://github.com/jku-win se/quantum_modularization 2021).