Upper bound on the knowable information of a quantum state
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.
Statement of the 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
, with the i-th state prepared with probability
. Let
be the classical register containing the choice of state made by Alice. Bob's objective is to recover the value of
from measurement results on the state he received. Let
be the classical register containing Bob's measurement outcome. Note that
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
and
, 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
and
as the (classical) mutual information between the two registers maximized over all possible choices of measurements on Bob's side:
![{\displaystyle I_{\rm {acc}}(X:Y)=\sup _{\{\Pi _{i}^{B}\}_{i}}I(X:Y|\{\Pi _{i}^{B}\}_{i}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91ec6f8bbf5c6087ffc356de2089ddc5031a4e7b)
where
![{\displaystyle I(X:Y|\{\Pi _{i}^{B}\}_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6dce5b9be1cfc578a84217252663bd5257c00263)
is the (classical) mutual information of the joint probability distribution given by
![{\displaystyle p_{ij}=p_{i}\operatorname {Tr} (\Pi _{j}^{B}\rho _{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cf224fe520b68df76bb16d5e180705420208439)
. 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_{\rm {acc}}(X:Y)\leq \chi (\eta )\equiv S\left(\sum _{i}p_{i}\rho _{i}\right)-\sum _{i}p_{i}S(\rho _{i}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31778f890ad5c71dbbdbba11076a738ab708e011)
where
![{\displaystyle \eta \equiv \{(p_{i},\rho _{i})\}_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3a1d8ad677790b3e8fb69573a3caf05e0c27ff2)
is the ensemble of states Alice is using to send information, and
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
is the
von Neumann entropy. This
![{\displaystyle \chi (\eta )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0850c85751dda872215897a9990e0f1563d5e0ca)
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:
![{\displaystyle \chi (\eta )=I\left(\sum _{i}p_{i}|i\rangle \!\langle i|\otimes \rho _{i}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d5281ffb591c1d501b3a1a087a29efdc6fa84e8)
with
![{\displaystyle I(\rho _{AB})\equiv S(\rho _{A})+S(\rho _{B})-S(\rho _{AB})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efc040b43292f81f398fe58e630b392da18080a3)
the quantum mutual information of the bipartite state
![{\displaystyle \rho _{AB}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52dc0328876861971e9b6cbb560f05d99a2c85f8)
. 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.
Proof
Consider the composite system that describes the entire communication process, which involves Alice's classical input
, the quantum system
, and Bob's classical output
. The classical input
can be written as a classical register
with respect to some orthonormal basis
. By writing
in this manner, the von Neumann entropy
of the state
corresponds to the Shannon entropy
of the probability distribution
:
![{\displaystyle 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/541c4b105c8c19f36afaf7bd3c2987684aca2ef1)
The initial state of the system, where Alice prepares the state
with probability
, is described by
![{\displaystyle \rho ^{XQ}:=\sum _{x=1}^{n}p_{x}|x\rangle \langle x|\otimes \rho _{x}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6902784913fe8c6a150c8ad78b08c17506eeaf66)
Afterwards, Alice sends the quantum state to Bob. As Bob only has access to the quantum system
but not the input
, he receives a mixed state of the form
. Bob measures this state with respect to the POVM elements
, and the probabilities
of measuring the outcomes
form the classical output
. This measurement process can be described as a quantum instrument
![{\displaystyle {\mathcal {E}}^{Q}(\rho _{x})=\sum _{y=1}^{m}q_{y|x}\rho _{y|x}\otimes |y\rangle \langle y|,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b37cd2fb1cd105ace343a84fb2c0edcfd1ad820d)
where
is the probability of outcome
given the state
, while
for some unitary
is the normalised post-measurement state. Then, the state of the entire system after the measurement process is
![{\displaystyle \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|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb7bd4c52bfd1108927565e64519860aeae18c50)
Here
is the identity channel on the system
. Since
is a quantum channel, and the quantum mutual information is monotonic under completely positive trace-preserving maps,[1]
. Additionally, as the partial trace over
is also completely positive and trace-preserving,
. These two inequalities give
![{\displaystyle S(X:Y)\leq S(X:Q).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3161710f8a949a8588f968061109e2f1d8587160)
On the left-hand side, the quantities of interest depend only on
![{\displaystyle \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|,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72672dcd69b2576cda56903b143ca84e1a2bd896)
with joint probabilities
. Clearly,
and
, which are in the same form as
, describe classical registers. Hence,
![{\displaystyle S(X:Y)=S(X)+S(Y)-S(XY)=H(X)+H(Y)-H(XY)=I(X:Y).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/522f00f105e1f49d20b30a26a465958fa8c1f42b)
Meanwhile,
depends on the term
![{\displaystyle \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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c74950b8dba4144d4e88986ed9dd52996c1611b)
where
is the identity operator on the quantum system
. Then, the right-hand side is
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a0c64885b694802d5bc24dbee8412669ad28318)
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.[2]
See also
References
Further reading