A Quantum Genetic Algorithm Framework For The MaxCut Problem

Abstract

The MaxCut problem is a fundamental problem in Combinatorial Optimization, with sig- nificant implications across diverse domains such as logistics, network design, and statistical

physics. The algorithm represents innovative approaches that balance theoretical rigor with practical scalability. The proposed method introduces a Quantum Genetic Algorithm (QGA)

using a Grover-based evolutionary framework and divide-and-conquer principles. By partition- ing graphs into manageable subgraphs, optimizing each independently, and applying graph

contraction to merge the solutions, the method exploits the inherent binary symmetry of Max- Cut to ensure a more efficient and robust approximation performance. Theoretical analysis

establishes a foundation for a better performance of the algorithm, while empirical evalua- tions provide quantitative evidence of its effectiveness. On complete graphs, the proposed

method consistently achieves the true optimal MaxCut values, outperforming the Semidefi- nite Programming (SDP) approach, which provides up to 99.7% of the optimal solution for

larger graphs. On Erdős-Rényi random graphs, the QGA demonstrates competitive perfor- mance, achieving median solutions within 92-96% of the SDP results. These results showcase

the potential of the QGA framework to deliver competitive solutions, even under heuristic constraints, while demonstrating its promise for scalability as quantum hardware evolves.