Curator's Take
This article delivers the first systematic, cross‑problem hardware benchmark of both standard and qubit‑efficient quantum optimizers—including the inaugural real‑device results for QRAO and a multi‑problem PCE study—providing a rare empirical map of where current gate‑based processors begin to be noise‑dominated (around Fₑₛₜ≈0.1, roughly 770 two‑qubit gates on IBM’s Heron). By exposing that even modestly sized knapsack and independent‑set instances hit this fidelity wall while dense encodings for the quadratic assignment problem fail to produce feasible solutions, it underscores the urgent need for tighter error mitigation, smarter encodings, or hardware with lower CZ error rates. The findings give developers a concrete performance baseline against which emerging algorithmic tricks (e.g., warm‑start QAOA) and next‑generation devices can be measured, highlighting both progress made and the practical gap that still separates today’s quantum optimizers from real‑world advantage.
— Mark Eatherly
Summary
Despite rapid progress in quantum optimization, broad real-hardware benchmarks comparing multiple algorithmic families across diverse combinatorial problems under a common protocol remain limited. We benchmark gate-based quantum optimization on four NP-hard problems: multi-dimensional knapsack (MDKP), maximum independent set (MIS), quadratic assignment (QAP), and market-share (MSP). We study VQE, CVaR-VQE, standard, multi-angle, and warm-start QAOA, together with qubit-efficient PCE and QRAO, on IBM Heron r1/r2 processors using resilience-level-2 mitigation. To our knowledge, this includes the first real-hardware QRAO results and the first multi-problem PCE hardware benchmark. Across 247 method-instance combinations, we report transpiled circuit size, hardware outcomes, and an independent-error gate-count fidelity proxy, $F_{\mathrm{est}}$. For MDKP and MIS, an empirical operating point near $F_{\mathrm{est}}\approx 0.1$, corresponding to about 770 two-qubit gates at the median Heron-r2 CZ error rate, marks the onset of noise-dominated execution. QAP exposes a separate bottleneck: dense one-hot encodings and an exponentially sparse feasible manifold, with feasible fraction $10!/2^{100}$ at $n=10$; no tested hardware method produces a feasible assignment. Compiled QAOA-family circuits are generally noise dominated, and a matched uniform-random control shows that most feasible low-fidelity outcomes fall within the random range, apart from one finite-sample MIS warm-start exception. A SWAP-aware, fractional-gate, Nighthawk-topology compilation counterfactual reduces two-qubit counts but leaves all circuits below $F_{\mathrm{est}}=10^{-3}$. These conclusions apply to the tested implementations rather than QAOA in general. Qubit-efficient methods extend runnable instance sizes, but only within the empirical fidelity budget.