We consider the problem of quantum state certification, where one is given $n$ copies of an unknown $d$-dimensional quantum mixed state $\rho$ and one wants to test whether $\rho$ is equal to some known mixed state $\sigma$ or else is $\eps$-far from $\sigma$. The goal is to use notably fewer copies than the $\Omega(d^2)$ needed for full tomography on $\rho$ (i.e., density estimation).

We give two robust state certification algorithms: one with respect to fidelity using $n = O(d/\eps)$ copies and one with respect to trace distance using $n = O(d/\eps^2)$ copies. The latter algorithm also applies when $\sigma$ is unknown as well. These copy complexities are optimal up to constant factors.

Joint work with Ryan O'Donnell and John Wright.