Holevo's theorem

In physics, in the area of quantum information theory, Holevo's theorem (sometimes called Holevo's bound, since it establishes an upper bound) is an important limitative theorem in quantum computing which was published by Alexander Holevo in 1973. According to the theorem, the amount of information accessible given a quantum state $\rho$ is limited by its Holevo information

$\chi = S(\rho) -\sum_{i}^{} p(i) S(\rho_i)$,

where $S(\rho)=-\operatorname{tr}\rho\log_2\rho$ is the von Neumann entropy and the quantum state $\rho=\sum_{i} p(i)\rho_i$ is defined in terms of the encoded state $\rho_i$ with a prior distribution $p(i)$. When the state $\rho$ is interrogated using measurements described by a set of POVM elements $\{\Pi_0, \Pi_1, ..., \Pi_m\}$, then the mutual information $I(X;Y)$ between the encoded states (indexed by $X = 0, 1, 2, ...$) and the measurement outcomes (index by $Y = 0, 1, 2, ...$) is bounded from above by the Holevo quantity $\chi$ as:

$I(X;Y) \le \chi$

In essence, the Holevo bound proves that n qubits can represent only up to n classical (non-quantum encoded) bits. This is surprising, for two reasons: quantum computing is so often more powerful than classical computing, that results which show it to be only as good or inferior to conventional techniques are unusual, and because it takes $2^n-1$ complex numbers to encode the qubits which represent a mere n bits.

References

• Mathematical Sciences Research Institute Holevo's theorem and its implications for quantum communication and computation [1]
• Mark M. Wilde, "From Classical to Quantum Shannon Theory", arXiv:1106.1445v2 [quant-ph] - accessible on the ArXiv open repository. See in particular Section 11.6 and following. Holevo's theorem is presented as an exercise: exercise 11.9.1 on page 288.