  Variational Quantum Eigensolver (VQE) is a promising algorithm for near-term
quantum machines. It can be used to estimate the ground state energy of a
molecule by performing separate measurements of $O(N^4)$ terms. Several recent
papers observed that this scaling may be reducible to $O(N^3)$ by partitioning
the terms into linear-sized commuting families that can be measured
simultaneously. We confirm these empirical observations by studying the
MIN-COMMUTING-PARTITION problem at the level of the fermionic Hamiltonian and
its encoding into qubits. Moreover, we provide a fast, pre-computable procedure
for creating linearly-sized commuting partitions by solving a round-robin
scheduling problem via flow networks.
