Min entropy

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The min entropy, in information theory, is the smallest of the Rényi family of entropies, corresponding to the most conservative way of measuring the unpredictability of a set of outcomes, as the negative logarithm of the probability of the most likely outcome. The various Rényi entropies are all equal for a uniform distribution, but measure the unpredictability of a nonuniform distribution in different ways. The min entropy is never greater than the ordinary or Shannon entropy (which measures the average unpredictability of the outcomes) and that in turn is never greater than the Hartley or max entropy, defined as the logarithm of the number of outcomes.

As with the classical Shannon entropy and its quantum generalization, the von Neumann entropy, one can define a conditional versions of min entropy. The conditional quantum min entropy is a one-shot, or conservative, analog of conditional quantum entropy.

To interpret a conditional information measure, suppose Alice and Bob were to share a bipartite quantum state . Alice has access to system A and Bob to system B. The conditional entropy measures the average uncertainty Bob has about Alice's state upon sampling from his own system. The min entropy can be interpreted as the distance of a state from a maximally entangled state.

This concept is useful in quantum cryptography, in the context of privacy amplification (See for example [1]).

Definitions[edit]

Definition: Let be a bipartite density operator on the space . The min-entropy of A conditioned on B is defined to be

where the infimum ranges over all density operators on the space . The measure is the maximum relative entropy defined as

The smooth min entropy is defined in terms of the min entropy.

where the sup and inf range over density operators which are -close to . This measure of -close is defined in terms of the purified distance

where is the fidelity measure.

These quantities can be seen as generalizations of the von Neumann entropy. Indeed, the von Neumann entropy can be expressed as

This is called the fully quantum asymptotic equipartition theorem.[2] The smoothed entropies share many interesting properties with the von Neumann entropy. For example, the smooth min entropy satisfy a data-processing inequality: [3]

Operational interpretation of smoothed min entropy[edit]

Henceforth, we shall drop the subscript from the min entropy when it is obvious from the context on what state it is evaluated.

Min-entropy as uncertainty about classical information[edit]

Suppose an agent had access to a quantum system B whose state depends on some classical variable X. Furthermore, suppose that each of its elements is distributed according to some distribution . This can be described by the following state over the system XB.

where form an orthonormal basis. We would like to know what the agent can learn about the classical variable . Let be the probability that the agent guesses X when using an optimal measurement strategy

where is the POVM that maximizes this expression. It can be shown that this optimum can be expressed in terms of the min-entropy as

If the state is a product state i.e. for some density operators and , then there is no correlation between the systems X and B. In this case, it turns out that

Min-entropy as distance from maximally entangled state[edit]

The maximally entangled state on a bipartite system is defined as

where and form an orthonormal basis for the spaces A and B respectively. For a bipartite quantum state , we define the maximum overlap with the maximally entangled state as

where the maximum is over all CPTP operations and is the dimension of subsystem . This is a measure of how correlated the state is. It can be shown that . If the information contained in A is classical, this reduces to the expression above for the guessing probability.

Proof of operational characterization of min-entropy[edit]

The proof is from a paper by König, Schaffner, Renner '08.[4] It involves the machinery of semidefinite programs,.[5] Suppose we are given some bipartite density operator . From the definition of the min-entropy, we have

This can be re-written as

subject to the conditions

We notice that the infimum is taken over compact sets and hence can be replaced by a minimum. This can then be expressed succinctly as a semidefinite program. Consider the primal problem

This primal problem can also be fully specified by the matrices where is the adjoint of the partial trace over A. The action of on operators on B can be written as

We can express the dual problem as a maximization over operators on the space AB as

Using the Choi Jamiolkowski isomorphism, we can define the channel such that

where the bell state is defined over the space AA'. This means that we can express the objective function of the dual problem as

as desired.

Notice that in the event that the system A is a partly classical state as above, then the quantity that we are after reduces to

We can interpret as a guessing strategy and this then reduces to the interpretation given above where an adversary wants to find the string given access to quantum information via system B.

See also[edit]

References[edit]

  1. ^ Vazirani, Umesh, and Thomas Vidick. "Fully device independent quantum key distribution." arXiv:1210.1810 (2012)
  2. ^ Marco Tomamichel, Roger Colbeck, Renato Renner. "The Fully Quantum Asymptotic Equipartition Property." Information Theory, IEEE Transactions on 55 (2009), p. 5840-5847
  3. ^ Renato Renner, "Security of Quantum Key Distribution", Ph.D. Thesis, Diss. ETH No. 16242 arXiv:quant-ph/0512258
  4. ^ König, R., Renato Renner, and Christian Schaffner. "The operational meaning of min-and max-entropy." Information Theory, IEEE Transactions on 55.9 (2009): 4337-4347. arXiv:0807.1338
  5. ^ John Watrous, Theory of quantum information, Fall 2011, course notes, https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/07.pdf