Readout (measurement) error mitigation

What it fills

• Recover a noiseless expectation value by post-processing

  Estimate what an observable would have measured on a noiseless device by running modified or repeated circuits on the noisy one and combining the results classically. No qubits are spent on redundancy; the whole price is paid in shots.

When it applies

Addresses readout error only — it does nothing about gate or decoherence error, and treating it as general-purpose mitigation is a category error. The approach Nation et al. displace forms the full assignment matrix and inverts it, which needs $2^n$ calibration circuits and a $2^n x 2^n$ inverse and can return unphysical negative probabilities; their method never forms it. The scalable method works in the subspace defined by the observed bitstrings, accommodates correlated as well as uncorrelated errors, and yields computable error bounds.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  the observed counts over the bitstrings the device actually returned

# The form Nation et al. displace, for contrast -- do not build this:
#     calibrate the full 2^n x 2^n assignment matrix A, then apply A^-1.
#     That needs 2^n calibration circuits and a 2^n x 2^n inverse, and it
#     can return unphysical negative probabilities.

# The scalable form never forms A:
restrict to the subspace spanned by the observed bitstrings
build only the entries of A that act within that subspace
solve  A_sub p_true = p_observed  iteratively, without forming an inverse

return p_true, with its computable error bound

# readout error only. This does nothing about gate or decoherence error, and
# treating it as general-purpose mitigation is a category error.
# correlated as well as uncorrelated errors are accommodated

Cost, as the source states it

Nation, Kang, Sundaresan and Gambetta report a matrix-free preconditioned iterative solver converging in $O(1)$ steps and using orders of magnitude less memory than direct factorization, mitigating in a few seconds at qubit numbers where the direct method is intractable.

Implementations

• CTMP and tensor-product readout mitigation on ibmq_johannesburg

  • Mitigating measurement errors in multi-qubit experiments

  Bravyi, Sheldon, Kandala, McKay and Gambetta, at IBM Quantum's T. J. Watson and Almaden research centers, correct readout errors by classical post-processing for the class of algorithms in which measurement outcomes are used only to compute mean values of observables; they name variational quantum eigensolvers, quantum machine learning and tomography of entangled states, and state that the techniques are not applicable to single-shot measurements. The premise is that readout errors introduced by imperfect qubit measurements are often the dominant factor limiting scalability of near-term devices. The preprint (arXiv:2006.14044, 2020) was published as Phys. Rev. A 103, 042605 (2021).

  Two classical noise models are calibrated and then inverted. The tensor product (TP) model makes $A$ a tensor product of $2 \times 2$ noise matrices and depends on $2n$ error rates describing single-qubit readout errors $0 \to 1$ and $1 \to 0$. The correlated model is built from a Continuous Time Markov Process (CTMP): the noise matrix has the form $A = e^{G}$, where $G$ is a sum of local operators generating single- and two-qubit readout errors such as $01 \to 10$ and $11 \to 00$, and it depends on $2n^{2}$ error rates. Calibration prepares standard basis states and measures each repeatedly; three complete input sets are defined, and all three were performed for $n \le 7$ - weight-1 calibration (all $n$-bit strings of Hamming weight $0, 1, n$), weight-2 calibration (Hamming weight $0, 1, 2$), and a Hadamard calibration in which, for the smallest $p$ with $n < 2^{p}$, the input set is $\mathcal{C} = \{x^{0}, \ldots, x^{2^{p}-1}\}$ with $x^{a} \in \{0,1\}^{n}$ defined by $x^{a}_{b} = \sum_{i=1}^{p} a_{i} b_{i} \pmod{2}$ for $b = 1, \ldots, n$, where $a_{1}, \ldots, a_{p}$ are the binary digits of $a$; each two-bit error is then probed on exactly $2^{p-2}$ input states and in general $|\mathcal{C}| \le 2n$. Rather than forming the inverse noise matrix explicitly, error mitigation cancels errors by sampling noise matrices from a quasi-probability distribution (Algorithm 1), which yields an unbiased estimator of the ideal mean value; the total overhead, in measurements and classical post-processing, scales as $e^{4\gamma}\,\mathrm{poly}(n)$ in the noise strength $\gamma$.

  All experiments were performed on $n$-qubit registers of the 20-qubit IBM Quantum device ibmq_johannesburg, with only the chosen $n$-qubit register calibrated, unused qubits initialized in $|0\rangle$ in each calibration round and their outcomes ignored; every experiment used $N_{\mathrm{cal}} = 8192$ calibration rounds. The benchmark states were $n$-qubit graph states $|G_{n}\rangle = \left(\prod_{j=1}^{n-1} CZ_{j,j+1}\right) H^{\otimes n}|0^{n}\rangle$ on a path graph, for $4 \le n \le 12$, run on $n$-qubit subsets of qubits 0 through 11, plus a 20-qubit entangled state generated by a random depth-4 Clifford circuit of two layers of nearest-neighbour CNOT gates and two layers of single-qubit Clifford operators. The mean value of each stabilizer was estimated by measuring $M = 8192$ copies of the graph state, fidelity was estimated by averaging the stabilizer mean value over $\approx 100$ random stabilizers, and the entire experiment (calibration and mean value measurements) was repeated 16 times to estimate error bars.

  Bravyi et al. release no code of their own; the introduction points at Qiskit as the then-existing open-source toolkit for calibrating $A$ and mitigating readout errors for either a tensor product or a general noise model, cited as prior art alongside the tensor-product model. The CTMP scheme was implemented separately in Qiskit Ignis (Python, Apache License 2.0) by Christopher J. Wood with George S. Barron - PR 500, 'Add expectation value measurement error mitigation', merged 2020-09-23, three months after the preprint, first shipped in Ignis 0.5.0 on 2020-10-15 - as the class `CTMPExpvalMeasMitigator` in `qiskit/ignis/mitigation/expval/ctmp_mitigator.py`, whose sampling routine `_ctmp_inverse` is documented in its own docstring as equivalent to Algorithm 1 in Bravyi et al.; the companion `fit_ctmp_meas_mitigator` in `ctmp_fitter.py` extracts the generator rates from calibration data, and the tensor-product model ships alongside it as `tensored_mitigator.py`. Qiskit Ignis has since been deprecated and its repository, https://github.com/qiskit-community/qiskit-ignis, is archived.

  On ibmq_johannesburg - typical mean error rates $(1.75 \pm 1.05) \times 10^{-2}$ for CX gates, $(4.35 \pm 1.70) \times 10^{-4}$ for single qubit gates and $(3.44 \pm 1.72) \times 10^{-2}$ for readout errors - the CTMP model tracked the full assignment matrix more closely than the tensor-product model. Over 16 independent experiments at each of $n = 4, 5, 6, 7$, with both models fitted from weight-2 calibration and given exactly the same calibration data set, CTMP achieved a 2X reduction in the total variation distance to the full $A$-matrix for $n = 6, 7$ qubits; across the graph-state fidelities for $4 \le n \le 12$ under weight-1 calibration, the TP model systematically over-estimates the fidelity while CTMP agrees much better with the full $A$-matrix method (the full $A$-matrix model was only used for $n \le 7$). In the chosen 12-qubit register, some pairs of qubits, such as (7, 8), experience correlated errors with a few-percent rate. The measured CTMP noise strength was consistent with a linear scaling $\gamma \approx 0.05n$, with $\gamma \le 0.7$ over the graph-state experiments - an error mitigation overhead of at most $e^{4 \cdot 0.7} \le 20$, a factor of 20 increase in the number of measurements - and $\gamma \approx 1.1$ in the $n = 20$ experiment. In the 20-qubit random-Clifford experiment, mean values $\langle \psi | S | \psi \rangle$ were measured for $\approx 500$ stabilizers of weight 1 to 20 under Hadamard-type calibration; there the correlated two-qubit error rates $01 \leftrightarrow 10$ and $00 \leftrightarrow 11$ are less than 1% for all pairs of qubits, so the TP and CTMP results differ less. Classical post-processing was cheap: computing the error-mitigated mean value of a 20-qubit stabilizer with $T = 10^{6}$ samples in Algorithm 1 takes about 2 seconds on a laptop computer, and extracting the CTMP error rates from the 20-qubit calibration data takes about 1 second.

• M3 (Matrix-free Measurement Mitigation)

  • Scalable mitigation of measurement errors on quantum computers

  Nation, Kang, Sundaresan and Gambetta at IBM Quantum attack the scaling wall in the full-space approach: current measurement mitigation techniques utilize the full $2^{N}$-dimensional probability space, and thus do not scale beyond a handful of qubits. Their stated goal is to reduce the dimensionality of the linear system $\vec{p}_{\mathrm{noisy}} = A\,\vec{p}_{\mathrm{ideal}}$ without the need for computing $A$ itself, while still accommodating both uncorrelated and correlated errors and allowing for computing accurate error bounds. They place Bravyi et al. among the quasi-probability approaches that mitigate expectation values rather than distributions, and cite it for the proof that such quasi-probabilities give an unbiased estimate of the expectation value of an operator with spectral radius one that is diagonal in the computational basis.

  $\tilde{A}$ is defined to be the assignment matrix over only those bit-strings observed in $\vec{p}_{\mathrm{noisy}}$, so in the worst case its dimension equals the number of times the input circuit is sampled - typically 8192 on IBM Quantum systems - rather than $2^{N}$. Individual elements are computed on demand from bit-string values, $A^{(T)}_{\mathrm{row},\mathrm{col}} = \prod_{k=0}^{N-1} P^{(k)}_{\mathrm{row}[N-1-k],\mathrm{col}[N-1-k]}$ (Eq. 4), out of single-qubit calibration matrices $S_{k}$; an equivalent expression, Eq. (B1), built from $4 \times 4$ local noise matrices $C_{kl}$ whose elements are obtained following Section V of Bravyi et al., handles pairwise-correlated errors at $O(N^{2})$ floating-point evaluations per element instead of $O(N)$. As a corollary of grabbing elements individually, only those within a given Hamming distance $d(\mathrm{row},\mathrm{col}) \le D$ need be kept, which varies the sparsity of $\tilde{A}$; and because only selected elements of $A$ are taken, the columns of $\tilde{A}$ must be renormalized so that they once again sum to one (Eq. 5). The reduced system is solved either by direct LU factorization of $\tilde{A}$ or, where explicitly forming $\tilde{A}$ is still prohibitive, by a Jacobi-preconditioned matrix-free Krylov method (GMRES or BiCGSTAB), which requires computing only the product $\tilde{A}\vec{p}_{\mathrm{noisy}}$ and not $\tilde{A}$ itself. The mitigation overhead is $\mathcal{M} = \|A^{-1}\|_{1}^{2}$, which gives an upper bound on the standard deviation of an observable, $\sigma_{O} \le \sqrt{\mathcal{M}/s}$ at $s$ samples; rather than construct $\tilde{A}^{-1}$, the iterative Hager-Higham algorithm estimates $\|\tilde{A}^{-1}\|_{1} = \sqrt{\mathcal{M}}$ using only linear systems of equations involving $\tilde{A}$ and $\tilde{A}^{T}$, an estimate that is a lower bound on $\sqrt{\mathcal{M}}$ though in practice often exact or nearly so.

  Three hardware runs, with calibration circuits constructed and executed through Qiskit. (i) A 12-qubit circuit with an exact distribution of 43 unique bit-strings and an expectation value of $\sim 0.446$, executed 100 times on the 27 qubit IBM Quantum Kolkata system, mapping the virtual circuit qubits to physical qubits [1, 4, 7, 10, 12, 13, 14, 11, 8, 5, 3, 2], while varying the number of samples per circuit; calibration used 8192 samples per circuit, and the calibration data and raw input samples were identical for M3 and for the Qiskit Ignis comparison. (ii) GHZ states out to 42 qubits on the 65 qubit IBM Quantum Brooklyn system, prepared starting with a Hadamard gate on qubit 11 and, after the first 6 qubits, increasing the GHZ state by 4 qubits per layer; all calibration data and GHZ circuit execution used 8192 shots per circuit, and the average assignment and CNOT error rates across the qubits used were 2.15% and 1.01% respectively. (iii) An 8 qubit GHZ circuit executed 100 times on IBM Quantum Kolkata, a Falcon 5.11 series system with 330 ns readout pulses, using qubits [8, 5, 3, 2, 1, 4, 7, 6] that span two multiplex readout groupings at 8192 samples per circuit, then re-run with the readout pulse amplitudes intentionally increased by approximately 2x from the optimized values to induce correlated readout errors.

  M3, which stands for Matrix-free Measurement Mitigation. The paper's reference for the artefact is the repository https://github.com/qiskit-partners/mthree, which now resolves to https://github.com/Qiskit/qiskit-addon-mthree, described there as 'Matrix-free Measurement Mitigation' and licensed Apache-2.0; it is distributed on PyPI as `mthree`, summarised as 'M3: Matrix-free measurement mitigation' under Apache 2.0. The paper states the method is implemented with NumPy, SciPy and Cython, and makes use of Qiskit for calibration circuit construction and execution; the repository's language breakdown is Python, Cython and C.

  All timing data was taken on a quad core Intel i3-10100 system with 32 Gb of memory with NumPy and SciPy compiled against OpenBlas. On the 27 qubit IBM Quantum Kolkata system, M3 used at most 371 bit-strings (9% of the full-dimensionality) yet closely matched the full-dimensional tensored $A^{(T)}$ results over the entire range of samples, and agreed remarkably well with Qiskit Ignis above the $> 1000$ executions typically employed in practice; the sub-space reduction cut run time from $\sim 3$ s per circuit for Qiskit Ignis to at most $\sim 7$ ms for M3. The uncertainty bound given by the computed mitigation overhead $\mathcal{M}$ closely matched the experimental values, and for a tolerance of $\le 10^{-5}$, $\tilde{A}^{(T)}$ was well-approximated by keeping only terms out to $D = 3$. On the 65 qubit IBM Quantum Brooklyn system, GHZ states were mitigated out to 42 qubits, and only M3 allows for mitigating errors beyond 14 qubits; the comparators were the Qiskit Ignis tensored method and a bounded least-squares method the authors had modified to start from $\vec{p}_{\mathrm{noisy}}$ rather than a random vector (a 3x or more improvement in runtime), and they failed by algorithmic breakdown and extreme run-times respectively. At 42 qubits M3 took at most 1.2 seconds, rising to 2.4 and 4.5 seconds for the direct and iterative solutions when the mitigation overhead was computed as well. The M3 iterative method uses $\sim 1$ MiB of storage, against a compressed sparse column representation of the full 42-qubit $A$-matrix truncated at $D = 3$ requiring a total of 580.5 PiB, $\sim 120$x larger than the 4.85 PiB of memory on the Fugaku supercomputer. In the deliberately degraded 8-qubit Kolkata readout, the correlated M3 method using Eq. (B1) well captures the correlated readout errors, as evident by agreement with the complete $A$-matrix, while the tensored mitigator strongly over-corrects.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Zero-noise extrapolation (ZNE)

  Deliberately amplify the device noise by a set of known factors, measure the observable at each, and extrapolate the resulting curve back to zero noise. The fit is Richardson's deferred approach to the limit, or another model.

• Probabilistic error cancellation (PEC)

  Write the inverse of the characterized noise channel as a quasi-probability distribution over implementable operations, sample circuits from it, and combine the results with signed weights. Unlike extrapolation it inverts the noise rather than fitting through it, so it is unbiased in principle.

• Check the symmetries the answer must have

  The physics fixes quantities the true state cannot change — particle number, spin. Measure them alongside the run and discard, or post-process away, the outcomes that violate them: an error that moves the state out of the sector announces itself, and one that keeps it inside does not.

In the Atlas

• Readout-mitigated VQE

  Calibrated assignment errors are inverted or regularized before Pauli expectations are assembled.

Sources

• Mitigating measurement errors in multi-qubit experiments↗Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. McKay, Jay M. Gambetta · 2020nobody has read this paper for what it reports
• Scalable mitigation of measurement errors on quantum computers↗Paul D. Nation, Hwajung Kang, Neereja Sundaresan, Jay M. Gambetta · 2021theory yes · simulation ? · hardware ?