Publication Type

Journal Article

Version

acceptedVersion

Publication Date

1-2026

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 , and hardware outcomes. An empirical operating point near (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 at ); 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 ; 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 budget3.

Keywords

quantum optimization, benchmarking, variational quantum eigensolver, QAOA, qubit-efficient encoding, combinatorial optimization, NISQ

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

Quantum Science and Technology

Volume

11

Issue

4

Last Page

81

ISSN

2058-9565

Identifier

10.1088/2058-9565/ae94a4

Publisher

IOP Publishing

Additional URL

https://doi.org/10.1088/2058-9565/ae94a4

Download

Share

COinS