  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 with 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 a 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.
