Holevo's theorem

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 $\backslash \{\backslash rho\_1,...,\backslash rho\_n\backslash \}$, with the i-th state prepared with probability $p\_i$. Let $X$ be the classical register containing the choice of state made by Alice. Bob's objective is to recover the value of $X$ from measurement results on the state he received. Let $Y$ be the classical register containing Bob's measurement outcome. Note that $Y$ 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 $X$ and $Y$, 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 $X$ and $Y$ as the (classical) mutual information between the two registers maximized over all possible choices of measurements on Bob's side:$$I\_\{\backslash rm\; acc\}(X:Y)\; =\; \backslash sup\_\{\backslash \{\backslash Pi^B\_i\backslash \}\_i\; \}\; I(X:Y|\backslash \{\backslash Pi^B\_i\backslash \}\_i),$$where $I(X:Y|\backslash \{\backslash Pi^B\_i\backslash \}\_i)$ is the (classical) mutual information of the joint probability distribution given by $p\_\{ij\}\; =\; p\_i\; \backslash operatorname\{Tr\}(\backslash Pi^B\_j\; \backslash 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:$$I\_\{\backslash rm\; acc\}\; (X\; :\; Y)\; \backslash leq\; \backslash chi(\backslash eta)\; \backslash equiv\; S\backslash left(\backslash sum\_i\; p\_i\; \backslash rho\_i\backslash right)\; -\; \backslash sum\_i\; p\_i\; S(\backslash rho\_i),$$where $\backslash eta\backslash equiv\backslash \{(p\_i,\backslash rho\_i)\backslash \}\_i$ is the ensemble of states Alice is using to send information, and $S$ is the von Neumann entropy. This $\backslash chi(\backslash eta)$ is called the Holevo information or Holevo χ quantity.

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

:$\backslash rho^\{XQ\}\; :=\; \backslash sum\_\{x=1\}^n\; p\_x\; |x\backslash rangle\; \backslash langle\; x|\backslash otimes\backslash 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 $\backslash rho\; :=\; \backslash operatorname\{tr\}\_X\backslash left(\backslash rho^\{XQ\}\backslash right)\; =\; \backslash sum\backslash nolimits\_\{x=1\}^n\; p\_x\; \backslash rho\_x$. Bob measures this state with respect to the POVM elements $\backslash \{E\_y\backslash \}\_\{y=1\}^m$, and the probabilities $\backslash \{q\_y\backslash \}\_\{y=1\}^m$ of measuring the outcomes $y=1,2,\backslash dots,m$ form the classical output $Y$. This measurement process can be described as a quantum instrument

:$\backslash mathcal\{E\}^\{Q\}(\backslash rho\_x)\; =\; \backslash sum\_\{y=1\}^m\; q\_\{y|x\}\; \backslash rho\_\{y|x\}\; \backslash otimes\; |y\backslash rangle\; \backslash langle\; y|,$

where $q\_\{y|x\}\; =\; \backslash operatorname\{tr\}\backslash left(E\_y\backslash rho\_x\backslash right)$ is the probability of outcome $y$ given the state $\backslash rho\_x$, while $\backslash rho\_\{y|x\}\; =\; W\backslash sqrt\{E\_y\}\backslash rho\_x\backslash sqrt\{E\_y\}W^\backslash 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

:$\backslash rho^\{XQ\text{'}Y\}\; :=\; \backslash left[\backslash mathcal\{I\}^\{X\}\backslash otimes\backslash mathcal\{E\}^\{Q\}\backslash right]\backslash !\backslash left(\backslash rho^\{XQ\}\backslash right)\; =\; \backslash sum\_\{x=1\}^n\backslash sum\_\{y=1\}^m\; p\_x\; q\_\{y|x\}\; |x\backslash rangle\; \backslash langle\; x|\backslash otimes\backslash rho\_\{y|x\}\backslash otimes\; |y\backslash rangle\; \backslash langle\; y|.$

Here $\backslash mathcal\{I\}^X$ is the identity channel on the system $X$. Since $\backslash mathcal\{E\}^Q$ is a quantum channel, and the quantum mutual information is monotonic under completely positive trace-preserving maps,{{cite book |last=Preskill |first=John |date=June 2016|title=Quantum Information |chapter=Chapter 10. Quantum Shannon Theory |chapter-url= https://authors.library.caltech.edu/66493/2/chap10_15.pdf |pages=23–24 |access-date= 30 June 2021}} $S(X:Q\text{'}Y)\; \backslash leq\; S(X:Q)$. Additionally, as the partial trace over $Q\text{'}$ is also completely positive and trace-preserving, $S(X:Y)\; \backslash leq\; S(X:Q\text{'}Y)$. These two inequalities give

:$S(X:Y)\; \backslash leq\; S(X:Q).$

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

:$\backslash rho^\{XY\}\; :=\; \backslash operatorname\{tr\}\_\{Q\text{'}\}\backslash left(\backslash rho^\{XQ\text{'}Y\}\backslash right)\; =\; \backslash sum\_\{x=1\}^n\backslash sum\_\{y=1\}^m\; p\_x\; q\_\{y|x\}\; |x\backslash rangle\; \backslash langle\; x|\backslash otimes\; |y\backslash rangle\; \backslash 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, $\backslash rho^\{XY\}$ and $\backslash rho^Y\; :=\; \backslash operatorname\{tr\}\_X(\backslash rho^\{XY\})$, which are in the same form as $\backslash 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

:$\backslash log\; \backslash rho^\{XQ\}\; =\; \backslash log\backslash left(\backslash sum\_\{x=1\}^n\; p\_x\; |x\backslash rangle\; \backslash langle\; x|\backslash otimes\backslash rho\_x\backslash 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

:$\backslash 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.

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.{{Cite journal| doi = 10.1038/s41567-021-01271-7 | volume = 17| pages = 894–897 | last1 =Maslov| first1 = Dmitri| last2 = Kim| first2 = Jin-Sung| last3 = Bravyi| first3 = Sergey| last4 = Yoder| first4 = Theodore J.| last5 = Sheldon| first5 = Sarah| title = Quantum advantage for computations with limited space| journal = Nature Physics| date = 2021-06-28 | issue = 8| arxiv = 2008.06478| bibcode = 2021NatPh..17..894M| s2cid = 221136153}}

• Superdense coding

{{Reflist}}

• {{cite journal|first=Alexander S.|last=Holevo|authorlink=Alexander Holevo|title=Bounds for the quantity of information transmitted by a quantum communication channel|journal=Problems of Information Transmission|volume=9|pages=177–183|year=1973}}
• {{cite book |title=Quantum Computation and Quantum Information |last1=Nielsen |first1=Michael A. |authorlink1=Michael Nielsen |last2=Chuang |first2=Isaac L. |authorlink2=Isaac Chuang |year=2000 |publisher=Cambridge University Press |location=Cambridge, UK |isbn=978-0-521-63235-5 |oclc=43641333}} (see page 531, subsection 12.1.1 - equation (12.6) )
• {{cite arXiv | first = Mark M. | last = Wilde | title= From Classical to Quantum Shannon Theory |year= 2011| class = quant-ph | eprint= 1106.1445v2 }}. See in particular Section 11.6 and following. Holevo's theorem is presented as exercise 11.9.1 on page 288.

{{Quantum computing}}

Category:Quantum mechanical entropy

Category:Quantum information theory

Category:Limits of computation