Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to its expected robustness to systematic errors and the short circuit depth, it is one of the promising candidates likely to run on near-term quantum devices. We project the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, both for exact or approximate solution. When comparing approximate solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we introduce performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives.
Solving optimization problems is critical across many research domains, but the high dimensionality of parameter spaces often poses significant challenges. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for accelerating optimization in the Noisy Intermediate-Scale Quantum (NISQ) era by leveraging both classical and quantum computational resources. However, its performance can vary depending on the underlying quantum hardware architecture. In this work, we evaluate the performance of QAOA on different quantum hardware platforms, specifically, superconducting transmon qubits and trapped-ion qubits, targetting real-world optimization problems formulated as fully connected Quadratic Unconstrained Binary Optimization (QUBO) instances. We evaluate both the solution quality and time-to-solution using dense QUBO matrices. Furthermore, we show that large-scale problems, such as a 100-bit QUBO instance, can be effectively tackled by integrating quantum computing with high-performance computing (HPC) resources. This study provides practical insights into the strengths and limitations of different qubit technologies and advances the application of quantum computing in solving real-world optimization problems.
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 Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for solving NP hard combinatorial optimization problems on noisy intermediate-scale quantum (NISQ) hardware. However, its performance is critically dependent on the selection of the circuit depth a parameter that must be specified a priori without clear guidance. In this paper, we introduce a variant of QAOA called dynamic depth Quantum Approximate Optimization Algorithm (DDQAOA) that resolves the challenge of pre selecting a fixed circuit depth. Our method adaptively expands circuit depth, starting from p = 1 and progressing up to p = 10, by transferring learned parameters to deeper circuits based on convergence criteria. We tested this approach on 100 instances of the Constrained Shortest Path Problem (CSPP) at 10 qubit and 16 qubit scales. Our DDQAOA achieved superior approximation ratios and success probabilities with fewer CNOT gate evaluations than the standard QAOA for p = 3, 5, 10, and 15. In particular, while standard QAOA at p = 15 achieved results close to our approach, it used 217% and 159.3% more CNOT gates for 10 qubit and 16 qubit instances, respectively. This demonstrates the performance and practical applicability of DDQAOA to solve combinatorial optimization problems on near term devices.