Holevo's theorem

Holevo's theorem is an important limitative theorem in quantum computing, an interdisciplinary field of physics and computer science.

It is sometimes called Holevo's bound, since it establishes an upper bound to the amount of information that can be known about a quantum state (accessible information).

Suppose Alice wants to send a classical message to Bob by encoding it into a quantum state, and suppose she can prepare a state from some fixed set

be the classical register containing the choice of state made by Alice.

be the classical register containing Bob's measurement outcome.

is therefore a random variable whose probability distribution depends on Bob's choice of measurement.

Holevo's theorem bounds the amount of correlation between the classical registers

, regardless of Bob's measurement choice, in terms of the Holevo information.

This is useful in practice because the Holevo information does not depend on the measurement choice, and therefore its computation does not require performing an optimization over the possible measurements.

More precisely, define the accessible information between

as the (classical) mutual information between the two registers maximized over all possible choices of measurements on Bob's side:

is the (classical) mutual information of the joint probability distribution given by

There is currently no known formula to analytically solve the optimization in the definition of accessible information in the general case.

is the ensemble of states Alice is using to send information, and

Note that the Holevo information also equals the quantum mutual information of the classical-quantum state corresponding to the ensemble:

the quantum mutual information of the bipartite state

It follows that Holevo's theorem can be concisely summarized as a bound on the accessible information in terms of the quantum mutual information for classical-quantum states.

Consider the composite system that describes the entire communication process, which involves Alice's classical input

in this manner, the von Neumann entropy

, is described by Afterwards, Alice sends the quantum state to Bob.

, he receives a mixed state of the form

Bob measures this state with respect to the POVM elements

This measurement process can be described as a quantum instrument where

Then, the state of the entire system after the measurement process is Here

is a quantum channel, and the quantum mutual information is monotonic under completely positive trace-preserving maps,[1]

These two inequalities give On the left-hand side, the quantities of interest depend only on with joint probabilities

is the identity operator on the quantum system

Then, the right-hand side is which completes the proof.

In essence, the Holevo bound proves that given n qubits, although they can "carry" a larger amount of (classical) information (thanks to quantum superposition), the amount of classical information that can be retrieved, i.e. accessed, can be only up to n classical (non-quantum encoded) bits.

It was also established, both theoretically and experimentally, that there are computations where quantum bits carry more information through the process of the computation than is possible classically.