arXiv:2504.05989 · Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

Comparative Analysis of Classical and Quantum-Inspired Solvers: A Preliminary Study on the Weighted Max-Cut Problem

Aitor Morais, Eneko Osaba, Iker Pastor-López, Izaskun Oregi

Published Jul 14, 2025• 2 citations

Abstract

Combinatorial optimization is essential across numerous disciplines. Traditional metaheuristics excel at exploring complex solution spaces efficiently, yet they often struggle with scalability. Deep learning has become a viable alternative for quickly generating high-quality solutions, particularly when metaheuristics underperform. In recent years, quantum-inspired approaches such as tensor networks have shown promise in addressing these challenges. Despite these advancements, a thorough comparison of the different paradigms is missing. This study evaluates eight algorithms on Weighted Max-Cut graphs ranging from 10 to 250 nodes. Specifically, we compare a Genetic Algorithm representing metaheuristics, a Graph Neural Network for deep learning, and the Density Matrix Renormalization Group as a tensor network approach. Our analysis focuses on solution quality and computational efficiency (i.e., time and memory usage). Numerical results show that the Genetic Algorithm achieves near-optimal results for small graphs, although its computation time grows significantly with problem size. The Graph Neural Network offers a balanced solution for medium-sized instances with low memory demands and rapid inference, yet it exhibits more significant variability on larger graphs. Meanwhile, the Tensor Network approach consistently yields high approximation ratios and efficient execution on larger graphs, albeit with increased memory consumption.

DOI: 10.1145/3712255.3734363

Related papers

Unsupervised learning with GNNs for QUBO-based combinatorial optimization

Olga Valerevna Krylova, Frank Phillipson

Recent advances in deep learning techniques pose a question of whether they can facilitate the task of finding good quality solutions to combinatorial optimization (CO) problems in a practically relevant solution time. Specifically, it is of practical relevance to determine to which extent graph neural networks (GNNs) can be applied to CO problems that can be formulated as QUBO’s and thus be naturally interpreted as graph problems. In this research a GNNsolver is applied to two classical CO problems–the maximum cut problem and maximum independent set problem–in an unsupervised learning setting. We show that while GNN solver consistently finds good quality solutions for the Max Cut problem irrespective of the size and density of the graph, solving MIS problems is challenging for all but very sparse graphs. We further show how this problem can be addressed by embedding transfer between these two problems and compare two different GNN architectures–GCN and GraphSAGE on their robustness with respect to graph density and symmetry. Finally we demonstrate that change of widely used Adam optimizer to Rprop optimizer can lead to considerable reduction of solution times. • Previously suggested GNNsolver is effective on sparse graphs only. • Replacing Adam with RPROP reduced solution times. • GraphSAGE can handle denser graphs, GCN performs better on sparse graphs. • Transfer learning between MaxCut and MIS problems improves solvers performance.

EURO Journal on Computational OptimizationJan 1, 20250 citations

A Quantum Genetic Algorithm Framework For The MaxCut Problem

Paulo André Viana de Araújo

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.

Jan 30, 20250 citations

Quantum-Enhanced Network Flow Optimization: A Max-Flow Min-Cut Perspective

Gagan Guruprasad Phadke, Vandana M. Ladwani

This paper is a comparison between classical and quantum inspired methods for solving the max-flow problem, which is commonly a foundational challenge in optimization and graph theory. This study will investigate the feasibility and performance of applying the Quantum Approximate Optimization Algorithm (QAOA) and other hybrid quantum-classical approaches to address the max-flow problem. This paper starts with comparing quantum approaches with well-established classical methods such as the Ford-Fulkerson and Edmonds-Karp.The main aim of this work is to asses how close quantum-inspired formulations can get to classical approaches in terms of their flow value as well as their runtime. Implementations are developed using the Qiskit framework on simulated quantum backends and compared against classical baselines across synthetic graph instances of varying sizes and densities. Experimentally, it can be seen that quantum approaches implemented using the QAOA technique managed to attain flow solutions comparable to classical ones, demonstrating similar accuracy, and in certain very dense graph configurations, competitive runtime performance due to parallelization in state-vector computing.These findings suggest that although current quantum-inspired approaches may not yet surpass classical algorithms in efficiency, but they can replicate their outcomes with reasonable fidelity. This provides an important validation of their applicability to combinatorial optimization. This study also lays groundwork for future research to explore hardware-level implementations, scalability enhancements, and also hybrid integration strategies for quantum optimization in network flow problems.

International Conference on Next-Gen Quantum and Advanced Computing: Algorithms, Security, and Beyond (NQComp)Mar 5, 20260 citations

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.

Quantum Information ProcessingSep 23, 20251 citation

A Quantum Genetic Algorithm Framework for the MaxCut Problem

Paulo A. Viana, Fernando M. de Paula Neto

The MaxCut problem is a fundamental problem in Combinatorial Optimization, with significant 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 partitioning graphs into manageable subgraphs, optimizing each independently, and applying graph contraction to merge the solutions, the method exploits the inherent binary symmetry of MaxCut to ensure computational efficiency and robust approximation performance. Theoretical analysis establishes a foundation for the efficiency of the algorithm, while empirical evaluations provide quantitative evidence of its effectiveness. On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite 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 performance, 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.

arXiv:2501.01058Jan 2, 20250 citations

Integrating Quantum Approximate Optimization Algorithm with Machine Learning for Graph-Structured Problem Solving

Dr. Mamta Singh

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.

Mar 25, 20260 citations