Sampling complexity of quantum channel discrimination

Abstract In this paper, we study the problem of sampling complexity for channel discrimination with respect to two different strategies: product strategy and adaptive strategy. We first formally introduce the definitions of the sampling complexity of the channels under the framework of hypothesis testing , wherein the goal is to determine the minimum number of samples needed to reach a desired error probability. We then establish the lower and upper bounds on the sampling complexity of the symmetric, asymmetric, and error exponent hypothesis testing settings. We show that, by imposing product strategy on testing, the bounds are always characterized by the generalized channel divergence, while with adaptive strategy, the bounds are characterized by the amortized channel divergence. Finally, we analyze two concrete examples, and obtain that the adaptive strategy can not lead to an advantage to the problem of determining the sampling complexity for classical-quantum channels, which can bring advantages for generalized amplitude damping channels.