Fast Partitioning of Pauli Strings into Commuting Families for Optimal
  Expectation Value Measurements of Dense Operators
The Pauli strings appearing in the decomposition of an operator can be can be
grouped into commuting families, reducing the number of quantum circuits needed
to measure the expectation value of the operator. We detail an algorithm to
completely partition the full set of Pauli strings acting on any number of
qubits into the minimal number of sets of commuting families, and we provide
python code to perform the partitioning. The partitioning method scales
linearly with the size of the set of Pauli strings and it naturally provides a
fast method of diagonalizing the commuting families with quantum gates. We
provide a package that integrates the partitioning into Qiskit, and use this to
benchmark the algorithm with dense Hamiltonians, such as those that arise in
matrix quantum mechanics models, on IBM hardware. We demonstrate computational
speedups close to the theoretical limit of $(3/2)^m$ relative to qubit-wise
commuting groupings, for $m=2,\dotsc,6$ qubits.
Ben Reggio Nouman Butt Andrew Lytle Patrick Draper