Abstract
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 terms. Several recent papers observed that this scaling may be reducible to 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.