# Lower bounds on the number of measurements outcomes required for quantum state tomography

It seems that in order to reconstruct a quantum state, a large number of measurements is typically used.

1. Are there any known theoretical lower bounds on the number of measurements required to reconstruct a state?
2. Do we get different lower bounds if we consider pure states instead of mixed states?

You can give "information-theoretic" lower bounds by noting that the measurements can be seen as a linear map $$M$$ from quantum states to outcome probabilities $$y$$. For instance, if you have a POVM $$(E_i)_{i=1,\dots,N}$$, then the probability vector is $$y = \sum_i \mathrm{tr}(E_i \rho) e_i$$, where $$e_i$$ is the standard basis of $$\mathbb{R}^N$$.
Tomography is about finding an approximate solution to the equation $$y = Mx$$ where $$x$$ is a description of your state. Without further assumptions, this only works if $$M$$ has full rank, in particular your POVM has to have size $$N=\Omega(d^2)$$ when $$d$$ is your Hilbert space dimension.
However, if your state has low rank $$r$$, the problem can be solved more efficiently. For instance, this occurs when $$\rho$$ is a pure state (rank 1). In this case, a lower bound is $$N=\Omega(rd)$$ which can be achieved e.g. with ideas from compressed sensing and low-rank matrix recovery.
• @Haim The rank restricts the degrees of freedom. Pure states for instance, form a manifold of (real) dimension $2d-2$ in contrast to arbitrary states lying in a subspace of dimension $d^2-1$. Hence, to invert the measurement map for pure states, less measurement settings are needed. See e.g. arxiv.org/abs/1109.5478 for a concrete lower bound. – Markus Heinrich Jun 27 at 9:00