Holevo's theorem

Last updated November 17, 2023

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). It was published by Alexander Holevo in 1973.

Accessible information

As for several concepts in quantum information theory, accessible information is best understood in terms of a 2-party communication. So we introduce two parties: Alice and Bob. Alice has a classical random variable X, which can take the values {1, 2, ..., n} with corresponding probabilities {p₁, p₂, ..., p_n}. Alice then prepares a quantum state, represented by the density matrix ρ_X chosen from a set {ρ₁, ρ₂, ..., ρ_n}, and gives this state to Bob. Bob's goal is to find the value of X, and in order to do that, he performs a measurement on the state ρ_X, obtaining a classical outcome, which we denote with Y. In this context, the amount of accessible information, that is, the amount of information that Bob can get about the variable X, is the maximum value of the mutual information I(X : Y) between the random variables X and Y over all the possible measurements that Bob can do.^[1]

There is currently no known formula to compute the accessible information. There are, however, several upper bounds, the best-known of which is the Holevo bound, which is specified in the following theorem.^[1]

Statement of the theorem

Let {ρ₁, ρ₂, ..., ρ_n} be a set of mixed states and let ρ_X be one of these states drawn according to the probability distribution P = {p₁, p₂, ..., p_n}.

Then, for any measurement described by POVM elements {E_Y} and performed on $\rho =\sum _{X}p_{X}\rho _{X}$ , the amount of accessible information about the variable X knowing the outcome Y of the measurement is bounded from above as follows:

I(X:Y)\leq S(\rho )-\sum _{i}p_{i}S(\rho _{i}),

where $\rho =\sum _{i}p_{i}\rho _{i}$ , and $S$ is the von Neumann entropy.

The quantity on the right-hand side of this inequality is called the Holevo information or Holevo χ quantity:

{\displaystyle \chi

Proof

Consider the composite system that describes the entire communication process, which involves Alice's classical input $X$ , the quantum system $Q$ , and Bob's classical output $Y$ . The classical input $X$ can be written as a classical register $\rho ^{X}:=\sum \nolimits _{x=1}^{n}p_{x}|x\rangle \langle x|$ with respect to some orthonormal basis $\{|x\rangle \}_{x=1}^{n}$ . By writing $X$ in this manner, the von Neumann entropy $S(X)$ of the state $\rho ^{X}$ corresponds to the Shannon entropy $H(X)$ of the probability distribution $\{p_{x}\}_{x=1}^{n}$ :

S(X)=-\operatorname {tr} \left(\rho ^{X}\log \rho ^{X}\right)=-\operatorname {tr} \left(\sum _{x=1}^{n}p_{x}\log p_{x}|x\rangle \langle x|\right)=-\sum _{x=1}^{n}p_{x}\log p_{x}=H(X).

The initial state of the system, where Alice prepares the state $\rho _{x}$ with probability $p_{x}$ , is described by

\rho ^{XQ}:=\sum _{x=1}^{n}p_{x}|x\rangle \langle x|\otimes \rho _{x}.

Afterwards, Alice sends the quantum state to Bob. As Bob only has access to the quantum system $Q$ but not the input $X$ , he receives a mixed state of the form ${\displaystyle \rho$ . Bob measures this state with respect to the POVM elements $\{E_{y}\}_{y=1}^{m}$ , and the probabilities $\{q_{y}\}_{y=1}^{m}$ of measuring the outcomes $y=1,2,\dots ,m$ form the classical output $Y$ . This measurement process can be described as a quantum instrument

{\mathcal {E}}^{Q}(\rho _{x})=\sum _{y=1}^{m}q_{y|x}\rho _{y|x}\otimes |y\rangle \langle y|,

where $q_{y|x}=\operatorname {tr} \left(E_{y}\rho _{x}\right)$ is the probability of outcome $y$ given the state $\rho _{x}$ , while $\rho _{y|x}=W{\sqrt {E_{y}}}\rho _{x}{\sqrt {E_{y}}}W^{\dagger }/q_{y|x}$ for some unitary $W$ is the normalised post-measurement state. Then, the state of the entire system after the measurement process is

\rho ^{XQ'Y}:=\left[{\mathcal {I}}^{X}\otimes {\mathcal {E}}^{Q}\right]\!\left(\rho ^{XQ}\right)=\sum _{x=1}^{n}\sum _{y=1}^{m}p_{x}q_{y|x}|x\rangle \langle x|\otimes \rho _{y|x}\otimes |y\rangle \langle y|.

Here ${\mathcal {I}}^{X}$ is the identity channel on the system $X$ . Since ${\mathcal {E}}^{Q}$ is a quantum channel, and the quantum mutual information is monotonic under completely positive trace-preserving maps,^[2] $S(X:Q'Y)\leq S(X:Q)$ . Additionally, as the partial trace over $Q'$ is also completely positive and trace-preserving, $S(X:Y)\leq S(X:Q'Y)$ . These two inequalities give

S(X:Y)\leq S(X:Q).

On the left-hand side, the quantities of interest depend only on

\rho ^{XY}:=\operatorname {tr} _{Q'}\left(\rho ^{XQ'Y}\right)=\sum _{x=1}^{n}\sum _{y=1}^{m}p_{x}q_{y|x}|x\rangle \langle x|\otimes |y\rangle \langle y|=\sum _{x=1}^{n}\sum _{y=1}^{m}p_{x,y}|x,y\rangle \langle x,y|,

with joint probabilities $p_{x,y}=p_{x}q_{y|x}$ . Clearly, $\rho ^{XY}$ and $\rho ^{Y}:=\operatorname {tr} _{X}(\rho ^{XY})$ , which are in the same form as $\rho ^{X}$ , describe classical registers. Hence,

S(X:Y)=S(X)+S(Y)-S(XY)=H(X)+H(Y)-H(XY)=I(X:Y).

Meanwhile, $S(X:Q)$ depends on the term

\log \rho ^{XQ}=\log \left(\sum _{x=1}^{n}p_{x}|x\rangle \langle x|\otimes \rho _{x}\right)=\sum _{x=1}^{n}|x\rangle \langle x|\otimes \log \left(p_{x}\rho _{x}\right)=\sum _{x=1}^{n}\log p_{x}|x\rangle \langle x|\otimes I^{Q}+\sum _{x=1}^{n}|x\rangle \langle x|\otimes \log \rho _{x},

where $I^{Q}$ is the identity operator on the quantum system $Q$ . Then, the right-hand side is

{\begin{aligned}S(X:Q)&=S(X)+S(Q)-S(XQ)\\&=S(X)+S(\rho )+\operatorname {tr} \left(\rho ^{XQ}\log \rho ^{XQ}\right)\\&=S(X)+S(\rho )+\operatorname {tr} \left(\sum _{x=1}^{n}p_{x}\log p_{x}|x\rangle \langle x|\otimes \rho _{x}\right)+\operatorname {tr} \left(\sum _{x=1}^{n}p_{x}|x\rangle \langle x|\otimes \rho _{x}\log \rho _{x}\right)\\&=S(X)+S(\rho )+\underbrace {\operatorname {tr} \left(\sum _{x=1}^{n}p_{x}\log p_{x}|x\rangle \langle x|\right)} _{-S(X)}+\operatorname {tr} \left(\sum _{x=1}^{n}p_{x}\rho _{x}\log \rho _{x}\right)\\&=S(\rho )+\sum _{x=1}^{n}p_{x}\underbrace {\operatorname {tr} \left(\rho _{x}\log \rho _{x}\right)} _{-S(\rho _{x})}\\&=S(\rho )-\sum _{x=1}^{n}p_{x}S(\rho _{x}),\end{aligned}}

which completes the proof.

Comments and remarks

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.^[3]

Related Research Articles

In quantum mechanics, a density matrix is a matrix that describes the quantum state of a physical system. It allows for the calculation of the probabilities of the outcomes of any measurement performed upon this system, using the Born rule. It is a generalization of the more usual state vectors or wavefunctions: while those can only represent pure states, density matrices can also represent mixed states. Mixed states arise in quantum mechanics in two different situations:

when the preparation of the system is not fully known, and thus one must deal with a statistical ensemble of possible preparations, and
when one wants to describe a physical system which is entangled with another, without describing their combined state.

Quantum decoherence is the loss of quantum coherence, the process in which a system's behaviour changes from that which can be explained by quantum mechanics to that which can be explained by classical mechanics. In quantum mechanics, particles such as electrons are described by a wave function, a mathematical representation of the quantum state of a system; a probabilistic interpretation of the wave function is used to explain various quantum effects. As long as there exists a definite phase relation between different states, the system is said to be coherent. A definite phase relationship is necessary to perform quantum computing on quantum information encoded in quantum states. Coherence is preserved under the laws of quantum physics.

In physics, a partition function describes the statistical properties of a system in thermodynamic equilibrium. Partition functions are functions of the thermodynamic state variables, such as the temperature and volume. Most of the aggregate thermodynamic variables of the system, such as the total energy, free energy, entropy, and pressure, can be expressed in terms of the partition function or its derivatives. The partition function is dimensionless.

In quantum physics, a measurement is the testing or manipulation of a physical system to yield a numerical result. A fundamental feature of quantum theory is that the predictions it makes are probabilistic. The procedure for finding a probability involves combining a quantum state, which mathematically describes a quantum system, with a mathematical representation of the measurement to be performed on that system. The formula for this calculation is known as the Born rule. For example, a quantum particle like an electron can be described by a quantum state that associates to each point in space a complex number called a probability amplitude. Applying the Born rule to these amplitudes gives the probabilities that the electron will be found in one region or another when an experiment is performed to locate it. This is the best the theory can do; it cannot say for certain where the electron will be found. The same quantum state can also be used to make a prediction of how the electron will be moving, if an experiment is performed to measure its momentum instead of its position. The uncertainty principle implies that, whatever the quantum state, the range of predictions for the electron's position and the range of predictions for its momentum cannot both be narrow. Some quantum states imply a near-certain prediction of the result of a position measurement, but the result of a momentum measurement will be highly unpredictable, and vice versa. Furthermore, the fact that nature violates the statistical conditions known as Bell inequalities indicates that the unpredictability of quantum measurement results cannot be explained away as due to ignorance about "local hidden variables" within quantum systems.

In linear algebra and functional analysis, the partial trace is a generalization of the trace. Whereas the trace is a scalar valued function on operators, the partial trace is an operator-valued function. The partial trace has applications in quantum information and decoherence which is relevant for quantum measurement and thereby to the decoherent approaches to interpretations of quantum mechanics, including consistent histories and the relative state interpretation.

In physics, the von Neumann entropy, named after John von Neumann, is an extension of the concept of Gibbs entropy from classical statistical mechanics to quantum statistical mechanics. For a quantum-mechanical system described by a density matrix $ρ$ , the von Neumann entropy is

In functional analysis and quantum information science, a positive operator-valued measure (POVM) is a measure whose values are positive semi-definite operators on a Hilbert space. POVMs are a generalization of projection-valued measures (PVM) and, correspondingly, quantum measurements described by POVMs are a generalization of quantum measurement described by PVMs.

In quantum mechanics, notably in quantum information theory, fidelity is a measure of the "closeness" of two quantum states. It expresses the probability that one state will pass a test to identify as the other. The fidelity is not a metric on the space of density matrices, but it can be used to define the Bures metric on this space.

In quantum information theory, quantum relative entropy is a measure of distinguishability between two quantum states. It is the quantum mechanical analog of relative entropy.

In quantum information theory, quantum mutual information, or von Neumann mutual information, after John von Neumann, is a measure of correlation between subsystems of quantum state. It is the quantum mechanical analog of Shannon mutual information.

In physics, a quantum instrument is a mathematical abstraction of a quantum measurement, capturing both the classical and quantum outputs. It combines the concepts of measurement and quantum operation. It can be equivalently understood as a quantum channel that takes as input a quantum system and has as its output two systems: a classical system containing the outcome of the measurement and a quantum system containing the post-measurement state.

In quantum mechanics, and especially quantum information theory, the purity of a normalized quantum state is a scalar defined as

A Werner state is a × -dimensional bipartite quantum state density matrix that is invariant under all unitary operators of the form $. That is, it is a bipartite quantum state that satisfies$

In quantum mechanics, and especially quantum information and the study of open quantum systems, the trace distanceT is a metric on the space of density matrices and gives a measure of the distinguishability between two states. It is the quantum generalization of the Kolmogorov distance for classical probability distributions.

In the theory of quantum communication, an amplitude damping channel is a quantum channel that models physical processes such as spontaneous emission. A natural process by which this channel can occur is a spin chain through which a number of spin states, coupled by a time independent Hamiltonian, can be used to send a quantum state from one location to another. The resulting quantum channel ends up being identical to an amplitude damping channel, for which the quantum capacity, the classical capacity and the entanglement assisted classical capacity of the quantum channel can be evaluated.

In quantum information theory, the idea of a typical subspace plays an important role in the proofs of many coding theorems. Its role is analogous to that of the typical set in classical information theory.

The entropy of entanglement is a measure of the degree of quantum entanglement between two subsystems constituting a two-part composite quantum system. Given a pure bipartite quantum state of the composite system, it is possible to obtain a reduced density matrix describing knowledge of the state of a subsystem. The entropy of entanglement is the Von Neumann entropy of the reduced density matrix for any of the subsystems. If it is non-zero, i.e. the subsystem is in a mixed state, it indicates the two subsystems are entangled.

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 and that in turn is never greater than the Hartley or max-entropy, defined as the logarithm of the number of outcomes with nonzero probability.

Generalized relative entropy is a measure of dissimilarity between two quantum states. It is a "one-shot" analogue of quantum relative entropy and shares many properties of the latter quantity.

The quantum Fisher information is a central quantity in quantum metrology and is the quantum analogue of the classical Fisher information. The quantum Fisher information $of a state with respect to the observable is defined as$

References

1 2 Nielsen & Chuang (2000).
↑ Preskill, John (June 2016). "Chapter 10. Quantum Shannon Theory" (PDF). Quantum Information. pp. 23–24. Retrieved 30 June 2021.
↑ Maslov, Dmitri; Kim, Jin-Sung; Bravyi, Sergey; Yoder, Theodore J.; Sheldon, Sarah (2021-06-28). "Quantum advantage for computations with limited space". Nature Physics. 17 (8): 894–897. arXiv: 2008.06478 . Bibcode:2021NatPh..17..894M. doi:10.1038/s41567-021-01271-7. S2CID 221136153.