  Measuring the expectation value of Pauli operators on prepared quantum states
is a fundamental task in a multitude of quantum algorithms. Simultaneously
measuring sets of operators allows for fewer measurements and an overall
speedup of the measurement process. We investigate the task of partitioning a
random subset of Pauli operators into simultaneously-measurable parts. Using
heuristics from coloring random graphs, we give an upper bound for the expected
number of parts in our partition. We go on to conjecture that allowing
arbitrary Clifford operators before measurement, rather than single-qubit
operations, leads to a decrease in the number of parts which is linear with
respect to the lengths of the operators. We give evidence to confirm this
conjecture and comment on the importance of this result for a specific
near-term application: speeding up the measurement process of the variational
quantum eigensolver.
