Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A Topology-Driven Quantum Suitability Estimator for Hybrid QAOA–Classical Pipelines

Rohan Boddu

Published Aug 11, 2026• 0 citations
Publisher

Abstract

Abstract Quantum processing units are scarce. Schedulers dispatch Max-Cut subgraphs to them anyway, rarely pausing to ask whether a cheap classical heuristic would have closed the gap just as well. This routing blindness wastes exactly the resource it can least afford to waste. QSE—a Topology-Driven Quantum Suit-ability Estimator—answers a narrower question than either QAOA or a classical heuristic can answer alone. Using only polynomial-time graph topology features, its four-phase pipeline routes each Max-Cut subgraph to the Quantum Approximate Optimization Algorithm (QAOA), to a classical greedy heuristic, or to human review, whichever the topology signal warrants. Central to this decision is a single quantity: the expected greedy gap, f cmax = 1 − ¯ c greedy /c *. It captures how far a 15-ordering-averaged greedy heuristic falls short of the exact Max-Cut optimum—no more, no less. 137 graphs, drawn from 18 structural families at N = 16, clear three pre-registered validation bars. Hardness exists (max(f cmax) = 0.2444); a cross-validated random forest learns it from topology alone (R 2 RF = 0.527 ± 0.11); and, more tellingly, a single feature—transitivity—tracks it almost linearly (|r| = 0.676). Reaching these results required repairing a self-calibrating sign-alignment layer for QAOA simulation, introduced after two earlier implementations silently violated the [0, m] physicality bound on every one of 105 runs; the repair eliminates the violation entirely. Trained on the resulting 105 physically valid QAOA evaluations , a meta-router (regressor R 2 CV = 0.506 ± 0.119; classifier accuracy 76.2%, ROC-AUC 0.834) feeds a production scheduler. That scheduler computes a polynomial-time spectral proxy for hardness and reports per-decision uncertainty as a tree-ensemble spread. Rather than forcing a verdict, ambiguous cases are downgraded to REVIEW. Alongside these results, we document three classes of engineering failure—a Hamiltonian sign-convention bug, a graph-reconstruction seed mismatch, and five fabricated-input bugs in an earlier scheduler—each diagnosed and corrected, since the diagnoses prove as informative as the final numbers.

DOI
10.21203/rs.3.rs-10220081/v1

Related papers

When the Device Decides: Calibration-Conditioned Suitability Estimation for Hybrid QAOA–Classical Max-Cut Pipelines

Rohan Boddu

Abstract A topology-driven suitability estimator answers whether a Max-Cut instance deserves quantum hardware. This paper asks the question that estimator cannot: does the answer change with the device? Extending the QSE framework from noiseless simulation to calibration-conditioned noise models of three IBM chip generations — Falcon (Guadalupe, cx), Eagle (Brisbane, ecr), and Heron (Torino, cz) — we evaluate depth-1 QAOA on 100 graphs from 12 structural families at N=10 and N=12, producing 300 physically valid (graph, device) evaluations. Three findings emerge. First, a negative baseline stronger than any in the noiseless literature: under calibrated noise, p=1 QAOA loses to a 15- ordering-averaged greedy heuristic on 300 of 300 instances (mean ratios 0.759 vs. 0.934), and even noiseless p=1 QAOA loses on all instances (0.803). Second, the degree of loss is predictable and device-dependent: a random forest reaches graph-grouped CV R2 = 0.431±0.086 from topology alone and 0.467±0.085 when calibration and transpilation features are added; a median-split relativeamenability classifier attains accuracy 0.77 and ROC-AUC 0.858 from topology alone, with average clustering the dominant signal (r = 0.56 with quantum utility). Third, a diagnostic negative result: a classifier asked to pick the better of the two modern backends per graph fails completely (AUC 0.434 vs. base rate 0.57) — and the failure is correct, because per-graph Torino–Brisbane differences sit at the shot-noise floor (paired t-test p = 0.03–0.07 across simulator seeds), whereas the Falcon–Eagle generation gap is decisive (p ≈ 10−28). A 4096-shot rerun confirms the diagnosis in both directions: the tie resolves (p = 2.5×10−11, Torino ahead by 0.004 in mean ratio) and the classifier rises to AUC 0.64 — a real but operationally minor ranking. Device-conditioning matters at the granularity of chip generations, not of individual healthy devices. An extension to the original 137-graph QSE benchmark at N=16 (411 further evaluations) confirms every finding and strengthens all learnability results (ratio R2 = 0.82; 1 amenability AUC 0.966; 0 QAOA wins in 711 total evaluations), and the full benchmark executed on three Heron R2 production devices (300 hardware evaluations, 94 s of QPU time) validates the study end-to-end: snapshot predictions hold at MAE ≤ 0.010, QAOA wins 0 of 1,221 evaluations overall, the amenability classifier transfers to hardware labels (AUC 0.827; 94% label agreement), and same-generation devices separate at 1024 shots (p ≤ 2.6 × 10−3) by an operationally minor 0.010. We also document how the greedy-gap hardness signal central to QSE collapses below N=16 (same-protocol RF R2 falls from 0.306 to 0.076; transitivity correlation from −0.564 to −0.351) — re-derivation on the original benchmark exposing a greedy-protocol difference that confounds naive cross-study comparisons — and two engineering failures — a ZZ-phase sign-convention bug caught by a cross-simulator parity check, and transpiler gatedirection faults in legacy Falcon noise models — whose diagnoses shaped the final pipeline.

•Aug 19, 2026•0 citations

Where NISQ-Era Quantum Optimization Stands Today: An Honest Benchmark of QAOA Against Classical Heuristics on a Real-World Exam-Scheduling Max-Cut Problem

Prashant ARYA, Cybergeon Technologies India

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.

•Jul 25, 2026•0 citations

MillionQAOA: A Dividable QAOA Framework for Solving Million-Vertex-Scale Max-Cut Problems

Xie-Ru Li, Po-Hsuan Huang, Chia-Heng Tu +1 more

Hybrid quantum-classical optimization has made the Quantum Approximate Optimization Algorithm (QAOA) a leading candidate for combinatorial optimization tasks, and Max-Cut stands out among them for its broad practical footprint and its clean reduction to QUBO and Ising form. Prior divide-and-conquer adaptations push QAOA toward larger inputs, yet they stay capped at tens of thousands of vertices and never engage modern GPU cluster hardware, leaving million-scale instances out of reach. This work closes that gap with MillionQAOA, a GPU-accelerated divide-and-conquer framework capable of solving Max-Cut instances of up to one million vertices on multi-node H100 GPU clusters. The framework is organized as a four-phase, topology-aware pipeline: parallel graph synthesis, solver-shard formation, concurrent GPU-parallel circuit solving, and candidate consolidation through boundary binning paired with a layer-wise frontier expansion. On a testbed of 8 DGX-H100 nodes (64 GPUs in total), MillionQAOA scales near-linearly from 62.5K through 1M vertices, matches classical greedy solvers in cut quality at the 50K-vertex mark (within 0.2% higher), and cuts execution time by up to 13.6 ×, making it a deployable route to million-vertex Max-Cut at scale.

Proceedings of the International Conference on Parallel Processing•Sep 13, 2026•0 citations

Benchmarking QAOA vs Classical Algorithms for Max-Cut Optimization

Ayan Khan

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.

•Jan 1, 2026•0 citations

Benchmarking QAOA vs Classical Algorithms for Max-Cut Optimization

Ayan Khan

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.

•May 6, 2026•0 citations

What do QAOA energies reveal about graphs?

Márió Szegedy

Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum algorithm to approximately solve NP optimization problems such as MAX-CUT. We describe a new application area of QAOA circuits: graph structure discovery. We omit the time-consuming parameter-optimization phase and utilize the dependence of QAOA energy on the graph structure for randomly or judiciously chosen parameters to learn about graphs. In the first part, Following up on Wang et. al. and Brandao et. al. we give explicit formulas. We show that the layer-one QAOA energy for the MAX-CUT problem for three regular graphs carries exactly the information: {\em (# of vertices, # of triangles)}. We have calculated our explicit formulas differently from \cite{wang2018quantum}, by developing the notion of the $U$ polynomial of a graph $G$. Many of our discoveries can be interpreted as computing $U(G)$ under various restrictions. The most basic question when comparing the structure of two graphs is if they are isomorphic or not. We find that the QAOA energies separate all non-isomorphic three-regular graphs up to size 18, all strongly regular graphs up to size 26 and the Praust and the smallest Miyazaki examples. We observe that the QAOA energy values can be also used as a proxy to how much graphs differ. Unfortunately, we have also found a sequence of non-isomorphic pairs of graphs, for which the energy gap seems to shrink at an exponential rate as the size grows. Our negative findings however come with a surprise: if the QAOA energies do not measurably separate between two graphs, then both of their energy landscapes must be extremely flat (indistinguishable from constant), already when the number of QAOA layers is intermediately large. This holds due to a remarkable uncoupling phenomenon that we have only deduced from computer simulation.

arXiv:1912.12277•Dec 27, 2019•13 citations
Abstract Quantum processing units are scarce. Schedulers dispatch Max-Cut subgraphs to them anyway, rarely pausing to ask whether a cheap classical heuristic would have closed the gap just as well. This routing blindness wastes exactly the resource it can least afford to waste. QSE—a Topology-Driven Quantum Suit-ability Estimator—answers a narrower question than either QAOA or a classical heuristic can answer alone. Using only polynomial-time graph topology features, its four-phase pipeline routes each Max-Cut subgraph to the Quantum Approximate Optimization Algorithm (QAOA), to a classical greedy heuristic, or to human review, whichever the topology signal warrants. Central to this decision is a single quantity: the expected greedy gap, f cmax = 1 − ¯ c greedy /c *. It captures how far a 15-ordering-averaged greedy heuristic falls short of the exact Max-Cut optimum—no more, no less. 137 graphs, drawn from 18 structural families at N = 16, clear three pre-registered validation bars. Hardness exists (max(f cmax) = 0.2444); a cross-validated random forest learns it from topology alone (R 2 RF = 0.527 ± 0.11); and, more tellingly, a single feature—transitivity—tracks it almost linearly (|r| = 0.676). Reaching these results required repairing a self-calibrating sign-alignment layer for QAOA simulation, introduced after two earlier implementations silently violated the [0, m] physicality bound on every one of 105 runs; the repair eliminates the violation entirely. Trained on the resulting 105 physically valid QAOA evaluations , a meta-router (regressor R 2 CV = 0.506 ± 0.119; classifier accuracy 76.2%, ROC-AUC 0.834) feeds a production scheduler. That scheduler computes a polynomial-time spectral proxy for hardness and reports per-decision uncertainty as a tree-ensemble spread. Rather than forcing a verdict, ambiguous cases are downgraded to REVIEW. Alongside these results, we document three classes of engineering failure—a Hamiltonian sign-convention bug, a graph-reconstruction seed mismatch, and five fabricated-input bugs in an earlier scheduler—each diagnosed and corrected, since the diagnoses prove as informative as the final numbers.
Abstract A topology-driven suitability estimator answers whether a Max-Cut instance deserves quantum hardware. This paper asks the question that estimator cannot: does the answer change with the device? Extending the QSE framework from noiseless simulation to calibration-conditioned noise models of three IBM chip generations — Falcon (Guadalupe, cx), Eagle (Brisbane, ecr), and Heron (Torino, cz) — we evaluate depth-1 QAOA on 100 graphs from 12 structural families at N=10 and N=12, producing 300 physically valid (graph, device) evaluations. Three findings emerge. First, a negative baseline stronger than any in the noiseless literature: under calibrated noise, p=1 QAOA loses to a 15- ordering-averaged greedy heuristic on 300 of 300 instances (mean ratios 0.759 vs. 0.934), and even noiseless p=1 QAOA loses on all instances (0.803). Second, the degree of loss is predictable and device-dependent: a random forest reaches graph-grouped CV R2 = 0.431±0.086 from topology alone and 0.467±0.085 when calibration and transpilation features are added; a median-split relativeamenability classifier attains accuracy 0.77 and ROC-AUC 0.858 from topology alone, with average clustering the dominant signal (r = 0.56 with quantum utility). Third, a diagnostic negative result: a classifier asked to pick the better of the two modern backends per graph fails completely (AUC 0.434 vs. base rate 0.57) — and the failure is correct, because per-graph Torino–Brisbane differences sit at the shot-noise floor (paired t-test p = 0.03–0.07 across simulator seeds), whereas the Falcon–Eagle generation gap is decisive (p ≈ 10−28). A 4096-shot rerun confirms the diagnosis in both directions: the tie resolves (p = 2.5×10−11, Torino ahead by 0.004 in mean ratio) and the classifier rises to AUC 0.64 — a real but operationally minor ranking. Device-conditioning matters at the granularity of chip generations, not of individual healthy devices. An extension to the original 137-graph QSE benchmark at N=16 (411 further evaluations) confirms every finding and strengthens all learnability results (ratio R2 = 0.82; 1 amenability AUC 0.966; 0 QAOA wins in 711 total evaluations), and the full benchmark executed on three Heron R2 production devices (300 hardware evaluations, 94 s of QPU time) validates the study end-to-end: snapshot predictions hold at MAE ≤ 0.010, QAOA wins 0 of 1,221 evaluations overall, the amenability classifier transfers to hardware labels (AUC 0.827; 94% label agreement), and same-generation devices separate at 1024 shots (p ≤ 2.6 × 10−3) by an operationally minor 0.010. We also document how the greedy-gap hardness signal central to QSE collapses below N=16 (same-protocol RF R2 falls from 0.306 to 0.076; transitivity correlation from −0.564 to −0.351) — re-derivation on the original benchmark exposing a greedy-protocol difference that confounds naive cross-study comparisons — and two engineering failures — a ZZ-phase sign-convention bug caught by a cross-simulator parity check, and transpiler gatedirection faults in legacy Falcon noise models — whose diagnoses shaped the final pipeline.
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.
Hybrid quantum-classical optimization has made the Quantum Approximate Optimization Algorithm (QAOA) a leading candidate for combinatorial optimization tasks, and Max-Cut stands out among them for its broad practical footprint and its clean reduction to QUBO and Ising form. Prior divide-and-conquer adaptations push QAOA toward larger inputs, yet they stay capped at tens of thousands of vertices and never engage modern GPU cluster hardware, leaving million-scale instances out of reach. This work closes that gap with MillionQAOA, a GPU-accelerated divide-and-conquer framework capable of solving Max-Cut instances of up to one million vertices on multi-node H100 GPU clusters. The framework is organized as a four-phase, topology-aware pipeline: parallel graph synthesis, solver-shard formation, concurrent GPU-parallel circuit solving, and candidate consolidation through boundary binning paired with a layer-wise frontier expansion. On a testbed of 8 DGX-H100 nodes (64 GPUs in total), MillionQAOA scales near-linearly from 62.5K through 1M vertices, matches classical greedy solvers in cut quality at the 50K-vertex mark (within 0.2% higher), and cuts execution time by up to 13.6 ×, making it a deployable route to million-vertex Max-Cut at scale.
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.
Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum algorithm to approximately solve NP optimization problems such as MAX-CUT. We describe a new application area of QAOA circuits: graph structure discovery. We omit the time-consuming parameter-optimization phase and utilize the dependence of QAOA energy on the graph structure for randomly or judiciously chosen parameters to learn about graphs. In the first part, Following up on Wang et. al. and Brandao et. al. we give explicit formulas. We show that the layer-one QAOA energy for the MAX-CUT problem for three regular graphs carries exactly the information: {\em (# of vertices, # of triangles)}. We have calculated our explicit formulas differently from \cite{wang2018quantum}, by developing the notion of the UUU polynomial of a graph GGG. Many of our discoveries can be interpreted as computing U(G)U(G)U(G) under various restrictions. The most basic question when comparing the structure of two graphs is if they are isomorphic or not. We find that the QAOA energies separate all non-isomorphic three-regular graphs up to size 18, all strongly regular graphs up to size 26 and the Praust and the smallest Miyazaki examples. We observe that the QAOA energy values can be also used as a proxy to how much graphs differ. Unfortunately, we have also found a sequence of non-isomorphic pairs of graphs, for which the energy gap seems to shrink at an exponential rate as the size grows. Our negative findings however come with a surprise: if the QAOA energies do not measurably separate between two graphs, then both of their energy landscapes must be extremely flat (indistinguishable from constant), already when the number of QAOA layers is intermediately large. This holds due to a remarkable uncoupling phenomenon that we have only deduced from computer simulation.