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.

However, the number of measurement settings is not the only important quantity in tomography. Sample complexity (i.e. the number of copies of your state), robustness to measurement errors, post-processing time etc. are important aspects as well. Low rank assumptions can also be used to reduce the sample complexity.

There's a lot of literature on this ... with different flavors. You can have a look at the introduction and the references in

• Thank you for this answer. Can you elaborate on how to obtain the lower bound in the rank 1 case?
– Haim
Jun 25 '21 at 20:16
• @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. Jun 27 '21 at 9:00
• What's the meaning of "measurement settings", what's the difference from the "measuring numbers" ? Oct 2 '21 at 2:36
• @KarryMa With "measurement settings", one usually means the number of different outcomes of a measurement, i.e. the size of the POVM you use. OP asked for "number of measurements" and I think they actually meant "measurement settings". The actual number of measurements you have to perform is considerably larger since you have to collect statistics to estimate each outcome Born probability. Standard bounds on this number, e.g. based on Hoeffding's inequality, are often really high. For well-structured POVMs it is possible to derive considerably better bounds, though. Oct 4 '21 at 8:12