Abstract
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 p₁, …, p_T on [d] = {1, 2, …, d}, and one wishes to accept/reject the hypothesis that their average p_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 ≫ √d/ε² + 1/ε⁴, one can (whp) distinguish p_avg = q from d_TV(p_avg,q) > ε. This nearly matches the optimal result for the classical iid setting (namely, T ≫ √d/ε²). 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 ρ₁, …, ρ_T, one can distinguish ρ_avg = σ from D_tr(ρ_avg,σ) > ε provided T ≫ d/ε². (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.