⚛️ quantum physics

From Circuits to Hardware: Benchmarking Standard and Qubit-Efficient Quantum Optimization on Real Hardware

This paper presents a comprehensive real-hardware benchmark of various gate-based quantum optimization algorithms across four NP-hard problems on IBM Heron processors, revealing that current noise levels render most feasible outcomes indistinguishable from random chance and that while qubit-efficient methods extend runnable instance sizes, they remain constrained by a strict empirical fidelity budget.

Original authors: Monit Sharma, Hoong Chuin Lau

Published 2026-07-14

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Monit Sharma, Hoong Chuin Lau

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you're trying to solve a massive, tangled puzzle using a brand-new, super-fragile robot arm. You have a bunch of different strategies: some try to grab the whole puzzle at once, others try to shrink the puzzle down to fit in your pocket, and some try to rearrange the pieces before you even start. This paper is like a giant, real-world stress test of those robot arms on four very different types of puzzles, using actual quantum computers (the "robot arms") instead of just pretending on a computer screen.

Here's the scoop on what happened when they put these strategies to the test on real hardware.

The Big Picture: The "Pocket Puzzle" Trap

The main finding is a bit of a reality check. For a long time, people thought the best way to solve hard problems on quantum computers was to make the problem smaller so it fits on fewer "qubits" (the robot's fingers). The idea was: Fewer fingers = easier to solve.

But the paper suggests that this isn't always true. While shrinking the puzzle (using "qubit-efficient" methods) does let you fit bigger problems onto the machine, it doesn't guarantee you'll get a good answer. In fact, sometimes shrinking the puzzle makes the robot arm wiggle so much from noise that it drops the pieces entirely. The authors measured this on real IBM Heron processors and found that just because a method uses fewer qubits doesn't mean it works better. It's like trying to carry a heavy box in a tiny backpack; sure, the backpack is small, but if the box is too heavy for your back, you're still going to drop it.

The Four Puzzles: A Tale of Four Problems

The researchers tested four different types of "NP-hard" problems (which just means they are super hard for normal computers, too). Each one behaved differently:

The Multi-Dimensional Knapsack Problem (MDKP): Imagine a backpacking trip where you have to pack items that are heavy, take up space, and have to fit in specific compartments.
- What happened: This was the "happy medium." All the methods, from the big ones to the tiny compressed ones, actually managed to find some valid solutions. The compressed methods (PCE and QRAO) worked well here, proving that shrinking the problem can help, but only if the robot arm is steady enough.
The Maximum Independent Set (MIS): Imagine a party where you want to invite the most guests possible, but no two guests can be enemies (they can't sit next to each other).
- What happened: This was the "cliff." For small parties, the robots did great. But as the party got bigger, the robots suddenly stopped working. The paper shows a sharp "feasibility cliff" where, once the problem gets slightly too big, the noise on the real hardware makes it impossible to find any valid guest list. It's like trying to balance a house of cards in a hurricane; it works for a few cards, but then poof, everything collapses.
The Quadratic Assignment Problem (QAP): Imagine assigning 10 or 12 people to 10 or 12 desks, but the cost depends on how far apart they sit and who they talk to.
- What happened: This was the "total failure." The paper explicitly states that no tested method returned a single valid solution for this problem on real hardware. Why? Because the rules are so strict (like a specific permutation) that the valid answers are incredibly rare—only about 1 in $10^{23}$ to $10^{34}$ possible arrangements are correct. The noise on the computer drowned out the signal so completely that the robots were just guessing randomly. The authors argue this isn't just a "we need better computers" issue; the problem structure itself is too dense for current tech.
The Market Share Problem (MSP): Imagine trying to split a pizza so that everyone gets exactly the slice size they ordered.
- What happened: This was the "compression paradox." The compressed methods (PCE and QRAO) shrank the problem down to just 7–11 qubits (tiny!), while the normal methods needed up to 156. But here's the kicker: the tiny methods got terrible results. They couldn't match the targets. The normal, larger methods actually did better. This proves that making the problem smaller doesn't automatically make the answer better.

The "Noise" Factor: When the Robot Wobbles

The paper introduces a cool way to measure how much the computer is wobbling. They call it a "fidelity proxy" ( $F_{est}$ ). Think of it as a "signal-to-noise" meter.

If the meter is high (around 0.1 or 10%), the robot is steady enough to hear the instructions.
If the meter drops below 0.001 (0.1%), the robot is so wobbly that it's basically just spinning its wheels.

They found that for many of the "QAOA" style methods (a popular algorithm family), the robot was so wobbly that the results were indistinguishable from just picking a random answer. The paper ran a control test where they compared the robot's output to a uniform random guess. For most of the big, complex circuits, the robot did no better than a random guess. In fact, for one specific case, a "warm-start" method did slightly better than random, but that was a rare exception, not the rule.

What the Paper Rules Out

The authors are very careful to say what they didn't find:

They rule out the idea that "fewer qubits = better performance." The data shows that shrinking the circuit often introduces other problems (like deeper circuits after translation) that cancel out the benefits.
They rule out the idea that QAOA methods are currently ready for prime time on these hard problems. After the computer translates the instructions to its own language (transpilation), the circuits become so huge and noisy that they fail. Even if they tried to optimize the routing (how the robot moves its fingers), the circuits would still be too wobbly to work.
They rule out the idea that simulation results (pretending on a perfect computer) tell the whole story. The gap between the "perfect simulation" and the "real hardware" is huge. A method that looks great in a simulation often fails miserably on real hardware because of the extra steps needed to make it work.

How Sure Are They?

The authors are very sure about what they measured. They didn't just guess; they ran 247 different combinations of methods and problems on real IBM Heron processors (specifically the r1 and r2 versions). They logged every single step, from how the code was translated to the final result.

They measured the exact number of gates (steps) the robot had to take.
They measured the error rates of the specific chips they used.
They simulated some parts to get a baseline, but they are clear that the simulation results are just a reference, not the final answer.

They are not claiming that quantum computers are useless. They are saying that for these specific problems and these specific current machines, the "shrink it down" strategy has limits, and some problems (like QAP) are just too hard right now. They suggest that we need to look at the whole picture—the size of the problem, the noise, and how the code gets translated—rather than just counting qubits.

The Takeaway for a Curious Teen

Think of quantum optimization like trying to send a message across a noisy room.

The "Standard" way is to shout the whole message clearly. It's loud, but if the room is too big, the noise drowns it out.
The "Compressed" way is to whisper a coded message. It's quieter and fits in a smaller space, but if the code is too complex or the room is too noisy, nobody can decode it, and you just get gibberish.

This paper says: "Hey, whispering isn't always the answer! Sometimes, the noise in the room is so bad that even the best code gets lost. And for some really tricky puzzles (like the QAP), the room is just too noisy for any of our current robots to solve it."

The authors aren't saying "give up." They are saying, "Let's stop pretending that just because we made the puzzle smaller, we solved it. We need to look at the whole mess—the noise, the translation, and the actual result—to see what's really working."

Title: From Circuits to Hardware: Benchmarking Standard and Qubit-Efficient Quantum Optimization on Real Hardware

Authors: Monit Sharma and Hoong Chuin Lau
Publication: IOP Publishing (Journal of Quantum Science and Technology, forthcoming)

Problem Statement

Despite rapid progress in quantum optimization algorithms, the field lacks broad, real-hardware benchmarks that compare multiple algorithmic families across diverse, classically hard combinatorial problems under a unified protocol. Existing evaluations are often limited to single problem classes, single algorithm families, or simulator-based settings that fail to account for practical constraints such as compilation overhead, qubit connectivity, gate noise, and execution variability. Consequently, it remains difficult to assess how different strategies (standard variational methods vs. qubit-efficient encodings) compare when mapped to real devices, or to determine when qubit-efficient formulations offer genuine practical advantages beyond nominal width reduction.

Methodology

The authors present a hardware-aware benchmarking study executed on IBM Heron r1 and r2 processors (superconducting transmon devices) under resilience-level-2 mitigation. The study evaluates gate-based quantum optimization methods across four NP-hard combinatorial problem classes:

Multi-Dimensional Knapsack Problem (MDKP): Packing-type constraints.
Maximum Independent Set (MIS): Graph-based independence structure.
Quadratic Assignment Problem (QAP): Dense, strongly coupled quadratic assignment.
Market Share Problem (MSP): Application-driven balancing constraints.

Algorithmic Families Tested:

Variational Energy-Minimization: Variational Quantum Eigensolver (VQE) and Conditional Value-at-Risk VQE (CVaR-VQE).
QAOA-Style: Standard QAOA, Warm-Start QAOA (WS-QAOA), and Multi-Angle QAOA (MA-QAOA).
Qubit-Efficient Encodings: Pauli Correlation Encoding (PCE) and Quantum Random Access Optimization (QRAO).

Experimental Protocol:

Workflow: All problems were converted to Quadratic Unconstrained Binary Optimization (QUBO) form using quadratic penalties, then mapped to Ising Hamiltonians.
Execution: The study utilized a fixed-shot variational optimization protocol (COBYLA optimizer, 200 iterations, 1,000 shots per evaluation) on real hardware.
Metrics: The benchmark reports solution quality (optimality gap or target deviation), feasibility, algorithm-level circuit width, transpiled circuit depth, two-qubit gate counts ( $N_{2Q}$ ), compilation overhead, and execution robustness.
Fidelity Modeling: An independent-error gate-count fidelity proxy ( $F_{est} \approx (1 - \epsilon_{2Q})^{N_{2Q}}$ ) was derived from backend calibration data to distinguish signal-preserving from noise-dominated execution regimes.

Key Contributions

Unified Cross-Family Benchmark: The first unified benchmark evaluating variational, QAOA-style, and qubit-efficient methods across four structurally distinct NP-hard problems under a common experimental protocol.
Hardware-Aware Evaluation: A shift from idealized resource estimates to a protocol that treats compilation overhead, transpiled circuit characteristics, and execution robustness as primary benchmark dimensions.
Quantitative Noise Thresholds: The establishment of an empirically grounded fidelity threshold ( $F_{est} \approx 0.1$ , corresponding to $\sim770$ two-qubit gates on Heron-r2) marking the transition to noise-dominated execution.
Reproducible Baseline: A fully reproducible empirical baseline including software stacks, backend metadata, transpilation policies, and per-instance diagnostics, with all code and instances publicly available.

Key Results

MDKP (Balanced Regime): All method families returned feasible solutions. Qubit-efficient methods (PCE, QRAO) significantly reduced qubit requirements but did not uniformly outperform full-width methods in solution quality. CVaR-VQE showed strong performance on specific instances.
MIS (Feasibility Cliff): A sharp feasibility breakdown was observed as instance size increased. While small instances were solved with zero gap, larger instances (64+ qubits) saw a collapse in feasibility for most methods, with only Warm-Start QAOA remaining feasible on the largest tested graph.
QAP (Structural Barrier): No tested hardware method returned a feasible assignment for any QAP instance. The combination of dense interactions, strict one-hot constraints, and an exponentially sparse feasible manifold ( $10!/2^{100} \approx 10^{-23.54}$ ) rendered all tested pipelines infeasible on current hardware, even for the smallest instances.
MSP (Compression vs. Quality): Qubit-efficient encodings achieved dramatic width reduction (7–11 qubits vs. 48–156) but resulted in significantly worse recovered solution quality (large target deviations) compared to full-width methods.
Compilation Overhead: Transpilation increased two-qubit gate counts by factors of 4.5 to 6.2 across problem families. For QAOA-family circuits, transpiled two-qubit counts often exceeded 20,000, pushing $F_{est}$ below $10^{-30}$ .
Noise Dominance: A matched uniform-random control showed that for low-fidelity QAOA-family runs ( $F_{est} < 10^{-3}$ ), most feasible outcomes lay within the empirical random range, suggesting that the signal was dominated by noise.
Simulator-Hardware Gap: Simulator rankings did not uniformly transfer to hardware. In some MDKP cases, hardware runs achieved lower gaps than simulators (potentially due to finite-shot stochasticity), while in others, hardware performance degraded significantly.

Significance and Claims

The paper does not claim a practical quantum advantage over classical solvers. Instead, it establishes a systematic empirical baseline for assessing quantum optimization under realistic constraints.

Qubit Count is Insufficient: The study demonstrates that lower qubit count (via compression) does not consistently imply better final performance on hardware. Gains from width reduction are often offset by transpilation overhead, increased effective circuit depth, or degraded robustness.
Problem-Dependent Viability: Practical performance is highly dependent on the interaction between problem structure, encoding choice, and hardware constraints. A method competitive on one problem class (e.g., MDKP) may fail completely on another (e.g., QAP).
Compilation as a First-Class Metric: The identity of a quantum optimization method changes materially after transpilation. Benchmarks must report transpiled circuit characteristics (depth, $N_{2Q}$ ) rather than just algorithm-level width to provide a complete picture of deployability.
Fidelity Thresholds: The derived $F_{est}$ thresholds provide actionable guidance, indicating that current hardware is likely noise-dominated for deep QAOA circuits and dense assignment problems, limiting the regime where quantum methods can be reliably tested.

The authors conclude that near-term benchmarking should focus on characterizing trade-offs (width vs. quality, algorithmic design vs. compiled cost) rather than searching for a single "best" algorithm, and that claims of practical advantage must be supported by hardware-realized solution quality and execution diagnostics, not just simulator results or nominal qubit counts.