  Near-term quantum computers contain noisy devices, which makes it difficult
to infer the correct answer even if a program is run for thousands of trials.
On current machines, qubit measurements tend to be the most error-prone
operations (with an average error-rate of 4%) and often limit the size of
quantum programs that can be run reliably on these systems. As quantum programs
create and manipulate correlated states, all the program qubits are measured in
each trial and thus, the severity of measurement errors increases with the
program size. The fidelity of quantum programs can be improved by reducing the
number of measurement operations.
  We present JigSaw, a framework that reduces the impact of measurement errors
by running a program in two modes. First, running the entire program and
measuring all the qubits for half of the trials to produce a global (albeit
noisy) histogram. Second, running additional copies of the program and
measuring only a subset of qubits in each copy, for the remaining trials, to
produce localized (higher fidelity) histograms over the measured qubits. JigSaw
then employs a Bayesian post-processing step, whereby the histograms produced
by the subset measurements are used to update the global histogram. Our
evaluations using three different IBM quantum computers with 27 and 65 qubits
show that JigSaw improves the success rate on average by 3.6x and up-to 8.4x.
Our analysis shows that the storage and time complexity of JigSaw scales
linearly with the number of qubits and trials, making JigSaw applicable to
programs with hundreds of qubits.
