Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States

Many applications of quantum simulation require to prepare and then characterize quantum states by efficiently estimating k-body reduced density matrices (k-RDMs), from which observables of interest are obtained. Naive estimation of such RDMs require repeated state preparation for each matrix element. However, commuting matrix elements may be measured simultaneously, allowing for a significant cost reduction.
In this work we design schemes for such parallelization with near-optimal complexity in the system size N. We describe a scheme to sample all elements of a qubit k-RDM using only O(3^k log^k-1(N)) unique measurements. We detail a scheme to sample all elements of the fermionic 2-RDM using only O(N²) unique measurements, with O(N)-depth measurement circuit. We prove a lower bound of O(N^k) on the number of unique measurements required to directly sample all elements of a fermionic k-RDM, making our fermionic 2-RDM scheme asymptotically optimal. We finally construct circuits to sample the expectation value of a linear combination of ω anti-commuting 2-body fermionic operators with O(ω) gates on a linear array.