# Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States

### Abstract

Many applications of quantum simulation require to prepare and then characterize quantum states by performing an efficient partial tomography to estimate observables corresponding to k-body reduced density matrices (k-RDMs). For instance, variational algorithms for the quantum simulation of chemistry usually require that one measure the fermionic 2-RDM. While such marginals provide a tractable description of quantum states from which many important properties can be computed, their determination often requires a prohibitively large number of circuit repetitions. Here we describe a method by which all elements of k-RDMs acting on N qubits can be sampled with a number of circuits scaling as O(3^k log^{k-1} N), an exponential improvement in N over prior art. Next, we show that if one is able to implement a linear depth circuit on a linear array prior to measurement, then one can sample all elements of the fermionic 2-RDM using only O(N^2) circuits. We prove that this result is asymptotically optimal. Finally, we demonstrate that one can estimate the expectation value of any linear combination of fermionic 2-RDM elements using O(N^4 / w) circuits, each with only O(w) gates on a linear array where w < N is a free parameter. We expect these results will improve the viability of many proposals for near-term quantum simulation.