  For potential quantum advantage, Variational Quantum Algorithms (VQAs) need
high accuracy beyond the capability of today's NISQ devices, and thus will
benefit from error mitigation. In this work we are interested in mitigating
measurement errors which occur during qubit measurements after circuit
execution and tend to be the most error-prone operations, especially
detrimental to VQAs. Prior work, JigSaw, has shown that measuring only small
subsets of circuit qubits at a time and collecting results across all such
subset circuits can reduce measurement errors. Then, running the entire
(global) original circuit and extracting the qubit-qubit measurement
correlations can be used in conjunction with the subsets to construct a
high-fidelity output distribution of the original circuit. Unfortunately, the
execution cost of JigSaw scales polynomially in the number of qubits in the
circuit, and when compounded by the number of circuits and iterations in VQAs,
the resulting execution cost quickly turns insurmountable.
  To combat this, we propose VarSaw, which improves JigSaw in an
application-tailored manner, by identifying considerable redundancy in the
JigSaw approach for VQAs: spatial redundancy across subsets from different VQA
circuits and temporal redundancy across globals from different VQA iterations.
VarSaw then eliminates these forms of redundancy by commuting the subset
circuits and selectively executing the global circuits, reducing computational
cost (in terms of the number of circuits executed) over naive JigSaw for VQA by
25x on average and up to 1000x, for the same VQA accuracy. Further, it can
recover, on average, 45% of the infidelity from measurement errors in the noisy
VQA baseline. Finally, it improves fidelity by 55%, on average, over JigSaw for
a fixed computational budget. VarSaw can be accessed here:
https://github.com/siddharthdangwal/VarSaw.
