This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
The transition from theoretical quantum computing to practical real-world applications heavily relies onhybrid quantum-classical architectures designed for NoisyIntermediate-Scale Quantum (NISQ) devices. Among these approaches, the Quantum Approximate Optimization Algorithm(QAOA) is a prominent strategy for addressing complex combinatorial optimization challenges, such as the NP-hard MaxCut problem. Instead of performing the entire computationon a quantum processor, QAOA utilizes a quantum circuit toevaluate a parameterized cost function, whereas a classical optimizer refines the parameters iteratively. This study presentsa rigorous empirical evaluation comparing the performanceof QAOA against established classical solvers on small-scaleMax-Cut instances. All experiments were implemented andexecuted using Python (Qiskit Aer) on a state-vector simulator.Using Erdős–Rényi random graphs and regular graphs with4 to 20 nodes, we benchmark QAOA at depths p = 2 andp = 3 against simulated annealing, the Goemans–WilliamsonSDP-based algorithm, and a linear-time greedy heuristic. Ourexperimental results demonstrate that low-depth QAOA implementations exhibit severe performance degradation, prohibitive computational overhead (O(2^n) scaling), and low convergencerates compared to mature classical algorithms. At 20 nodes,QAOA (p = 2) achieves only a 0.467 approximation ratio versus0.856 for Goemans–Williamson, with a 210× runtime slowdownover greedy heuristics
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.
This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.