HAMMER: boosting fidelity of noisy Quantum circuits by exploiting Hamming behavior of erroneous outcomes

Today's noisy quantum computers return a histogram of measured bit-strings in which the correct answer is often buried under louder wrong ones, so you cannot tell which outcome is right — but this Georgia Tech work makes a striking empirical observation on real IBM and Google machines, that the wrong outcomes are not random but cluster in Hamming space just a few bit-flips away from the correct answer (because each error flips only a qubit or two), so the correct string sits at the center of a halo of near-neighbor errors; HAMMER is a calibration-free classical post-processing step that reweights the histogram to boost outcomes surrounded by such a supporting halo, recovering an average 1.37x better solution quality across 500-plus circuits and sharpening QAOA's optimization landscape without touching the quantum hardware.

The argument in one glance

Problem

A noisy quantum computer buries the right answer under louder wrong ones

You run a program on a real quantum computer thousands of times and get back a HISTOGRAM: each measured bit-string with how often it appeared. On a perfect machine the correct answer would tower over everything. But today's NISQ machines have roughly 1-to-2% error per two-qubit gate, so the histogram is smeared — correct and incorrect outcomes both appear, and often the noise is loud enough that a wrong outcome is the tallest bar. In one 10-qubit Bernstein-Vazirani circuit the correct answer showed up only 8% of the time while a wrong string dominated at 20%. Reading the tallest bar gives you the wrong answer, and you have no way to know.
What people did

Correct the measurement bias with a calibration matrix

The established defense is readout (measurement) error mitigation. Measure known basis states many times to learn how often a 0 is misread as a 1 and vice versa, assemble that into a noise matrix, and invert it to un-bias the output distribution. IBM's M3 and Bravyi et al. do exactly this. It is principled and widely used — it removes the systematic distortion introduced at the moment of measurement.
Why it fell short

Readout correction ignores the errors that actually scramble the answer

Measurement bias is only one source of noise, and often not the dominant one. The gate errors and decoherence that accumulate THROUGHOUT the circuit are what really scatter probability away from the correct answer, and a readout calibration matrix says nothing about them. Worse, the calibration itself costs machine time and drifts as the device recalibrates. So even after readout correction, the correct answer can still be a minority bar in a noisy histogram, and there was no calibration-free technique that used the STRUCTURE of the full distribution — the way the errors are arranged relative to each other — to pull the correct answer back out.
This paper's idea

Notice that errors cluster near the truth, and reweight the histogram to exploit it

HAMMER (Georgia Tech) starts from an empirical discovery on real IBM and Google hardware: erroneous outcomes are NOT random. Because each error flips only a qubit or two, a wrong outcome is usually just a few bit-flips — a small HAMMING distance — from the correct one. Measured across many circuits, the average distance from correct outcomes sits far below the n/2 you would expect from uniform-random errors. So the correct string sits at the CENTER of a halo of lower-probability near-neighbor errors. HAMMER is a calibration-free, unsupervised classical post-processing step: it scores each outcome by how much supporting mass sits in its small-Hamming-distance neighborhood, boosts the ones that look like the center of such a halo, and renormalizes. No hardware change, no calibration, stackable with everything — average 1.37x better solution quality across 500-plus circuits, and sharper QAOA optimization landscapes.

Why this problem is worth solving

Every useful result from a near-term quantum computer arrives as a histogram of measured bit-strings, and the whole game is deciding which bar is the real answer. The trouble is that noise does not just lower the correct bar — it moves probability onto neighboring strings, and it can pile enough onto one wrong string to make it the tallest. So the naive reading (take the mode) fails, and the field has spent enormous effort trying to un-smear the distribution. The overlooked question HAMMER asks is not how to remove the noise but how the noise is ARRANGED, and to see the arrangement you have to look at outcomes in the right coordinate system, namely

the space where each possible measurement outcome is a bit-string and the distance between two outcomes is the HAMMING DISTANCE — the number of bit positions in which they differ. The string 111111111 and 110011111 are at Hamming distance 2, because two qubits disagree. Viewing the histogram this way, rather than as an unordered list of labels, is what makes the structure of the errors visible: an error that flips one qubit moves you one step in Hamming space, an error that flips two moves you two steps, and so on. The correct answer and its most common error variants are therefore NEIGHBORS in this space, clustered together, even though as raw integer labels they look unrelated

. Once you look there, a pattern jumps out that a list of labels completely hides.

The pattern is that errors are physically LOCAL in Hamming space. A gate error, a decoherence event, or a measurement flip typically corrupts only one or two qubits at a time, so it nudges the outcome a short distance from the truth rather than teleporting it to a random string. You can make this precise with the

the average Hamming distance between the correct outcome and the erroneous outcomes, weighted by how often each error occurs. This single number is a sharp test of whether errors are structured. If errors were uniformly random over all n-bit strings, the expected distance would be n/2 — a wrong answer would differ from the correct one in about half its bits. HAMMER measures EHD on real IBM and Google circuits and finds it far BELOW n/2, growing only slowly with circuit size: the errors sit close to the correct answer, not scattered across the whole space. The gap between the measured EHD and the uniform-random n/2 is the exploitable structure — proof that the noise is benign in a specific, usable way

. This matters because it inverts the usual pessimism. The worst case assumed by uniform-random error is almost never what real hardware does; the typical case is far kinder, and the correct answer, though not the tallest bar, is reliably the one surrounded by the densest halo of near neighbors. HAMMER exists to turn that observation into a recovered answer, cheaply and after the fact, without changing a single thing about how the circuit ran.

What people did before, and where it broke

Readout (measurement) error mitigation (IBM M3, Bravyi et al.). Learn a calibration matrix of how basis states are misread and invert it to un-bias the distribution. Corrects only the MEASUREMENT step, not the gate and decoherence errors that accumulate through the circuit; and the calibration costs machine time and drifts. Real but partial, and not calibration-free.
Correlated-error and ensemble mitigation (VERITAS, ensemble-mapping). Exploit a known model of correlated errors, or average over multiple qubit mappings, to cancel structured noise. Powerful when the error model is known, but they REQUIRE that model or extra circuit runs; HAMMER assumes no error model and needs no additional executions.
Zero-noise extrapolation / probabilistic error cancellation. Run the circuit at several amplified noise levels and extrapolate to zero noise. Effective but expensive — many extra circuit executions — and orthogonal to what HAMMER does on a single existing histogram.
Just take the mode of the histogram. The trivial baseline: report the most frequent outcome. Fails exactly when noise is loud enough to make a wrong string the tallest bar (correct at 8%, wrong at 20% in the paper’s example) — which is the regime that matters.
The gap. No prior method used the SPATIAL STRUCTURE of the full noisy distribution — how the errors are arranged in Hamming space relative to each other — to recover the answer, with no calibration, no error model, no extra circuit runs, and full compatibility with all of the above. HAMMER fills exactly that gap, and stacks on top of them.

How HAMMER works

From a noisy histogram to a reweighted one, using only Hamming structure

Put the outcomes in Hamming space new

Take the raw measured histogram and treat each bit-string as a point whose distance to any other is the number of differing bits. This coordinate change is the whole enabling move: as unordered integer labels the outcomes look unrelated, but in Hamming space the correct answer and its common error-variants are near neighbors, because each physical error flips only a qubit or two.
↓ →
Confirm the structure is there (EHD) new

Measure the Expected Hamming Distance — the noise-weighted average distance of outcomes from the correct answer. Uniform-random errors would give n/2; real IBM and Google circuits give far less, and it grows only slowly with qubit count. That gap below n/2 is the exploitable signal that errors cluster near the truth.
↓ →
Build each outcome's Hamming spectrum new

For every outcome x, sweep outward by Hamming distance d and total the probability mass of all outcomes at exactly distance d — the Cumulative Hamming Strength CHS(x, d). This spectrum describes the halo around x: a true center has lots of mass close in (small d) from its error-children, while a random wrong string does not.
↓ →
Learn per-distance weights W[d] new

Average the spectra across all outcomes and invert them to get weights W[d] that up-weight the distances where high-probability outcomes concentrate and down-weight distances where only average low-probability mass spreads. Neighborhoods are restricted to d up to about n/2 so distant spurious outliers cannot game the score.
↓ →
Score the supporting halo, with a filter new

For each outcome x, compute a neighborhood score S(x) = sum over near distances of W[d] times CHS, but count ONLY neighbors with LOWER probability than x. The filter is the key: a genuine peak is surrounded by its lower-probability error-children (it corroborates them), whereas a spuriously-tall wrong outcome that is really a satellite of a bigger peak gets no credit.
↓ →
Reweight and renormalize new

The corrected likelihood is L(x) = Pr(x) times S(x): an outcome that is both reasonably frequent AND sits at the center of a supporting halo is boosted; a loud but unsupported wrong outcome is not. Normalize to get a new distribution of higher fidelity. Pure classical post-processing — no calibration, no error model, no extra circuit runs, and stackable with readout mitigation and compiler tricks.

Evaluated on experimental data from IBM (Paris, Manhattan) and Google Sycamore across 500-plus unique circuits, on Bernstein-Vazirani and QAOA workloads, measured by Probability of Successful Trial, Inference Strength, Cost Ratio, and Total Variational Distance. O(N-squared) in the number of unique outcomes; single-threaded Python took 56 seconds for 20K unique outcomes.

The idea

Look at the errors in the right coordinate system and their structure appears. As a plain list of measured integers, the outcomes of a noisy quantum circuit look like noise with no usable pattern — the correct answer is just one label among many, and a wrong label happens to be taller. HAMMER’s first move is a change of representation: view each outcome as a bit-string and measure distances by how many bits differ. In that Hamming space the picture transforms, because each physical error (a flipped qubit) is a single step, so the correct answer and its most common corruptions are literal neighbors. The Expected Hamming Distance, far below the uniform-random n/2, quantifies it. This is the match-the-representation-to-the- phenomenon discipline the site keeps rewarding: the pattern was always in the data, but only the right coordinates make it visible — the same reason viewing values near 1.0 or side-channel traces in the right basis suddenly reveals exploitable structure.

The correct answer is the one that its own errors vouch for. Because errors flip few qubits, the correct string sits at the center of a cloud of lower-probability near-neighbors — its error-children. A wrong string that is merely loud, by contrast, is usually a satellite hanging off some larger peak and lacks its own supporting halo. HAMMER turns this into a test: score each outcome by the probability mass of its LOWER-probability Hamming neighbors, so an outcome is boosted only when it is corroborated by the errors that would naturally scatter around the truth. It is a self-consistency argument — the true answer leaves a fingerprint in the shape of the noise around it — and the lower-probability filter is what stops a big wrong peak from stealing credit for mass that really belongs to a bigger neighbor. Distinguish signal from a loud impostor by the support structure around it, not by height alone.

Fix it afterward, on the cheap classical side, without touching the quantum run. Quantum machine time is the scarce, expensive resource; classical post-processing on a histogram is nearly free. HAMMER puts all of its work on the cheap side: it takes whatever noisy distribution the hardware already produced and reweights it, with no calibration circuits, no error model, and no additional executions. That makes it orthogonal to and stackable with everything else — readout mitigation, better compilation, zero-noise extrapolation — because it changes none of them; it only re-reads their output more intelligently. It is the off-critical-path, do-the-work-where-it-is-cheap move the site sees again and again: spend classical cycles you have in abundance to rescue the output of a quantum run you cannot afford to repeat.

One noisy Bernstein-Vazirani histogram, rescued

The wrong bar is taller, but the right bar has the halo

A 10-qubit Bernstein-Vazirani circuit from the paper. The correct hidden string is 111111111; numbers are from HAMMER's evaluation.

Step 1 of 5

Read the raw histogram and get it wrong

The circuit is run thousands of times. The correct answer 111111111 appears only 8% of the time, while a wrong outcome 110011111 dominates at 20%. Taking the tallest bar — the obvious thing — returns the wrong string. Nothing about the two heights tells you which is real; by height alone the noise has won.

Inference Strength (a signal-to-competitor ratio) starts at about 0.4 — the correct answer is losing
readout error mitigation alone would not fix this: the damage is from gate and decoherence errors, not measurement bias

Why it works

Each physical error flips only one or two qubits → so an erroneous outcome is a small Hamming distance from the correct one, not a random string → the correct answer and its common errors are neighbors, and the measured EHD sits far below the uniform-random n/2.
The correct answer is surrounded by a cloud of its own lower-probability error-children → scoring each outcome by the mass of its lower-probability near-neighbors rewards being the center of such a halo → the true answer is boosted even when it is not the tallest bar.
A merely-loud wrong outcome is usually a satellite of a bigger peak → the filter counts only neighbors LESS probable than x, so a satellite gets no support → height without corroboration is not rewarded, separating signal from loud impostor.
Quantum machine time is scarce but classical cycles are cheap → HAMMER does all its work as post-processing on the existing histogram, with no calibration, error model, or reruns → it is free relative to the quantum cost and stacks with every other mitigation.
Real NISQ noise is far more benign than the worst-case uniform-random assumption → exploiting the typical case (local errors) rather than provisioning for the worst case → recovers an average 1.37x better solution quality on hardware today.

What it costs

It fails when the noise is too high. The whole method rests on errors clustering near the truth; once error rates push past roughly 2-to-3%, outcomes disperse toward uniform, EHD climbs to n/2, and the halo vanishes. HAMMER is a NISQ-regime technique and offers nothing in the high-noise limit.
Structure degrades with circuit depth. Deeper circuits accumulate more flips per outcome, washing out the Hamming locality; Bernstein-Vazirani (whose depth scales super-linearly) loses the structure faster than shallow QAOA. The benefit tracks fidelity, not the algorithm in the abstract.
No theory, only observation. The authors are explicit that they cannot derive the Hamming behavior from first principles of quantum error models — they surmise reasons but establish none. It is an empirical regularity, which means it could break on hardware or circuits that behave differently.
Quadratic post-processing cost. The reconstruction is O(N-squared) in the number of unique outcomes; for 20K unique outcomes a single-threaded Python run took 56 seconds. Large output supports need care, though the quantum run still dominates wall-clock and the step is parallelizable.
Evaluation needs the known answer; multi-optimum cases need the optimal set. The algorithm itself is unsupervised, but scoring its quality (PST, EHD) uses the known correct outcome, and for problems with several optima (QAOA) the cost metric measures distance to the nearest optimum — so assessing it assumes the optima are known even though running it does not.

The evaluation

Experimental data from IBM (Paris, Manhattan) and Google Sycamore, more than 500 unique quantum circuits, on Bernstein-Vazirani and QAOA, measured by Probability of Successful Trial, Inference Strength, Cost Ratio, and Total Variational Distance, against the raw histogram and alongside readout error mitigation.

Three ways to read a noisy quantum histogram

Property	Take the raw histogram (mode)	Readout error mitigation	HAMMER
Error sources addressed
Needs calibration or an error model?
What signal it uses
Extra quantum runs?	No
Improvement (NISQ regime)

HAMMER is orthogonal to readout mitigation and can be stacked on top of it and on compiler optimizations. Its benefit tracks fidelity: large in the NISQ regime, vanishing once error rates exceed roughly 2-to-3% and outcomes disperse toward the uniform-random n/2.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

HAMMER lives entirely in the NISQ regime and its gains track fidelity, not the algorithm in the abstract: the method rests on errors clustering near the truth, so once error rates climb past roughly 2-to-3%, or circuits grow deep enough to accumulate many flips per outcome, the Hamming structure washes out toward the uniform-random n/2 and there is nothing left to exploit (Bernstein-Vazirani loses it faster than shallow QAOA). The Hamming behavior itself is an empirical observation the authors explicitly cannot derive from first principles — a regularity seen on today’s IBM and Google machines, not a theorem, so it could differ on other hardware. The reconstruction is O(N-squared) in unique outcomes (56 seconds for 20K in single-threaded Python), which is cheap against the quantum run but not free for very large supports. And while the algorithm is genuinely unsupervised, judging its quality uses the known correct answer, and its QAOA cost metric assumes the optimal set is known. None of this weakens the core contribution — that real quantum noise is structured, that the correct answer is the one its own errors corroborate in Hamming space, and that a calibration-free classical reweighting can turn that structure into a recovered answer, stacking on top of every existing mitigation.

Background

Exploit the structure in the noise, on the cheap classical side

HAMMER sits in the site’s quantum-computing cluster and rhymes with several ideas covered elsewhere on this site. Its founding move — that the errors are not random but structured, and that the structure is exploitable — is the same better-than-worst-case insight the quantum-error-decoding pages turn on: the uniform-random error assumption (Expected Hamming Distance = n/2) is a pessimistic worst case that real hardware almost never realizes, so the win comes from provisioning for the typical case (local, few-qubit flips) instead. Its enabling trick is a change of representation: viewing outcomes in Hamming space rather than as unordered labels makes an invisible pattern obvious, the same match-the-representation-to-the-phenomenon discipline the 8-bit-numerics page uses to put precision where the data is and the side-channel pages use to read a signal in the right basis. Its scoring rule is a self-consistency, corroboration-by- neighbors argument — the correct answer is trusted because its own error-children vouch for it, and a loud impostor is rejected for lacking that support — the same distinguish-signal-from- plausible-impostor logic the site’s adversarial-verification and consensus patterns rely on. And it is, at heart, an off-critical-path move: quantum machine time is the scarce resource, so HAMMER does all its work as free classical post-processing on a histogram already in hand, orthogonal to and stackable with readout mitigation and better compilation — the same do-the-work-where-it-is-cheap division of labor the worst-case-provisioning and datacenter-scheduling families use when they push expensive decisions off the hot path.

If you remember only three things

1. Noisy quantum computers return a histogram in which the correct answer is often not the tallest bar (correct at 8% versus a wrong outcome at 20% in one example), and readout error mitigation only corrects measurement bias, leaving the gate and decoherence errors that actually scramble the distribution untouched — so there was no calibration-free way to recover the answer from the full noisy output.
2. HAMMER's discovery, measured on real IBM and Google hardware, is that erroneous outcomes are not random but cluster in Hamming space just a few bit-flips from the correct answer (because each error flips only a qubit or two), so the measured Expected Hamming Distance sits far below the uniform-random n/2 and the correct string sits at the center of a halo of its own lower-probability error-children; HAMMER scores each outcome by the mass of its lower-probability near-neighbors and reweights the histogram to boost the corroborated ones, all as calibration-free, model-free, rerun-free classical post-processing.
3. The payoff on 500-plus circuits is a 1.38x average improvement in Probability of Successful Trial on Bernstein-Vazirani and 1.37x in QAOA cost ratio (up to 2.4x), plus sharper QAOA landscapes that extend useful optimization from two layers to three — with the honest limits that it is a NISQ-regime technique that vanishes above roughly 2-to-3% error, rests on an empirical (un-derived) regularity, and costs O(N-squared) post-processing. The durable lessons: real noise is structured, the true answer is the one its own errors vouch for, and the right representation plus cheap classical work can rescue an expensive quantum run.

Check yourself

Check your understanding

1. HAMMER views measured outcomes in Hamming space (distance = number of differing bits) rather than as a plain list of bit-strings. Predict why this change of representation is what makes the technique possible at all.
2. In the example, a wrong outcome (110011111) is louder at 20% than the correct one (111111111) at 8%, yet HAMMER correctly boosts the quieter string. Predict what signal lets it tell the true answer from a loud wrong one.
3. HAMMER does all its work as classical post-processing on the histogram the hardware already produced, with no calibration, no error model, and no extra circuit runs. Predict why this design choice matters beyond mere convenience.
4. HAMMER measures the Expected Hamming Distance of errors and finds it far below n/2 — the value expected if errors were uniformly random. Predict why that gap below n/2 is the foundation the whole method stands on, and what it implies about when HAMMER stops working.

Sources

arXiv:2208.09371 — HAMMER: boosting fidelity of noisy Quantum circuits by exploiting Hamming behavior of erroneous outcomes — ASPLOS 2022 (full text read via ar5iv).
ACM DL: HAMMER (ASPLOS 2022) — published version.