Hoeffding’s formulation and solution to the universal hypothesis testing (UHT) problem had a profound impact on many subsequent works dealing with asymmetric hypotheses. In this work, we introduce a quantum universal hypothesis testing framework that serves as a quantum analog to Hoeffding’s UHT. Motivated by Hoeffding’s approach, which estimates the empirical distribution and uses it to construct the test statistic, we employ quantum state tomography to reconstruct the unknown state prior to forming the test statistic. Leveraging the concentration properties of quantum state tomography, we establish the exponential consistency of the proposed test: the type II error probability decays exponentially quickly, with the exponent determined by the trace distance between the true state and the nominal state.
Quantum hypothesis testing (QHT) concerns the statistical inference of unknown quantum states. In the general setting of composite hypotheses, the goal of QHT is to determine whether an unknown quantum state belongs to one or another of two classes of states based on the measurement of a number of copies of the state. Prior art on QHT with composite hypotheses focused on a fixed-copy two-step protocol, with state estimation followed by an optimized joint measurement. However, this fixed-copy approach may be inefficient, using the same number of copies irrespective of the inherent difficulty of the testing task. To address these limitations, we introduce the quantum sequential universal test (QSUT), a novel framework for sequential QHT in the general case of composite hypotheses. QSUT builds on universal inference, and it alternates between adaptive local measurements aimed at exploring the hypothesis space and joint measurements optimized for maximal discrimination. QSUT is proven to rigorously control the type I error under minimal assumptions about the hypothesis structure. We present two practical instantiations of QSUT, one based on the Helstrom-Holevo test and one leveraging shallow variational quantum circuits. Empirical results across a range of composite QHT tasks demonstrate that QSUT consistently reduces copy complexity relative to state-of-the-art fixed-copy strategies.
We consider the problem of discriminating between two different states of a finite quantum system in the setting of large numbers of copies, and find a closed form expression for the asymptotic exponential rate at which the error probability tends to zero. This leads to the identification of the quantum generalisation of the classical Chernoff distance, which is the corresponding quantity in classical symmetric hypothesis testing. The proof relies on two new techniques introduced by the authors, which are also well suited to tackle the corresponding problem in asymmetric hypothesis testing, yielding the quantum generalisation of the classical Hoeffding bound. This has been done by Hayashi and Nagaoka for the special case where the states have full support. The goal of this paper is to present the proofs of these results in a unified way and in full generality, allowing hypothesis states with different supports. From the quantum Hoeffding bound, we then easily derive quantum Stein’s Lemma and quantum Sanov’s theorem. We give an in-depth treatment of the properties of the quantum Chernoff distance, and argue that it is a natural distance measure on the set of density operators, with a clear operational meaning.
An upper bound on simple quantum hypothesis testing in the asymmetric setting is shown using a useful inequality by Audenaert et al. [Phys. Rev. Lett. 98, 160501 (2007)] which was originally invented for symmetric setting. Using this upper bound, we obtain the Hoeffding bound, which is identical with the classical counterpart if the hypotheses, composed of two density operators, are mutually commutative. Its attainability has been a long-standing open problem. Further, using this bound, we obtain a better exponential upper bound of the average error probability of classical-quantum channel coding.
The ultimate limits of quantum state discrimination are often thought to be captured by asymptotic bounds that restrict the achievable error probabilities, notably the quantum Chernoff and Hoeffding bounds. Here we study hypothesis testing protocols that are permitted a probability of producing an inconclusive discrimination outcome, and investigate their performance when this probability is suitably constrained. We show that even by allowing an arbitrarily small probability of inconclusiveness, the limits imposed by the quantum Hoeffding and Chernoff bounds can be significantly exceeded. This completely circumvents the conventional trade-offs between error exponents in hypothesis testing while incurring only a vanishingly small overhead over conventional approaches. Such improvements over standard state discrimination are robust and can be obtained even when an exponentially vanishing probability of inconclusive outcomes is demanded. Relaxing the constraints on the inconclusive probability can enable even larger advantages, but this comes at a price. We show a 'strong converse' property of this setting: targeting error exponents beyond those achievable with vanishing inconclusiveness necessarily forces the probability of inconclusive outcomes to converge to one. By exactly quantifying the rate of this convergence, we give a complete characterisation of the trade-offs between error exponents and rates of conclusive outcome probabilities. Overall, our results provide a comprehensive asymptotic picture of how the allowance for inconclusive measurement outcomes reshapes optimal quantum hypothesis testing.
The task of binary quantum hypothesis testing is to determine the state of a quantum system via measurements on it, given the side information that it is in one of two possible states, say
ρ and
σ. This task is generally studied in either the symmetric setting, in which the two possible errors incurred in the task (the so-called type I and type II errors) are treated on an equal footing, or the asymmetric setting in which one minimizes the type II error probability under the constraint that the corresponding type I error probability is below a given threshold. Here we define a one-parameter family of binary quantum hypothesis testing tasks, which we call
s-hypothesis testing, and in which the relative significance of the two errors are weighted by a parameter
s. In particular,
s-hypothesis testing interpolates continuously between the regimes of symmetric and asymmetric hypothesis testing. Moreover, if arbitrarily many identical copies of the system are assumed to be available, then the minimal error probability of
s-hypothesis testing is shown to decay exponentially in the number of copies, with a decay rate given by a quantum divergence which we denote as
ξs(ρ∥σ), and which satisfies a host of interesting properties. Moreover, this one-parameter family of divergences interpolates continuously between the corresponding decay rates for symmetric hypothesis testing (the quantum Chernoff divergence) for
s=1, and asymmetric hypothesis testing (the Umegaki relative entropy) for
s=0.
The method of types is a fundamental tool in classical information theory, with applications ranging from composite hypothesis testing and universal source coding to the capacity of arbitrarily varying channels. In this work we introduce an empirical operator acting as a quantum analog of the empirical distribution. We show that this empirical operator satisfies combinatorial and large-deviation bounds, which in combination describe a quantum method of types. As an application, we use our method to prove a universal achievability result for composite quantum hypothesis testing.