Non-iid hypothesis testing: from classical to quantum

We study hypothesis testing (aka state certification) in the 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 p1, dots, pT on [d] = 1, 2, dots, d, and one wishes to accept/reject the hypothesis that their average pavg equals a known hypothesis distribution q. Garg et al. showed that if one has just c = 2 samples from each pi, and provided T gg frac√dε2 + frac1ε4, one can (whp) distinguish pavg = q from dTV(pavg,q) > ε. This nearly matches the optimal result for the classical iid setting (namely, T gg frac√dε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 quantum states. Here we uncover an unexpected phenomenon: for any d-dimensional hypothesis state σ, and given just a single copy (c = 1) of each state ρ1, dots, ρT, one can distinguish ρavg = σ from Dtr(ρavg,σ) > ε provided T gg d/ε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. We also show that the analogous phenomenon happens for the non-iid extension of identity testing between unknown states. 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.