When a Quantum Computer Finds Good Answers—but Misses the Best Ones

Why averages can mislead

A quantum optimization algorithm is useful only if its measurements produce strong candidate answers. Yet hardware benchmarks often compare a device with a simulation using an average cost. That average can improve even when the chance of sampling the single best answer has collapsed.

Sanim Yousuf Fahim and Mohammad Arif Hossain examine this problem with the quantum approximate optimization algorithm, or QAOA. Their circuits solve small binary optimization subproblems arising in a larger method called ADMM. They use a shallow, depth-two circuit whose four adjustable angles were trained on separate examples and then reused, rather than tuned anew on the processor.

The paper first derives a useful baseline. If noise simply mixes the ideal output with uniformly random bit strings, then every improvement over random sampling shrinks by the same fraction. In that special case, the mean score and the probability of the optimum should retain equal fractions of their ideal improvement. This is a prediction of a simplified noise model, not a universal law.

Testing the prediction on hardware

The researchers compared exact, noiseless QAOA output with device-matched simulations and measurements on IBM’s Heron processor, ibm_marrakesh. They studied five eight-bit problems and ten twelve-bit problems in a main random-instance family, plus ten twelve-bit planted problems with rugged cost landscapes. Each hardware circuit was measured 4,096 times. The processor executed the first binary step of the decomposition; this was not a full-scale optimization demonstration.

For the twelve-bit main family, the mean-score measure retained roughly 29–46% of its noiseless improvement over uniform guessing across hardware runs. But the floor-corrected probability of measuring the exact optimum retained only about 5–15%. Put another way, the optimum appeared a median of roughly 5.5–14 times among 4,096 measurements per instance. If the noise had behaved like the uniform-mixture model at the measured mean retention, the expected median would instead have been about 23–33 optimal measurements. The probability gap was lower than the mean-retention estimate on at least nine of ten problems in each run.

The team also grouped answers by how close their cost was to the optimum. Near-optimal sets were depleted about as strongly as the optimum, while the device best retained its ability to avoid answers worse than a random guess. Thus the average score mostly reflected avoiding poor answers, not preserving the best ones. The authors caution that their floor correction assumes noise moves probability toward a uniform distribution; on the planted problems without suppression, the counts showed a bias toward bit strings with fewer ones, which can distort that correction.

A device-matched noise simulation reproduced the direction of the mismatch but was too optimistic about the optimum: in the first submission, its estimated optimal-probability retention was 5.4–8 times higher than the hardware’s. Dynamical decoupling improved retention in some runs, while twirling reduced it; a second submission also showed that day-to-day drift was large enough that single runs of a setting cannot cleanly establish its effect.

What the results do—and do not—show

On the planted problems, noiseless QAOA found the optimum in 98% of 768-measurement blocks. On hardware without suppression it did so in 62%, about the range of local classical heuristics in this small experiment. The main-family hardware time-to-solution estimates were five to fourteen times their noiseless values. These are comparisons on small, selected problem sets, not evidence that quantum hardware generally loses to classical methods or that QAOA offers an advantage.

The study used one processor, depth-two circuits, ten problems per twelve-bit family, and one execution per suppression setting in each submission. The authors did not record gate-error and coherence measurements for the executions, so they could not identify the physical error processes responsible. Optimal counts were small, making their per-instance estimates noisy; the authors nevertheless found the mean-versus-optimum ordering consistently across the main-family runs. The work is a preprint, not a peer-reviewed result.

The practical lesson is narrower but important: a benchmark for an optimization sampler should report how often it finds the optimum and near-optimal sets, alongside averages, and give the shot counts behind those estimates. A good-looking mean is not, by itself, evidence that the useful answers survived.