Holevo's theorem is an important limitative theorem inquantum computing, an interdisciplinary field ofphysics andcomputer science. It is sometimes calledHolevo's bound, since it establishes anupper bound to the amount of information that can be known about aquantum state (accessible information). It was published byAlexander Holevo in 1973.

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${\displaystyle \{{\rho }_1,...,{\rho }_n\}}$, with the i-th state prepared with probability${\displaystyle p_i}$. Let${\displaystyle X}$ be the classical register containing the choice of state made by Alice. Bob's objective is to recover the value of${\displaystyle X}$ from measurement results on the state he received. Let${\displaystyle Y}$ be the classical register containing Bob's measurement outcome. Note that${\displaystyle Y}$ is therefore a random variable whose probability distribution depends on Bob's choice ofmeasurement.

Holevo's theorem bounds the amount of correlation between the classical registers${\displaystyle X}$ and${\displaystyle Y}$, regardless of Bob's measurement choice, in terms of theHolevo 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 theaccessible information between${\displaystyle X}$ and${\displaystyle Y}$ as the (classical) mutual information between the two registers maximized over all possible choices of measurements on Bob's side:$${\displaystyle I_{\mathrm{a}\mathrm{c}\mathrm{c}}(X:Y)=\underset{\{{\mathrm{\Pi }}_i^B{\}}_i}{sup}I(X:Y|\{{\mathrm{\Pi }}_i^B{\}}_i),}$$where${\displaystyle I(X:Y|\{{\mathrm{\Pi }}_i^B{\}}_i)}$ is the (classical) mutual information of the joint probability distribution given by${\displaystyle p_{ij}=p_i\mathrm{Tr}({\mathrm{\Pi }}_j^B{\rho }_i)}$. There is currently no known formula to analytically solve the optimization in the definition of accessible information in the general case. Nonetheless, we always have the upper bound:$${\displaystyle I_{\mathrm{a}\mathrm{c}\mathrm{c}}(X:Y)\le \chi (\eta )\equiv S\left(\sum _i{p}_i{\rho }_i\right)-\sum _i{p}_{i}S({\rho }_i),}$$where${\displaystyle \eta \equiv \{(p_i,{\rho }_i){\}}_i}$ is the ensemble of states Alice is using to send information, and${\displaystyle S}$ is thevon Neumann entropy. This${\displaystyle \chi (\eta )}$ is called theHolevo information orHolevoχ quantity.

Note that the Holevo information also equals thequantum mutual information of the classical-quantum state corresponding to the ensemble:$${\displaystyle \chi (\eta )=I\left(\sum _i{p}_i|i⟩⟨i|\otimes {\rho }_i\right),}$$with${\displaystyle I({\rho }_{AB})\equiv S({\rho }_A)+S({\rho }_B)-S({\rho }_{AB})}$ the quantum mutual information of the bipartite state${\displaystyle {\rho }_{AB}}$. 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${\displaystyle X}$, the quantum system${\displaystyle Q}$, and Bob's classical output${\displaystyle Y}$. The classical input${\displaystyle X}$ can be written as a classical register${\displaystyle {\rho }^X:={\sum }_{x=1}^n{p}_x|x⟩⟨x|}$ with respect to some orthonormal basis${\displaystyle \{|x⟩{\}}_{x=1}^n}$. By writing${\displaystyle X}$ in this manner, thevon Neumann entropy${\displaystyle S(X)}$ of the state${\displaystyle {\rho }^X}$ corresponds to theShannon entropy${\displaystyle H(X)}$ of the probability distribution${\displaystyle \{p_x{\}}_{x=1}^n}$:

${\displaystyle S(X)=-\mathrm{tr}\left({\rho }^X\log {\rho }^X\right)=-\mathrm{tr}\left(\sum _{x=1}^n{p}_x\log p_x|x⟩⟨x|\right)=-\sum _{x=1}^n{p}_x\log p_x=H(X).}$

The initial state of the system, where Alice prepares the state${\displaystyle {\rho }_x}$ with probability${\displaystyle p_x}$, is described by

${\displaystyle {\rho }^{XQ}:=\sum _{x=1}^n{p}_x|x⟩⟨x|\otimes {\rho }_x.}$

Afterwards, Alice sends the quantum state to Bob. As Bob only has access to the quantum system${\displaystyle Q}$ but not the input${\displaystyle X}$, he receives a mixed state of the form${\displaystyle \rho :={\mathrm{tr}}_X\left({\rho }^{XQ}\right)={\sum }_{x=1}^n{p}_x{\rho }_x}$. Bob measures this state with respect to thePOVM elements${\displaystyle \{E_y{\}}_{y=1}^m}$, and the probabilities${\displaystyle \{q_y{\}}_{y=1}^m}$ of measuring the outcomes${\displaystyle y=1,2,\dots ,m}$ form the classical output${\displaystyle Y}$. This measurement process can be described as aquantum instrument

${\displaystyle {\mathcal{E}}^Q({\rho }_x)=\sum _{y=1}^m{q}_{y|x}{\rho }_{y|x}\otimes |y⟩⟨y|,}$

where${\displaystyle q_{y|x}=\mathrm{tr}\left(E_y{\rho }_x\right)}$ is the probability of outcome${\displaystyle y}$ given the state${\displaystyle {\rho }_x}$, while${\displaystyle {\rho }_{y|x}=W\sqrt{E_y}{\rho }_x\sqrt{E_y}{W}^{†}/q_{y|x}}$ for some unitary${\displaystyle W}$ is the normalisedpost-measurement state. Then, the state of the entire system after the measurement process is

${\displaystyle {\rho }^{X{Q}^{\prime }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⟩⟨x|\otimes {\rho }_{y|x}\otimes |y⟩⟨y|.}$

Here${\displaystyle {\mathcal{I}}^X}$ is the identity channel on the system${\displaystyle X}$. Since${\displaystyle {\mathcal{E}}^Q}$ is aquantum channel, and thequantum mutual information is monotonic undercompletely positive trace-preserving maps,^[1]${\displaystyle S(X:Q^{\prime }Y)\le S(X:Q)}$. Additionally, as thepartial trace over${\displaystyle Q^{\prime }}$ is also completely positive and trace-preserving,${\displaystyle S(X:Y)\le S(X:Q^{\prime }Y)}$. These two inequalities give

${\displaystyle S(X:Y)\le S(X:Q).}$

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

${\displaystyle {\rho }^{XY}:={\mathrm{tr}}_{Q^{\prime }}\left({\rho }^{X{Q}^{\prime }Y}\right)=\sum _{x=1}^n\sum _{y=1}^m{p}_x{q}_{y|x}|x⟩⟨x|\otimes |y⟩⟨y|=\sum _{x=1}^n\sum _{y=1}^m{p}_{x,y}|x,y⟩⟨x,y|,}$

withjoint probabilities${\displaystyle p_{x,y}=p_x{q}_{y|x}}$. Clearly,${\displaystyle {\rho }^{XY}}$ and${\displaystyle {\rho }^Y:={\mathrm{tr}}_X({\rho }^{XY})}$, which are in the same form as${\displaystyle {\rho }^X}$, describe classical registers. Hence,

${\displaystyle S(X:Y)=S(X)+S(Y)-S(XY)=H(X)+H(Y)-H(XY)=I(X:Y).}$

Meanwhile,${\displaystyle S(X:Q)}$ depends on the term

${\displaystyle \log {\rho }^{XQ}=\log \left(\sum _{x=1}^n{p}_x|x⟩⟨x|\otimes {\rho }_x\right)=\sum _{x=1}^n|x⟩⟨x|\otimes \log \left(p_x{\rho }_x\right)=\sum _{x=1}^n\log p_x|x⟩⟨x|\otimes I^Q+\sum _{x=1}^n|x⟩⟨x|\otimes \log {\rho }_x,}$

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

which completes the proof.

In essence, the Holevo bound proves that givennqubits, although they can "carry" a larger amount of (classical) information (thanks to quantum superposition), the amount of classical information that can beretrieved, i.e.accessed, can be only up ton 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.^[2]

• Superdense coding

• Holevo, Alexander S. (1973). "Bounds for the quantity of information transmitted by a quantum communication channel".Problems of Information Transmission.9:177–183.
• Nielsen, Michael A.;Chuang, Isaac L. (2000).Quantum Computation and Quantum Information. Cambridge, UK: Cambridge University Press.ISBN 978-0-521-63235-5.OCLC 43641333. (see page 531, subsection 12.1.1 - equation (12.6) )
• Wilde, Mark M. (2011). "From Classical to Quantum Shannon Theory".arXiv:1106.1445v2 [quant-ph].. See in particular Section 11.6 and following. Holevo's theorem is presented as exercise 11.9.1 on page 288.

• Quantum mechanical entropy
• Quantum information theory
• Limits of computation

• Use American English from January 2019
• All Wikipedia articles written in American English
• Articles with short description
• Short description matches Wikidata