Tight Bounds for Quantum State Certification with Incoherent
  Measurements
  We consider the problem of quantum state certification, where we are given
the description of a mixed state $\sigma \in \mathbb{C}^{d \times d}$, $n$
copies of a mixed state $\rho \in \mathbb{C}^{d \times d}$, and $\varepsilon >
0$, and we are asked to determine whether $\rho = \sigma$ or whether $\| \rho -
\sigma \|_1 > \varepsilon$. When $\sigma$ is the maximally mixed state
$\frac{1}{d} I_d$, this is known as mixedness testing. We focus on algorithms
which use incoherent measurements, i.e. which only measure one copy of $\rho$
at a time. Unlike those that use entangled, multi-copy measurements, these can
be implemented without persistent quantum memory and thus represent a large
class of protocols that can be run on current or near-term devices.
  For mixedness testing, there is a folklore algorithm which uses incoherent
measurements and only needs $O(d^{3/2} / \varepsilon^2)$ copies. The algorithm
is non-adaptive, that is, its measurements are fixed ahead of time, and is
known to be optimal for non-adaptive algorithms. However, when the algorithm
can make arbitrary incoherent measurements, the best known lower bound is only
$\Omega (d^{4/3} / \varepsilon^2)$ [Bubeck-Chen-Li '20], and it has been an
outstanding open problem to close this polynomial gap. In this work, 1) we
settle the copy complexity of mixedness testing with incoherent measurements
and show that $\Omega (d^{3/2} / \varepsilon^2)$ copies are necessary, and 2)
we show the instance-optimal bounds for state certification to general $\sigma$
first derived by [Chen-Li-O'Donnell '21] for non-adaptive measurements also
hold for arbitrary incoherent measurements.
  Qualitatively, our results say that adaptivity does not help at all for these
problems. Our results are based on new techniques that allow us to reduce the
problem to understanding certain matrix martingales, which we believe may be of
independent interest.
