Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1204.0711 · Journal of Mathematical Physics

Quantum state discrimination bounds for finite sample size

Koenraad M. R. Audenaert, Milán Mosonyi, Frank Verstraete

Published Dec 1, 2012• 47 citations
arXivHTMLPDF

Abstract

In the problem of quantum state discrimination, one has to determine by measurements the state of a quantum system, based on the a priori side information that the true state is one of the two given and completely known states, ρ or σ. In general, it is not possible to decide the identity of the true state with certainty, and the optimal measurement strategy depends on whether the two possible errors (mistaking ρ for σ, or the other way around) are treated as of equal importance or not. Results on the quantum Chernoff and Hoeffding bounds and the quantum Stein's lemma show that, if several copies of the system are available then the optimal error probabilities decay exponentially in the number of copies, and the decay rate is given by a certain statistical distance between ρ and σ (the Chernoff distance, the Hoeffding distances, and the relative entropy, respectively). While these results provide a complete solution to the asymptotic problem, they are not completely satisfying from a practical point of view. Indeed, in realistic scenarios one has access only to finitely many copies of a system, and therefore it is desirable to have bounds on the error probabilities for finite sample size. In this paper we provide finite-size bounds on the so-called Stein errors, the Chernoff errors, the Hoeffding errors, and the mixed error probabilities related to the Chernoff and the Hoeffding errors.

DOI
10.1063/1.4768252

Related papers

Asymptotic Error Rates in Quantum Hypothesis Testing

K. M. R. Audenaert, M. Nussbaum, Arleta Szkoła +1 more

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.

arXiv:0708.4282•Communications in Mathematical Physics•Feb 7, 2008•288 citations

An asymptotic error bound for testing multiple quantum hypotheses

Michael Nussbaum, Arleta Szkoła

We consider the problem of detecting the true quantum state among r possible ones, based of measurements performed on n copies of a finite-dimensional quantum system. A special case is the problem of discriminating between r probability measures on a finite sample space, using n i.i.d. observations. In this classical setting, it is known that the averaged error probability decreases exponentially with exponent given by the worst case binary Chernoff bound between any possible pair of the r probability measures. Define analogously the multiple quantum Chernoff bound, considering all possible pairs of states. Recently, it has been shown that this asymptotic error bound is attainable in the case of r pure states, and that it is unimprovable in general. Here we extend the attainability result to a larger class of r-tuples of states which are possibly mixed, but pairwise linearly independent. We also construct a quantum detector which universally attains the multiple quantum Chernoff bound up to a factor 1/3.

arXiv:1112.1529•The Annals of Statistics•Dec 1, 2011•21 citations

Discrimination Power of a Quantum Detector

Christoph Hirche, Masahito Hayashi, E. Bagán +1 more

We investigate the ability of a quantum measurement device to discriminate two states or, generically, two hypotheses. In full generality, the measurement can be performed a number n of times, and arbitrary preprocessing of the states and postprocessing of the obtained data are allowed. There is an intrinsic error associated with the measurement device, which we aim to quantify, that limits its discrimination power. We minimize various error probabilities (averaged or constrained) over all pairs of n-partite input states. These probabilities, or their exponential rates of decrease in the case of large n, give measures of the discrimination power of the device. For the asymptotic rate of the averaged error probability, we obtain a Chernoff-type bound, dual to the standard Chernoff bound for which the state pair is fixed and the optimization is over all measurements. The key point in the derivation is that identical copies of input states become optimal in asymptotic settings. Optimal asymptotic rates are also obtained for constrained error probabilities, dual to Stein's lemma and Hoeffding's bound. We further show that adaptive protocols where the state preparer gets feedback from the measurer do not improve the asymptotic rates. These rates thus quantify the ultimate discrimination power of a measurement device.

arXiv:1610.07644•Physical Review Letters•Apr 17, 2017•5 citations

Asymptotically optimal discrimination between multiple pure quantum states

Michael Nussbaum, Arleta Szkoła

We consider the decision problem between a finite number of states of a finite quantum system, when an arbitrary large number of copies of the system is available for measurements. We provide an upper bound on the asymptotic exponential decay of the averaged probability of rejecting the true state. It represents a generalized quantum Chernoff distance of a finite set of states. As our main result we prove that the bound is sharp in the case of pure states.

•Jan 11, 2010•2 citations

Quantum hypothesis testing with group symmetry

Fumio Hiai, Milán Mosonyi, Masahito Hayashi

The asymptotic discrimination problem of two quantum states is studied in the setting where measurements are required to be invariant under some symmetry group of the system. We consider various asymptotic error exponents in connection with the problems of the Chernoff bound, the Hoeffding bound, and Stein’s lemma, and derive bounds on these quantities in terms of their corresponding statistical distance measures. A special emphasis is put on the comparison of the performances of group-invariant and unrestricted measurements.

arXiv:0904.0704•Journal of Mathematical Physics•Oct 1, 2009•24 citations

Discriminating States: The Quantum Chernoff Bound

K. M. R. Audenaert, John Calsamiglia, R. Muñoz-Tapia +4 more

We consider the problem of discriminating two different quantum states in the setting of asymptotically many copies, and determine the minimal probability of error. This leads to the identification of the quantum Chernoff bound, thereby solving a long-standing open problem. The bound reduces to the classical Chernoff bound when the quantum states under consideration commute. The quantum Chernoff bound is the natural symmetric distance measure between quantum states because of its clear operational meaning and because it does not seem to share some of the undesirable features of other distance measures.

arXiv:quant-ph/0610027•Physical Review Letters•Apr 17, 2007•561 citations
In the problem of quantum state discrimination, one has to determine by measurements the state of a quantum system, based on the a priori side information that the true state is one of the two given and completely known states, ρ or σ. In general, it is not possible to decide the identity of the true state with certainty, and the optimal measurement strategy depends on whether the two possible errors (mistaking ρ for σ, or the other way around) are treated as of equal importance or not. Results on the quantum Chernoff and Hoeffding bounds and the quantum Stein's lemma show that, if several copies of the system are available then the optimal error probabilities decay exponentially in the number of copies, and the decay rate is given by a certain statistical distance between ρ and σ (the Chernoff distance, the Hoeffding distances, and the relative entropy, respectively). While these results provide a complete solution to the asymptotic problem, they are not completely satisfying from a practical point of view. Indeed, in realistic scenarios one has access only to finitely many copies of a system, and therefore it is desirable to have bounds on the error probabilities for finite sample size. In this paper we provide finite-size bounds on the so-called Stein errors, the Chernoff errors, the Hoeffding errors, and the mixed error probabilities related to the Chernoff and the Hoeffding errors.
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.
We consider the problem of detecting the true quantum state among r possible ones, based of measurements performed on n copies of a finite-dimensional quantum system. A special case is the problem of discriminating between r probability measures on a finite sample space, using n i.i.d. observations. In this classical setting, it is known that the averaged error probability decreases exponentially with exponent given by the worst case binary Chernoff bound between any possible pair of the r probability measures. Define analogously the multiple quantum Chernoff bound, considering all possible pairs of states. Recently, it has been shown that this asymptotic error bound is attainable in the case of r pure states, and that it is unimprovable in general. Here we extend the attainability result to a larger class of r-tuples of states which are possibly mixed, but pairwise linearly independent. We also construct a quantum detector which universally attains the multiple quantum Chernoff bound up to a factor 1/3.
We investigate the ability of a quantum measurement device to discriminate two states or, generically, two hypotheses. In full generality, the measurement can be performed a number n of times, and arbitrary preprocessing of the states and postprocessing of the obtained data are allowed. There is an intrinsic error associated with the measurement device, which we aim to quantify, that limits its discrimination power. We minimize various error probabilities (averaged or constrained) over all pairs of n-partite input states. These probabilities, or their exponential rates of decrease in the case of large n, give measures of the discrimination power of the device. For the asymptotic rate of the averaged error probability, we obtain a Chernoff-type bound, dual to the standard Chernoff bound for which the state pair is fixed and the optimization is over all measurements. The key point in the derivation is that identical copies of input states become optimal in asymptotic settings. Optimal asymptotic rates are also obtained for constrained error probabilities, dual to Stein's lemma and Hoeffding's bound. We further show that adaptive protocols where the state preparer gets feedback from the measurer do not improve the asymptotic rates. These rates thus quantify the ultimate discrimination power of a measurement device.
The asymptotic discrimination problem of two quantum states is studied in the setting where measurements are required to be invariant under some symmetry group of the system. We consider various asymptotic error exponents in connection with the problems of the Chernoff bound, the Hoeffding bound, and Stein’s lemma, and derive bounds on these quantities in terms of their corresponding statistical distance measures. A special emphasis is put on the comparison of the performances of group-invariant and unrestricted measurements.
We consider the problem of discriminating two different quantum states in the setting of asymptotically many copies, and determine the minimal probability of error. This leads to the identification of the quantum Chernoff bound, thereby solving a long-standing open problem. The bound reduces to the classical Chernoff bound when the quantum states under consideration commute. The quantum Chernoff bound is the natural symmetric distance measure between quantum states because of its clear operational meaning and because it does not seem to share some of the undesirable features of other distance measures.