Efficient Estimation of Pauli Observables by Derandomization

We consider the problem of jointly estimating expectation values of many Pauli observables, a crucial subroutine in variational quantum algorithms. Starting with randomized measurements, we propose an efficient derandomization procedure that iteratively replaces random single-qubit measurements by fixed Pauli measurements; the resulting deterministic measurement procedure is guaranteed to perform at least as well as the randomized one. In particular, for estimating any $L$ low-weight Pauli observables, a deterministic measurement on only of order $\log (L)$ copies of a quantum state suffices. In some cases, for example, when some of the Pauli observables have high weight, the derandomized procedure is substantially better than the randomized one. Specifically, numerical experiments highlight the advantages of our derandomized protocol over various previous methods for estimating the ground-state energies of small molecules.

Figure 1

Illustration of the derandomization algorithm (Algorithm lg1): We envision $M$ randomized $n$-qubit measurements as a two-dimensional array composed of $n\times M$ Pauli labels. Blue squares are place holders for random Pauli labels, while green squares denote deterministic assignments (either $X$, $Y$, or $Z$). Starting with a completely unspecified array (left), the algorithm iteratively checks how a concrete Pauli assignment (red square) affects the confidence bound [Eq. (3)] averaged over all remaining assignments. A simple update rule [Eq. (8)] replaces the initially random label with a deterministic assignment that keeps the remaining confidence bound expectation as small as possible (center). Once the entire grid is traversed, no randomness is left (right) and the algorithm outputs $M$ deterministic $n$-qubit Pauli measurements.

Figure 2

$\mathrm{Be}{\mathrm{H}}_2$ ground-state energy estimation error (in Hartree) under Bravyi-Kitaev encoding [30] for different measurement schemes: The error for derandomized shadow is the root-mean-squared error (RMSE) over ten independent runs. The error for the other methods shows the RMSE over infinitely many runs and can be evaluated efficiently using the variance of one experiment [14].