{"ID":2859483,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.06147","arxiv_id":"2510.06147","title":"Non-iid hypothesis testing: from classical to quantum","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_1, \\dots, p_T$ on $[d] = \\{1, 2, \\dots, d\\}$, and one wishes to accept/reject the hypothesis that their average $p_{\\mathrm{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}}{ε^2} + \\frac{1}{ε^4}$, one can (whp) distinguish $p_{\\mathrm{avg}} = q$ from $d_{\\mathrm{TV}}(p_{\\mathrm{avg}},q) \u003e ε$. This nearly matches the optimal result for the classical iid setting (namely, $T \\gg \\frac{\\sqrt{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 $ρ_{\\mathrm{avg}} = σ$ from $D_{\\mathrm{tr}}(ρ_{\\mathrm{avg}},σ) \u003e ε$ 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.","short_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_1, \\dots, p_T$ on $[d] = \\{1, 2, \\dots, d\\}$, and one wishes to acce...","url_abs":"https://arxiv.org/abs/2510.06147","url_pdf":"https://arxiv.org/pdf/2510.06147v1","authors":"[\"Giacomo De Palma\",\"Marco Fanizza\",\"Connor Mowry\",\"Ryan O'Donnell\"]","published":"2025-10-07T17:19:26Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}