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.
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.
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.
The design of fast algorithms for combinatorial optimization greatly contributes to a plethora of domains such as logistics, finance, and chemistry. Quantum approximate optimization algorithms (QAOAs), which utilize the power of quantum machines and inherit the spirit of adiabatic evolution, are approaches to tackle combinatorial problems with potential runtime speedups. However, hurdled by the limited quantum resources nowadays, QAOAs are infeasible to manipulate large-scale problems. To address this issue, here we revisit the MaxCut problem via the divide-and-conquer heuristic: seek the solutions of subgraphs in parallel and then merge these solutions to obtain the global solution. Because of the Z2 symmetry in MaxCut, we prove that the merging process can be further cast into a new MaxCut problem and thus be addressed by QAOAs or other MaxCut solvers. In view of this, we propose QAOA-in-QAOA (QAOA2) to solve arbitrary large-scale MaxCut problems using small quantum machines. We also prove that the performance of QAOA2 is lower bounded with respect to the divide-and-conquer process. Experiment results illustrate that, under different graph settings, QAOA2 attains a competitive or even better performance over classical algorithms when the node count is around 2000. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale combinatorial optimization problems.
The Quantum Circuit Compilation Problem (QCCP) is challenging to the Artificial Intelligence community. It was already tackled with temporal planning, constraint programming, greedy heuristics and other techniques. In this paper, QCCP is formulated as a scheduling problem and solved by a genetic algorithm. We focus on QCCP for Quantum Approximation Optimization Algorithms (QAOA) applied to the MaxCut problem and consider Noisy Intermediate Scale Quantum (NISQ) hardware architectures. Based on the fact that these algorithms apply a set of basic quantum operations repeatedly over a number of rounds, we propose a genetic algorithm approach, termed Decomposition Based Genetic Algorithm (DBGA), that in each round extends the partial solutions obtained for the previous ones. DBGA is compared to the state of the art across a set of conventional instances. The results of the experimental study provided interesting insight in the problem structure and showed that DBGA is quite competitive with the state of the art. In particular, DBGA outperformed the best current method on the largest instances and provided new best solutions to most of them.
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.
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.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.