# Non-iid hypothesis testing: from classical to quantum

arXiv: https://arxiv.org/abs/2510.06147 · HTML: https://mlsanity.com/paper/2510.06147/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 65 references that are in the map.
- First posted on arXiv 7 Oct 2025.

## Builds on (most cited first, 17 of 17)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [A Hierarchy for Replica Quantum Advantage](https://mlsanity.com/paper/2111.05874/) (2021)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)
- [Toward Instance-Optimal State Certification With Incoherent Measurements](https://mlsanity.com/paper/2102.13098/) (2021)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)
- [Quantum chi-squared tomography and mutual information testing](https://mlsanity.com/paper/2305.18519/) (2023)
- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)
- [Few Single-Qubit Measurements Suffice to Certify Any Quantum State](https://mlsanity.com/paper/2506.11355/) (2025)
- [Testing identity of collections of quantum states: sample complexity analysis](https://mlsanity.com/paper/2103.14511/) (2021)
- [Testing with Non-identically Distributed Samples](https://mlsanity.com/paper/2311.11194/) (2023)
- [Instance-Optimal Quantum State Certification with Entangled Measurements](https://mlsanity.com/paper/2507.06010/) (2025)

## Abstract (arXiv)

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.