An invitation to the sample complexity of quantum hypothesis testing
arXiv:2403.17868 · doi:10.1038/s41534-025-00980-8
Abstract
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.
v4: 63 pages, 3 figures, final version; v3: 58 pages, 1 figure, correction to Corollary 10; see independent and concurrent work of Pensia, Jog, Loh at arXiv:2403.16981
References in corpus (54)
- Quantum algorithm for solving linear systems of equations
- Quantum principal component analysis
- On the reality of the quantum state
- On quantum Renyi entropies: a new generalization and some properties
- The operational meaning of min- and max-entropy
- Toward the first quantum simulation with quantum speedup
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- The Quantum Chernoff Bound
- Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Renyi relative entropy
- Min- and Max- Relative Entropies and a New Entanglement Monotone
- Unconditional security proof of long-distance continuous-variable quantum key distribution with discrete modulation
- Quantum state discrimination and its applications
- A Fully Quantum Asymptotic Equipartition Property
- A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Monotonicity of a relative Rényi entropy
- The Chernoff lower bound for symmetric quantum hypothesis testing
- Error Exponent in Asymmetric Quantum Hypothesis Testing and Its Application to Classical-Quantum Channel coding
- Generalization in Quantum Machine Learning: a Quantum Information Perspective
- Second-order asymptotics for quantum hypothesis testing
- Converse bounds for private communication over quantum channels
- Dimension witnesses and quantum state discrimination
- alpha-z-relative Renyi entropies
- Maximally epistemic interpretations of the quantum state and contextuality
- Asymptotic quantum cloning is state estimation
- Strong converse exponent for classical-quantum channel coding
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Hamiltonian Simulation with Optimal Sample Complexity
- Quantum Coding with Finite Resources
- Quantum algorithm for Petz recovery channels and pretty good measurements
- Comparison of quantum statistical models: equivalent conditions for sufficiency
- Second-Order Asymptotics for the Classical Capacity of Image-Additive Quantum Channels
- On the Second-Order Asymptotics for Entanglement-Assisted Communication
- Discriminating quantum states: the multiple Chernoff distance
- Quantum simulation of partial differential equations via Schrodingerisation
- From Wigner-Yanase-Dyson conjecture to Carlen-Frank-Lieb conjecture (New title)
- Optimized quantum f-divergences and data processing
- Moderate deviation analysis for classical communication over quantum channels
- Optimal Provable Robustness of Quantum Classification via Quantum Hypothesis Testing
- Quantum Sphere-Packing Bounds with Polynomial Prefactors
- Upper bounds on the error probabilities and asymptotic error exponents in quantum multiple state discrimination
- Optimal state discrimination and unstructured search in nonlinear quantum mechanics
- Investigating Properties of a Family of Quantum Renyi Divergences
- Analog quantum simulation of partial differential equations
- How many copies are needed for state discrimination?
- Geodesic distances on density matrices
- Second-order asymptotics for quantum hypothesis testing in settings beyond i.i.d. - quantum lattice systems and more
- Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
- On the optimal error exponents for classical and quantum antidistinguishability
- Parallelization of Adaptive Quantum Channel Discrimination in the Non-Asymptotic Regime
- Pufferfish Privacy: An Information-Theoretic Study
- Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing
- Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
- A hierarchy of efficient bounds on quantum capacities exploiting symmetry