Constrained quantum tomography of semi-algebraic sets with applications to low-rank matrix recovery

We analyze quantum state tomography in scenarios where measurements and states are both constrained. States are assumed to live in a semi-algebraic subset of state space, and measurements are supposed to be rank-one positive operator-valued measures, possibly with additional constraints. Specifically, we consider sets of von Neumann measurements and sets of local observables. We provide upper bounds on the minimal number of measurement settings or outcomes that are required for discriminating all states within the given set. The bounds exploit tools from real-algebraic geometry and lead to generic results that do not only show the existence of good measurements, but guarantee that almost all measurements with the same dimension characteristic perform equally well. In particular, we show that on an n-dimensional Hilbert space any two states of a semi-algebraic subset can be discriminated by k generic von Neumann measurements if k(n -1) is larger than twice the dimension of the subset. In case the subset is given by states of rank at most r, we show that k generic von Neumann measurements suffice to discriminate any two states provided that k(n -1) > 4r(n -r) -2. We obtain corresponding results for low-rank matrix recovery of hermitian matrices in the scenario where the linear measurement mapping is induced by tight frames.