Measurement reduction in variational quantum algorithms

Variational quantum algorithms are promising applications of noisy intermediate-scale quantum (NISQ) computers. These algorithms consist of a number of separate prepare-and-measure experiments that estimate terms in a Hamiltonian. The number of terms can become overwhelmingly large for problems at the scale of NISQ hardware that may soon be available. We use unitary partitioning (developed independently by Izmaylov et al. [J. Chem. Theory Comput. 16, 190 (2020)]) to define variational quantum eigensolver procedures in which additional unitary operations are appended to the ansatz preparation to reduce the number of terms. This approach may be scaled to use all coherent resources available after ansatz preparation. We also study the use of asymmetric qubitization to implement the additional coherent operations with lower circuit depth. Using this technique, we find a constant factor speedup for lattice and random Pauli Hamiltonians. For electronic structure Hamiltonians, we prove that linear term reduction with respect to the number of orbitals, which has been previously observed in numerical studies, is always achievable. For systems represented on 10–30 qubits, we find that there is a reduction in the number of terms by approximately an order of magnitude. Applied to the plane-wave dual-basis representation of fermionic Hamiltonians, however, unitary partitioning offers only a constant factor reduction. Finally, we show that noncontextual Hamiltonians may be reduced to effective commuting Hamiltonians using unitary partitioning.

Figure 1

Number of fully anticommuting sets for electronic structure Hamiltonians vs the number of terms in the full Pauli Hamiltonian using the greedy independent sets strategy. The number of fully anticommuting sets is at least an order of magnitude less than the number of terms. The Jordan-Wigner and Bravyi-Kitaev mappings perform almost equivalently.

Figure 2

Number of fully anticommuting sets for electronic structure Hamiltonians vs the number of spin orbitals using the Jordan-Wigner mapping. Left: Including all partitioning schemes. The “Majorana analytic” curve is the $\left(\genfrac{}{}{0pt}{}{N}{2}\right)(N-2)$ upper bound obtained from (t1) for generic Hamiltonians of Eq. (67). The “Majorana numeric” data points correspond to the partitions described in Sec. 4b without further optimization. This upper bound is loose due to sparsity in the molecular Hamiltonians vs the set of all possible terms. Right: Ratio of the number of terms to the number of anticommuting sets for systems with more than five spin orbitals. A roughly linear trend is observed, in agreement with the analytic scaling discussed in Sec. 4b.

Figure 3

Resource requirements for full and partial term reduction using the greedy algorithm for partitioning. Left: Average post-ansatz gates required for full term reduction. Whiskers denote one standard deviation in the length of the circuit required for each anticommuting partition in the Hamiltonian. The growth in circuit length is dramatically slower than the growth in the number of Hamiltonian terms but displays high variance between anticommuting sets. Right: Reduction in the number of required independent expectation values given restrictions on maximum individual circuit length. With highly restricted circuit lengths, term recombination is largely impossible. However, roughly 1000 additional gates at most are sufficient to perform near-maximal term reduction for the molecules considered here (up to 36 spin orbitals), which is in agreement with the figure to the left.

Figure 4

Partitioning of electronic structure terms. Finding an anticommuting partition of the quartic terms can be reduced to finding an anticommuting partition of quadratic terms with exclusively even (equiv. odd) indices. Each highlighted bin is such an anticommuting set. Excluding the red bin, each set shares one common index $2q$ for $3\le q\le N-1$. Although only three values of $N$ are depicted, the induction of this diagram is straightforward for arbitrary $N$. One thus obtains $N-3$ bins of size $q$ each and 1 “red bin” of size 3.