  In this work, we study the problem of testing properties of the spectrum of a
mixed quantum state. Here one is given $n$ copies of a mixed state
$\rho\in\mathbb{C}^{d\times d}$ and the goal is to distinguish whether $\rho$'s
spectrum satisfies some property $\mathcal{P}$ or is at least $\epsilon$-far in
$\ell_1$-distance from satisfying $\mathcal{P}$. This problem was promoted in
the survey of Montanaro and de Wolf under the name of testing unitarily
invariant properties of mixed states. It is the natural quantum analogue of the
classical problem of testing symmetric properties of probability distributions.
  Here, the hope is for algorithms with subquadratic copy complexity in the
dimension $d$. This is because the "empirical Young diagram (EYD) algorithm"
can estimate the spectrum of a mixed state up to $\epsilon$-accuracy using only
$\widetilde{O}(d^2/\epsilon^2)$ copies. In this work, we show that given a
mixed state $\rho\in\mathbb{C}^{d\times d}$: (i) $\Theta(d/\epsilon^2)$ copies
are necessary and sufficient to test whether $\rho$ is the maximally mixed
state, i.e., has spectrum $(\frac1d, ..., \frac1d)$; (ii)
$\Theta(r^2/\epsilon)$ copies are necessary and sufficient to test with
one-sided error whether $\rho$ has rank $r$, i.e., has at most $r$ nonzero
eigenvalues; (iii) $\widetilde{\Theta}(r^2/\Delta)$ copies are necessary and
sufficient to distinguish whether $\rho$ is maximally mixed on an
$r$-dimensional or an $(r+\Delta)$-dimensional subspace; and (iv) The EYD
algorithm requires $\Omega(d^2/\epsilon^2)$ copies to estimate the spectrum of
$\rho$ up to $\epsilon$-accuracy, nearly matching the known upper bound. In
addition, we simplify part of the proof of the upper bound. Our techniques
involve the asymptotic representation theory of the symmetric group; in
particular Kerov's algebra of polynomial functions on Young diagrams.

Quantum Physics