Sample complexity of quantum hypothesis testing
Hao-Chung Cheng Nilanjana Datta Nana Liu Theshani Nuradha Robert Salzmann Mark M. Wilde
Quantum hypothesis testing 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 quantum
hypothesis testing, 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 quantum hypothesis
testing, we characterize the sample complexity of binary quantum hypothesis
testing in the symmetric and asymmetric settings, and we provide bounds on the
sample complexity of multiple quantum hypothesis testing. In more detail, we
prove that the sample complexity of symmetric binary quantum hypothesis testing
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 quantum
hypothesis testing depends logarithmically on the inverse type~II error
probability and inversely on the quantum relative entropy. Finally, we provide
lower and upper bounds on the sample complexity of multiple quantum hypothesis
testing, with it remaining an intriguing open question to improve these bounds.