The Quantum Approximate Optimization Approach (QAOA) is a hybrid quantum-classical approach designed for solving NP-hard combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices. This study applies QAOA on a four-node Max-Cut problem to investigate the output between two IBM Quantum backends: ibm_torino (Heron r1) and ibm_brisbane (Eagle r3). The experiment uses fixed variational parameters γ=1.2 and β=2.4 for both backends, with a circuit depth of p=2. The ibm_torino backend always produced the right Max-Cut solutions by giving the right optimal bitstrings (0101 and 1010). The ibm_brisbane backend, on the other hand, sometimes gave the wrong bitstrings more often than the right ones. A hypothesis-driven analysis ascribes this discrepancy to variations in backend architecture, qubit connectivity, and parameter sensitivity, in addition to the simplicity of the unweighted four-node network employed.
The Quantum Approximate Optimization Approach (QAOA) is a hybrid quantum-classical approach designed for solving NP-hard combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices. This study applies QAOA on a four-node Max-Cut problem to investigate the output between two IBM Quantum backends: ibm_torino (Heron r1) and ibm_brisbane (Eagle r3). The experiment uses fixed variational parameters γ=1.2 and β=2.4 for both backends, with a circuit depth of p=2. The ibm_torino backend always produced the right Max-Cut solutions by giving the right optimal bitstrings (0101 and 1010). The ibm_brisbane backend, on the other hand, sometimes gave the wrong bitstrings more often than the right ones. A hypothesis-driven analysis ascribes this discrepancy to variations in backend architecture, qubit connectivity, and parameter sensitivity, in addition to the simplicity of the unweighted four-node network employed.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for near-term quantum advantage in combinatorial optimization. A central design parameter is circuit depth p, with theoretical analyses establishing asymptotic convergence under idealized conditions. This paper presents a limits study demonstrating that this theoretical relationship does not translate to measurable improvement on current noisy intermediate-scale quantum (NISQ) hardware for fault tree analysis applications. Across 120 QAOA executions on 60 QUBO-encoded fault tree instances (N ∈ {12, 16, 20, 24, 28, 32}) on IBM Quantum hardware (ibm_torino, 133-qubit Heron processor), circuit depths p = 1 and p = 2 were directly compared. The mean change in optimal state sampling probability from doubling circuit depth was Δmax_prob = 1.22 × 10⁻⁵ with a median Δ of zero. For 8,192 shots, the binomial sampling uncertainty is O(10⁻²); the observed mean delta is therefore approximately three orders of magnitude below the shot-noise scale, making the difference statistically indistinguishable from zero. Output distribution entropy approaches the theoretical maximum of log₂(8192) ≈ 13 bits, indicating hardware noise dominates algorithmic signal. These findings establish that for fault tree minimal cut set identification on current NISQ devices, computational resources are more effectively allocated to increased shot counts than to circuit depth. Complete experimental artifacts with SHA-256 verification are provided, enabling full reproducibility.
Full-pipeline benchmark of the Quantum Approximate Optimization Algorithm (QAOA) against classical combinatorial solvers on a weighted Max-Cut formulation of exam-scheduling conflict minimization. Compares random assignment, greedy heuristic, 2-opt local search, exact ILP (OR-Tools), and QAOA — first via noisy local simulation on an 18-qubit validation subset, then via live execution on IBM's ibm_marrakesh (Heron r2) processor at the full 42-qubit scale. Uses shot-weighted expected-value scoring throughout rather than best-observed-sample reporting. At 18 qubits QAOA reaches 95.4% of the proven optimum; at 42 qubits the hardware run's expected value falls below random guessing (49.05% vs 50.00%), with all 4,096 shots returning distinct bitstrings — the signature of decoherence overwhelming the circuit. Includes causal analysis of the failure mode and outlines planned comparison against quantum annealing hardware.
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.
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.