Memory-efficient Measurement Error Mitigation

[rraymondhp]

We found that measurement-error mitigation that should be memory-efficient, like the TensoredFilter, is implemented with creating a vector whose length is exponential in the number of qubits. This causes the measurement-error mitigation cannot be used when the number of qubits is beyond 25 or more. And the quantum devices we have now already have 65 qubits and more.

What is the expected behavior?

Implement measurement-error mitigation method in memory-efficient manner. For example, the code here should be replaced when dealing with mid and large number of qubits:
https://github.com/Qiskit/qiskit-ignis/blob/master/qiskit/ignis/mitigation/measurement/filters.py#L315

An improvement in the memory efficiency of CTMP method may also needed to deal with more qubits, as the method only requires evaluating sum.
https://github.com/Qiskit/qiskit-ignis/blob/master/qiskit/ignis/mitigation/expval/ctmp_mitigator.py#L126

[rraymondhp]

After reading the code, we also found that using qiskit.result.result.Result instance also causes exponential memory blow up. So, the TensoredFilter method indeed is not scalable to more than 30 qubits in a modest PC.
https://github.com/Qiskit/qiskit-ignis/blob/master/qiskit/ignis/mitigation/measurement/filters.py#L327
https://github.com/Qiskit/qiskit-ignis/blob/master/qiskit/ignis/mitigation/measurement/filters.py#L205

[yaelbh]

I'd like to clarify something, which seems to be clear to the author, but maybe not to readers of this issue. The tensored filter can perhaps be made to be memory-efficient, but run time must be exponential. This is not a software thing, but conceptual. The tensored version allows to efficiently calculate Pr(should have measured x | measured y) for all x, y in {0,1}^n, since we assume that this is independent and breaks down to the product of Pr(should have measured x_i | measured y_i) for all i in {0,..., n_1}. However, the qubits of x are still dependent, namely, Pr(should have measured x) is not equal to the product of Pr(should have measured x_i). Therefore, it is required to calculate separately Pr(should have measured x) for each of the 2^n x-s.

That said, one could imagine an option to transmit Pr(should have measured x) as soon as it is computed, without storing it (such a transmission is indeed not supported by the Result class). This option, if existed, could be exploited also by the complete filter. But for the tensored filter, this would made the difference between efficient and inefficient memory.

Even with this imaginary transmission, at the user's side, we eventually end up with a result that may consist of an exponential number of non-zero counts. We can thing of something along the following lines: the original execution of the device used a fixed number of shots, denote it by s. Therefore the original result consisted of at most s, and not 2^n, non-zero counts. Mitigation allows fractional counts, which may increase the number of non-zero counts to beyond s, up to 2^n. We could, after calculating Pr(should have measured x), randomize a result, such that we return a result that consists of s (or, could be another predefined number s') non-zero counts, mimicking an execution with s (s') shots. This solution loses some information on the way, but makes the tensored filter absolutely memory-efficient (albeit still not in run time).

[rraymondhp]

Thanks for making it very clear! Your point is absolutely correct: we have to preserve the number of shots (which can be performed at most polynomial in the number of qubits) and utilize that preservation to make the error-mitigation scalable. The fractional counts of the result of the mitigation should be rounded so as to preserve the number of counts.

[rraymondhp]

Apparently the paper below already had the answer..

https://arxiv.org/abs/2101.08946