Quantum Chernoff Bound

Discriminating States: The Quantum Chernoff Bound

K.M.R. Audenaert, et al.

PRL 98, 160501 (2007)

URL: http://link.aps.org/abstract/PRL/v98/e160501


As the title implies, this Letter demonstrates a quantum analogue of the classical Chernoff bound in information theory. Some of the mathematical formalisms in the paper were beyond me, but I did learn a few cool math tricks.

What is the Chernoff bound? Suppose you have a signal, and you know that the output comes from one of two sources. If you perform N measurements, what is the probability of attributing the data to the wrong source? In 1952, Chernoff showed that the probability of error decreases exponentially for a large number of measurements: P(N) -> exp(-kN). The largest possible k is known as the Chernoff bound (among other things, as the authors point out in footnote 2). It provides a concept of distance between probability distributions.

Until this Letter was published, there was apparently no quantum version of Chernoff's analysis. The authors analyze a two state system. They claim that the probability of error in determining the state also obeys P(N) -> exp(-kN). The quantum Chernoff bound is determined by minimizing the trace of the product of two density matrices. In the classical limit, the expression reduces to that of the classical Chernoff bound.

The one statement I could not verify was the one that follows Eq. (4). The authors say "the upper bound trivially follows" from a mathematical relation that is not at all obvious to me. Somehow, the authors are able to break the logarithm of the trace of a matrix product into a sum of two logarithms:

log [ Tr{ (A P^n)^s (B Q^n)^(1-s) } ] = log[ A^s B^(1-s) ] + n log[ Tr{ P^s Q^(1-s) } ]

This is stated without reference or justification. I don't see how the logarithm of a sum (the trace) can be rewritten as the sum of two logarithms. The authors are correct, however. If this relation is true, their expression for the Chernoff bound follows immediately.

The first paragraph of the "Proof" section contains two neat math tricks. One allows me to rewrite the power of a number (or positive definite matrix) as an integral, and the other allows me to rewrite the difference of two numbers as the integral of a single function. The second trick is similar to the Feynman trick we used in quantum field theory for combining denominators. It's interesting that it can be extended to matrices.

I didn't get much out of the rest of the paper. There are apparently a lot of subtle points and nice mathematical properties of the quantum Chernoff bound, but I lack the background to appreciate them.

The idea behind the Chernoff bound is interesting, and it seems relevant to a variety of fields. For instance, in cryptography, you might know a coded message uses one of two encryption schemes. Chernoff's theory says you only need to know the true value of a certain number of bits and perhaps something about the content of the message before you could distinguish between the two encryption schemes and focus your efforts.

Another area is in the analysis of experimental data. With a large data set, the probability of attributing your results to the wrong theory (distribution) becomes exponentially small. Of course, this assumes you know the distributions before you do the experiment.

In short, it's hard to make a wrong guess about the distribution if you have enough data.