Pictorial representation of the commutation on each index between two {a†a†aa} JW rectangles. All indices commute except possibly the eight indices with black bars—these indices anticommute when the black bar (X or Y) is vertically aligned with a blue rectangle Z. In this example, there are an even (4) number of anticommuting terms, so the two patterns commute.
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(N4) terms. This quartic scaling appears to be a significant obstacle to practical applications. However, we note that it empirically reduces to O(N3) when we partition 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, precomputable procedure for creating linearly sized commuting partitions by solving a round-robin scheduling problem via flow networks. In addition, we demonstrate how to construct the quantum circuits necessary for simultaneous measurement, and we discuss the statistical implication of simultaneous measurement. Our results are experimentally validated by a ground state estimation of deuteron with low shot budget on a 20-qubit IBM machine. doi 10.1109/TQE.2020.3035814
Gokhale, P; Angiuli, O.; Ding, Y.; Gui, K.; Tomesh T.; Suchara M.; Martonosi M.; Chong F.
