Optimizing Quantum Measurements by Partitioning Multisets of Observables

Quantum tomography approaches typically consider a set of observables that we wish to measure, designing a measurement scheme that measures each of the observables and then repeats the measurements as many times as necessary. We show that instead of considering only the simple set of observables, one should consider a multiset of the observables taking into account the required repetitions, to minimize the number of measurements. This leads to a graph theoretic multicoloring problem. We show that the multiset method offers at most quadratic improvement but it is achievable. Furthermore, despite the NP-hard optimal coloring problem, the multiset approach with greedy coloring algorithms already offers asymptotically quadratic improvement in test cases.