Ryan O'Donnell

A fundamental task in quantum information science is \emph{state certification}: testing whether a lab-prepared $n$-qubit state is close to a given hypothesis state. In this work, we show that \emph{every} pure hypothesis state can be certified using only $O(n^2)$ single-qubit measurements applied to $O(n)$ copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024). Our algorithm also showcases the power of \emph{adaptive measurements}: within each copy of the lab state, previous measurement outcomes dictate how subsequent qubit measurements are made. We show that the adaptivity is necessary, by proving an exponential lower bound on the number of copies needed for any nonadaptive single-qubit measurement algorithm.

We study hypothesis testing (aka state certification) in the \emph{non-identically distributed} setting. A recent work (Garg et~al.~2023) considered the classical case, in which one is given (independent) samples from $T$ unknown probability distributions $p_1, \dots, p_T$ on $[d] = \{1, 2, \dots, d\}$, and one wishes to accept/reject the hypothesis that their average $p_{\textnormal{avg}}$ equals a known hypothesis distribution~$q$. Garg et al.~showed that if one has just $c = 2$ samples from each $p_i$, and provided $T \gg \frac{\sqrt{d}}{\eps^2} + \frac{1}{\eps^4}$, one can (whp) distinguish $p_{\textnormal{avg}} = q$ from $\dtv{p_{\textnormal{avg}}}{q} > \eps$. This nearly matches the optimal result for the classical iid setting (namely, $T \gg \frac{\sqrt{d}}{\eps^2}$). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical \emph{quantum} states. Here we uncover an unexpected phenomenon: for any $d$-dimensional hypothesis state~$\sigma$, and given just a \emph{single} copy ($c = 1$) of each state $\rho_1, \dots, \rho_T$, one can distinguish $\rho_{\textnormal{avg}} = \sigma$ from $\Dtr{\rho_{\textnormal{avg}}}{\sigma} > \eps$ provided $T \gg d/\eps^2$. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with $c = 1$ is provably impossible in the classical case. A technical tool we introduce may be of independent interest: an Efron--Stein inequality, and more generally an Efron--Stein decomposition, in the quantum setting.