  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.
