VarSaw: Application-tailored Measurement Error Mitigation for Variational Quantum Algorithms

Siddharth Dangwal, Gokul Subramanian Ravi, Poulami Das, Kaitlin N. Smith, Jonathan Mark Baker and Frederic T. Chong

A known trick for cleaning up quantum measurement errors works beautifully on one circuit and becomes ruinous when a variational algorithm runs thousands of them — VarSaw finds the repetition the trick was blind to and deletes it.

The argument in one glance

Problem

Reading a qubit is the most error-prone thing you do to it

On current hardware a two-qubit gate fails about 1% of the time; a measurement fails about 4%. And measuring many qubits at once is worse than measuring them one at a time — on Google Sycamore, simultaneous measurements are 1.26 times more likely to go wrong. Every one of those failures corrupts the answer.
What people did

Measure fewer qubits at a time and stitch the answers together

JigSaw runs the same circuit many times, each run measuring only a small subset of qubits. Each subset result is accurate but says nothing about how qubits correlate. So JigSaw also runs the whole circuit once — noisy, but it captures correlations — and combines the two with Bayesian reconstruction into a distribution that is both accurate and correlated.
Why it fell short

One circuit is cheap; a variational algorithm is thousands of circuits, thousands of times

JigSaw multiplies the circuit count by roughly the number of qubits. A variational algorithm already runs one circuit per Pauli term in the Hamiltonian, and repeats the whole thing every tuning iteration. Compose the two and the per-iteration cost goes from roughly the fourth power of the qubit count to the fifth. For a molecule like chromium dimer, that means fifty thousand Pauli terms multiplied again by thirty-odd.
This paper's idea

Look at the whole application, and most of the work turns out to be duplicated

JigSaw is applied per circuit, so it cannot see that subsets generated for different Pauli terms overlap enormously. Do the subsetting at the Hamiltonian level instead, before the usual commutation-based merging, and most of them collapse together. Separately, the noisy full-circuit run does not need repeating every iteration — its correlations barely change, and re-running it only injects fresh measurement error.

Why this problem is worth solving

Variational algorithms are the most credible near-term use of quantum hardware, and they work by alternating: a quantum device evaluates a parameterised circuit called an

An ansatz is a quantum circuit whose gates carry adjustable parameters, chosen so that tuning those parameters can steer the machine through a useful range of quantum states.

, a classical optimiser adjusts the parameters, repeat until the measured energy stops falling. What is being measured is the energy of a

A Hamiltonian is a description of a physical system written as a sum of simple measurable pieces called Pauli terms, and its lowest eigenvalue is the ground-state energy the algorithm is searching for.

, and each of its terms has to be measured separately unless it can be merged with another. The flagship application is finding the ground-state energy of a molecule, which is exponentially hard classically and matters for predicting reaction rates and geometry. The catch is that the whole loop rests on measurements, and measurement is the least reliable operation these machines perform — roughly 4% error against 1% for a two-qubit gate.

The reasons are physical and stubborn. A measurement requires analogue and digital instruments coordinating across thermal domains from twenty millikelvin to room temperature, so it picks up thermal noise. Measuring several qubits at once introduces crosstalk between the readout apparatus. And measurement is slow — around 800 nanoseconds on Google hardware, four to five microseconds on IBM’s — during which the qubits keep decohering. Because a single failed measurement ruins the whole bitstring, the chance of reading out an entire register correctly falls off sharply with size, which is one of the things capping how large a program these devices can usefully run. That makes measurement error mitigation not a refinement but a precondition, and it explains why a technique that helps one circuit a lot can still be the wrong thing to run inside an algorithm that executes millions of them.

What people did before, and where it broke

Accept the noise and lean on the optimiser. Variational algorithms are supposed to be somewhat noise-robust because a classical optimiser sits in the loop. In practice the accuracy gap to what chemistry needs remains large, and measurement error is a big part of it.
Fix measurement error at the device level. Better readout electronics, shorter measurement times, less crosstalk. Real progress, but the paper is blunt that eradicating measurement error in hardware is not on the table.
Calibrate a correction matrix. Characterise how often each bitstring is misread and invert that. This scales badly with qubit count and assumes the error model is stable.
JigSaw: measure subsets, then reconstruct. Run the circuit repeatedly measuring only two qubits at a time, yielding local distributions that are accurate but uncorrelated; run the full circuit to get correlations that are noisy; combine with Bayesian reconstruction. It works — the paper reproduces its circuit-level benefit on four molecular instances.
The cost, though, is per circuit and multiplies. With a two-qubit sliding window over a Q-qubit circuit, JigSaw creates roughly Q-1 subset circuits for every circuit you wanted to run. Measured across molecules from 4 to 34 qubits, that is a 5.5x average increase in Pauli terms, and 12x for the 34-qubit chromium dimer.
Reduce circuits by commuting Pauli terms. Standard practice: Pauli strings whose observables commute can be measured by one circuit, so a 10-term Hamiltonian might need only 7 circuits. Every VQA framework does this. But it is applied to the Hamiltonian, and JigSaw is applied afterwards to each surviving circuit — so the two optimisations never meet.
The gap. JigSaw’s benefit is measured per circuit and its cost is paid per application. In a fixed budget, running JigSaw inside a variational algorithm can leave you with worse accuracy than doing no mitigation at all, because it burns the budget on circuits instead of on tuning iterations.

How VarSaw removes the duplicated work

Reordering two optimisations, and thinning out a third thing entirely

↓ →
↓ →
new
↓ →
new
↓ →
new
↓ →
new

Two of the three changes are pure reordering and reuse; only the third involves a trade-off.

The idea

The technique was right and the level was wrong. JigSaw operates on a circuit, which is the correct abstraction if you have one circuit. A variational algorithm has thousands, generated from one Hamiltonian, and they share enormous structure that is invisible from inside any single one of them. The paper’s framing is that this is a general lesson rather than a quirk: a state-of-the-art general-purpose optimisation, re-derived with knowledge of the application, can improve by orders of magnitude rather than percentages. The same argument — that a variational algorithm is a specific enough workload to justify rebuilding a general technique around it — is what motivates using classical simulation to bootstrap variational parameters instead of starting from a generic initialisation, covered elsewhere on this site.

Do the cheap optimisation second, not first. The spatial saving comes entirely from swapping the order of two steps that everyone already runs. Commuting Pauli strings can share a circuit, and a string with many identity positions commutes with many partners — the paper’s commutativity graph makes this vivid, where the all-identity string commutes with all 26 others while the all-Z string commutes with none. Subset strings are, by construction, almost all identity. So if you generate subsets first and merge second, you are merging exactly the population with the highest merge rate. Merging first and expanding second throws that away. On the paper’s worked four-qubit example, 10 Pauli terms become 7 after commutation, which JigSaw expands to 21 subset circuits, which VarSaw instead reduces to 9. Finding the exploitable redundancy by looking at the problem’s own structure rather than at the circuits it compiles into is the same move that lets a QAOA solver drop the graph’s highest-degree nodes to break a circuit into cheap independent pieces, covered elsewhere on this site.

Stale information from a quiet source beats fresh information from a noisy one. The temporal saving is the interesting one because it is a genuine trade. Re-running the full circuit every iteration gives correlation weights that faithfully track the current ansatz parameters and carry no accumulated reconstruction error. But that run is exactly the thing JigSaw exists to avoid — it measures every qubit at once, so it is drenched in measurement error. VarSaw’s hypothesis is that between neighbouring iterations the parameters barely move, so the staleness costs little, while the avoided measurement error saves a lot. The authors test it honestly by building the experiment that could refute it: in a noise-free simulation, maximum sparsity is clearly worse and gets stuck in a local minimum, exactly as the sceptical reading predicts. Under a realistic noise model it marginally wins. Trading freshness for a quieter signal, and letting the measured outcome decide how far to push it, is the same instinct behind treating a device’s noise profile as a dynamic quantity the algorithm should adapt to rather than a fixed property, covered elsewhere on this site.

Following one VQA iteration

What VarSaw actually executes on iteration three

A variational eigensolver tuning a molecular Hamiltonian, with the global sparsity currently set to run a full-circuit execution every two iterations.

Step 1 of 5

The optimiser hands over new parameters

The classical tuner proposes a fresh set of rotation angles for the ansatz, and the quantum side must now estimate the Hamiltonian energy under them.

Evaluating the energy means measuring the ansatz in the bases corresponding to each Pauli term. This is the per-iteration workload, and it is what gets multiplied by everything else.

Why it works

Subsets are identity-heavy, and identity-heavy strings merge. A two-qubit measurement subset leaves every other position as identity → identity positions impose no constraint on commutation, so such strings commute with almost everything → merging the subset pool collapses it to roughly 0.2x the baseline Pauli count, and the collapse gets better as molecules get larger.
The saving compounds with problem size. Pauli terms grow as the fourth power of qubit count while the reduced subset pool grows as roughly the first or second → the ratio between them widens → chromium dimer at 34 qubits needs only a 1% worst-case cost increase over the unmitigated baseline, against 12x for JigSaw.
Skipping globals removes error rather than merely saving time. Each global execution measures the entire register at once → that is precisely the high-crosstalk, high-error operation subsetting exists to avoid → so running fewer of them both saves circuits and injects less noise, which is why the temporal optimisation can improve accuracy and not only cost.
Cheaper iterations buy more iterations. A fixed circuit budget spent on fewer circuits per iteration → thousands of tuning steps instead of hundreds → the optimiser explores far more of the parameter space, which is why VarSaw beats JigSaw by 55% on average at equal budget despite using identical mitigation mathematics.
The sparsity is measured, not assumed. The hill-climb compares the stale-weight energy against the fresh-weight energy at every global → the algorithm discovers empirically how much staleness this device and this problem tolerate → so a machine with unusually clean readout would simply drive the sparsity back down rather than being silently mis-served.

What it costs (trade-offs and scope)

The temporal optimisation is useless without noise. The authors state this plainly and show it: in a noise-free simulation, maximum sparsity gets stuck in a local minimum and performs far worse than refreshing every iteration. The technique earns its keep only because measurement error is large today.
Stale weights are genuinely stale. The weights combining the subsets come from an older parameter setting, and Bayesian reconstruction error from that older result propagates forward. The bet is that this costs less than fresh measurement error, and the bet is workload-dependent.
The evaluation is mostly simulated, and the full technique only on small systems. Nine molecules are studied, but spatial-plus-temporal results are limited to systems of up to 8 qubits because simulating hundreds of VQA iterations is itself expensive. The larger molecules, including the 34-qubit case that produces the most striking cost numbers, show only the spatial benefit.
Real-device validation is small. The hardware runs on IBM Lagos and Jakarta use a 5-qubit transverse-field Ising Hamiltonian with just 3 Pauli terms — enough to demonstrate the temporal optimisation, far from a chemistry workload.
Only trivial qubit-wise commutation is used. More sophisticated commutation schemes exist and would reduce terms further, but they can inflate circuit depth and cost exponentially to construct. VarSaw’s benefits are expected to compose with them, not demonstrated to.
It inherits Bayesian reconstruction’s approximation error. The subset-plus-global reconstruction is statistical and imperfect. JigSaw’s own evaluation argues the mitigation outweighs it up to 18 qubits and this paper agrees, but it is an assumption carried forward rather than re-examined at scale.

The evaluation

Property	Metric	JigSaw applied to VQA	VarSaw
Circuits executed for the same accuracy	baseline
Worst-case per-iteration cost versus no mitigation
VQE inaccuracy recovered versus noisy baseline
Accuracy at equal circuit budget	a few hundred iterations
On real IBM hardware (Lagos, Jakarta)	full global execution every iteration

Simulation results use an IBMQ Mumbai noise model with the SU2 hardware-efficient ansatz and SPSA or ImFil optimisers; subset size is two qubits.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The headline 25x is a circuit-count reduction against JigSaw, and the most eye-catching number in the paper — 1000x — comes from the largest molecule, which is also the one where only the spatial half of the technique could be evaluated. The accuracy claims come from a different, smaller set of systems capped at 8 qubits, so no single benchmark demonstrates both halves at scale. Two caveats deserve equal billing with the wins. First, the temporal optimisation is explicitly not beneficial when measurement noise is small; the authors show the failure case rather than hiding it, but it means the technique is calibrated to present-day hardware and would need re-evaluating as readout improves. Second, the most interesting negative result in the paper is about JigSaw, not VarSaw: at a fixed circuit budget, applying JigSaw inside a variational algorithm produced worse accuracy than applying no mitigation at all, because the budget went into circuits instead of tuning steps. A technique can be a clear win at the circuit level and a net loss at the application level.

Background

Where this sits

This paper sits in the space between two lines of quantum systems work: error mitigation, which asks how to extract a better answer from a noisy device without full error correction, and variational algorithms, which are the most plausible near-term application of such devices. Most mitigation work is deliberately application-agnostic, and VarSaw’s argument is that this generality is precisely what makes it too expensive to use inside an algorithm that runs millions of circuits. The pattern generalises well beyond quantum computing — a technique validated on one unit of work, then deployed inside a loop that runs that unit relentlessly, often collapses on cost rather than on correctness. What makes this instance clean is that both fixes are structural rather than heuristic: one is a reordering of steps everyone already performs, the other a reuse decision with a measurable feedback signal. The broader family of NISQ-era techniques that reshape circuits, schedules and pulses to fit specific applications is covered elsewhere on this site.

If you remember only three things

1. Measurement is the noisiest operation on current quantum hardware, around 4% error versus 1% for a two-qubit gate, and measuring many qubits simultaneously is worse still.
2. JigSaw mitigates this well per circuit but multiplies circuit count by roughly the qubit count, which inside a variational algorithm pushes per-iteration cost from the fourth power of qubit count to the fifth — enough that at a fixed budget it can end up worse than no mitigation.
3. VarSaw removes the redundancy JigSaw could not see: generating measurement subsets before commutativity reduction rather than after collapses them by 25x on average, and reusing the noisy full-circuit correlations for around a hundred iterations both saves circuits and avoids injecting fresh measurement error.

Check yourself

Check your understanding

1. Why does JigSaw run both subset circuits and the full circuit?
2. Why does generating measurement subsets before commutativity reduction save so much more than doing it after?
3. What is the trade-off in executing the full circuit only occasionally?
4. What did the noise-free experiment show, and why did the authors include it?

Sources

The paper is “VarSaw: Application-tailored Measurement Error Mitigation for Variational Quantum Algorithms” by Siddharth Dangwal, Gokul Subramanian Ravi, Poulami Das, Kaitlin N. Smith, Jonathan Mark Baker and Frederic T. Chong, published at ASPLOS 2023 Volume 4, pages 362-377, DOI 10.1145/3623278.3624764.

This explainer is written from the full text, read via the arXiv version at arxiv.org/abs/2306.06027. All quantitative claims above come from the paper’s own sections 2, 3, 6 and 7: the 4% measurement error rate and 1.26x simultaneous-measurement penalty, the 5.5x average and 12x maximum JigSaw term expansion, the 0.2x average subset ratio and 20% worst-case per-iteration overhead, the 25x average and 1000x maximum circuit reduction, the 45% mean inaccuracy recovery over the noisy baseline, the 55% mean improvement over JigSaw at equal budget, the roughly one-in-a-hundred optimal global fraction, and the real-device results on IBM Lagos and Jakarta. The authors provide an implementation at github.com/siddharthdangwal/VarSaw. Readers should note that the cost results and the accuracy results are measured on different subsets of the nine molecules studied, since systems above 8 qubits could not be simulated for the hundreds of iterations the temporal optimisation requires.