Fast Partitioning of Pauli Strings into Commuting Families for Expectation Value Measurements of Dense Operators

The cost of measuring quantum expectation values of an operator can be reduced by grouping the Pauli string ($SU(2)$ tensor product) decomposition of the operator into maximally commuting sets. We detail an algorithm, presented in [1], to partition the full set of $m$-qubit Pauli strings into the minimal number of commuting families, and benchmark the performance with dense Hamiltonians on IBM hardware. Here we also compare how our method scales compared to graph-theoretic techniques for the generally commuting case.
Comment: 7 pages, 7 figures, Proceedings of the 40th International Symposium on Lattice Field Theory (Lattice 2023), July 31st - August 4th, 2023, Fermi National Accelerator Laboratory