From circuits to hardware: benchmarking standard and qubit-efficient quantum optimization on real hardware

Abstract

Despite rapid progress in quantum optimization, the field lacks broad real-hardware benchmarks comparing multiple algorithmic families across diverse classically hard combinatorial problems under one protocol. We present a hardware-aware benchmark of gate-based quantum optimization across four NP-hard problems: the multi-dimensional knapsack problem (MDKP), maximum independent set (MIS), quadratic assignment problem (QAP), and market-share problem, spanning variational methods (VQE, CVaR-VQE), standard, multi-angle, and warm-start QAOA, and qubit-efficient encodings (Pauli correlation encoding (PCE), QRAO), executed on IBM Heron r1/r2 processors under 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, an independent-error gate-count fidelity proxy Fest, and hardware outcomes. An empirical operating point near Fest≈0.1 ( ∼770 two-qubit gates at the median Heron-r2 CZ error rate) marks the transition to noise-dominated execution in the MDKP and MIS regimes. Two limitations emerge. QAP couples dense one-hot encodings with an exponentially sparse feasible manifold (feasible fraction 10!/2100 at n=10); no tested hardware method returns a feasible assignment. The tested QAOA-family circuits become noise-dominated after compilation, and a matched uniform-random control shows most feasible low-fidelity outcomes lie within the random range, with one MIS warm-start result reported as a finite-sample exception. A compilation counterfactual (SWAP-aware, fractional-gate, Nighthawk-topology) reduces two-qubit counts but moves no circuit above Fest=10−3; conclusions therefore apply to the tested implementations, not QAOA in general. Qubit-efficient methods extend runnable instance sizes but gain only within the empirical fidelity budget33 Code available at: https://github.com/SMU-Quantum/quantum-optimization-benchmarks.. Code available at: https://github.com/SMU-Quantum/quantum-optimization-benchmarks.