Tight Bounds for State Tomography with Incoherent Measurements
We consider the classic question of state tomography: given copies of an
unknown quantum state $\rho\in\mathbb{C}^{d\times d}$, output $\widehat{\rho}$
for which $\|\rho - \widehat{\rho}\|_{\mathsf{tr}} \le \varepsilon$. When one
is allowed to make coherent measurements entangled across all copies,
$\Theta(d^2/\varepsilon^2)$ copies are necessary and sufficient [Haah et al.
'17, O'Donnell-Wright '16]. Unfortunately, the protocols achieving this rate
incur large quantum memory overheads that preclude implementation on current or
near-term devices. On the other hand, the best known protocol using incoherent
(single-copy) measurements uses $O(d^3/\varepsilon^2)$ copies
[Kueng-Rauhut-Terstiege '17], and multiple papers have posed it as an open
question to understand whether or not this rate is tight. In this work, we
fully resolve this question, by showing that any protocol using incoherent
measurements, even if they are chosen adaptively, requires
$\Omega(d^3/\varepsilon^2)$ copies, matching the upper bound of
[Kueng-Rauhut-Terstiege '17].
  We do so by a new proof technique which directly bounds the "tilt" of the
posterior distribution after measurements, which yields a surprisingly short
proof of our lower bound, and which we believe may be of independent interest.