  Variational quantum eigensolver (VQE) is a promising algorithm suitable for
near-term quantum machines. VQE aims to approximate the lowest eigenvalue of an
exponentially sized matrix in polynomial time. It minimizes quantum resource
requirements both by co-processing with a classical processor and by
structuring computation into many subproblems. Each quantum subproblem involves
a separate state preparation terminated by the measurement of one Pauli string.
However, the number of such Pauli strings scales as $N^4$ for typical problems
of interest--a daunting growth rate that poses a serious limitation for
emerging applications such as quantum computational chemistry. We introduce a
systematic technique for minimizing requisite state preparations by exploiting
the simultaneous measurability of partitions of commuting Pauli strings. Our
work encompasses algorithms for efficiently approximating a
MIN-COMMUTING-PARTITION, as well as a synthesis tool for compiling simultaneous
measurement circuits. For representative problems, we achieve 8-30x reductions
in state preparations, with minimal overhead in measurement circuit cost. We
demonstrate experimental validation of our techniques by estimating the ground
state energy of deuteron on an IBM Q 20-qubit machine. We also investigate the
underlying statistics of simultaneous measurement and devise an adaptive
strategy for mitigating harmful covariance terms.
