Reduce complexity of sample_measure

[yaelbh]

What is the expected behavior?

sample_measure returns s measurement results, where s denotes the number of shots. Current implementation take O(s * 2^n) run time. #819 improves it to O(sn + 2^n). As noted in #819 (comment), this can be further improved to O(s + 2^n) (#819 (comment) explains how to generate a counts histogram; once this histogram exists, generating samples corresponding to the histogram takes O(s^2)).

[yaelbh]

The O(s + 2^n) algorithm should be implemented at some point, because a sub-optimal code is just not nice. However the gain in performance compared to the O(sn + 2^n) algorithm (#819) is expected to be small, probably even negligible. Note that there is anyway an additional step of converting samples from integer format to register format, which takes another O(sn). I suggest at this point to benchmark and merge #819 and #831, and return to this issue later.

[yaelbh]

If generating samples from the histogram takes O(s^2) (I feel that it can be improved to O(s log(s)) and maybe more) then possibly #819 just has smaller complexity, at least in the case where we really need samples and not just counts.

[yaelbh]

Samples from histogram is just O(s), it's a random permutation.

[yaelbh]

Probably can close this issue, @hhorii will decide.

[yaelbh]

@merav-aharoni @hhorii I remember that there were discussions about the measure sampling being implemented twice - in the statevector and the MPS simulator. I think there's a plan to unify it some day. When the day comes, which algorithm will be chosen, the binary search (implemented in the MPS sample measure using probabilities, and could be copied as is to the statevector section) or the other one (which is the statevector's one, and can be copied as is to the MPS section)? And, until the day comes, maybe determine which algorithm is preferable, remove the slower one, and duplicate the code of the faster one?

[yaelbh]

@hhorii Please don't close this issue until the last point is resolved, thanks

[hhorii]

Sorry that we have been leaving this issue. Please submit a new issue if it is still necessary.