# An invitation to the sample complexity of quantum hypothesis testing

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 135 references that are in the map.
- First posted on arXiv 26 Mar 2024.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Quantum Differential Privacy: An Information Theory Perspective](https://mlsanity.com/paper/2202.10717/) (2022)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Optimal Provable Robustness of Quantum Classification via Quantum Hypothesis Testing](https://mlsanity.com/paper/2009.10064/) (2020)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [The Learnability of Unknown Quantum Measurements](https://mlsanity.com/paper/1501.00559/) (2015)
- [Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems](https://mlsanity.com/paper/2306.13054/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [Quantum algorithm for Petz recovery channels and pretty good measurements](https://mlsanity.com/paper/2006.16924/) (2020)

## Built on by (most cited first, 5 of 5)

- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [Quantum Doeblin Coefficients: Interpretations and Applications](https://mlsanity.com/paper/2503.22823/) (2025)
- [Query Complexity of Classical and Quantum Channel Discrimination](https://mlsanity.com/paper/2504.12989/) (2025)
- [Sample Complexity of Composite Quantum Hypothesis Testing](https://mlsanity.com/paper/2601.08588/) (2026)
- [Privacy-Utility Tradeoffs in Quantum Information Processing](https://mlsanity.com/paper/2602.10510/) (2026)

## Abstract (arXiv)

Quantum hypothesis testing (QHT) has been traditionally studied from the information-theoretic perspective, wherein one is interested in the optimal decay rate of error probabilities as a function of the number of samples of an unknown state. In this paper, we study the sample complexity of QHT, wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. By making use of the wealth of knowledge that already exists in the literature on QHT, we characterize the sample complexity of binary QHT in the symmetric and asymmetric settings, and we provide bounds on the sample complexity of multiple QHT. In more detail, we prove that the sample complexity of symmetric binary QHT depends logarithmically on the inverse error probability and inversely on the negative logarithm of the fidelity. As a counterpart of the quantum Stein's lemma, we also find that the sample complexity of asymmetric binary QHT depends logarithmically on the inverse type II error probability and inversely on the quantum relative entropy, provided that the type II error probability is sufficiently small. We then provide lower and upper bounds on the sample complexity of multiple QHT, with it remaining an intriguing open question to improve these bounds. The final part of our paper outlines and reviews how sample complexity of QHT is relevant to a broad swathe of research areas and can enhance understanding of many fundamental concepts, including quantum algorithms for simulation and search, quantum learning and classification, and foundations of quantum mechanics. As such, we view our paper as an invitation to researchers coming from different communities to study and contribute to the problem of sample complexity of QHT, and we outline a number of open directions for future research.