Holevo’s theorem - Wikipedia

Source: https://en.wikipedia.org/wiki/Holevo%27s_theorem

Ring 2 — Canonical Grounding

Ring 3 — Framework Connections

Upper bound on the knowable information of a quantum state

Holevo’s theorem is a result in quantum information theory. It is sometimes called Holevo’s bound, since it gives an upper bound on the accessible information, which is amount of information that can be known about a quantum state. It was first published by Alexander Holevo in 1973.

Statement

Setting

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

{

1 , … ,

n } {\displaystyle {\rho _{1},…,\rho _{n}}} ${\rho _{1},...,\rho _{n}}$ , with the i-th state prepared with probability

i {\displaystyle p_{i}} $p_{i}$ . Let

X {\displaystyle X} $X$ be the classical register containing the choice of state made by Alice. Bob’s objective is to recover the value of

X {\displaystyle X} $X$ by measuring a POVM on the state he received. Let

Y {\displaystyle Y} $Y$ be the classical register containing Bob’s measurement outcome, which is a random variable whose distribution depends on Bob’s choice of measurement.

Holevo’s theorem bounds the amount of correlation between the classical registers

X {\displaystyle X} $X$ and

Y {\displaystyle Y} $Y$ , independently of Bob’s measurement choice, in terms of the Holevo information. The Holevo information does not depend on the measurement choice, and so this gives a bound which does not require optimizing over all possible measurements.

Precise statement

Define the accessible information between

X {\displaystyle X} $X$ and

Y {\displaystyle Y} $Y$ as the (classical) mutual information between the two registers maximized over all possible choices of Bob’s measurements:

a c c ( X : Y )

sup

{

}

i I ( X : Y

| {

}

i ) , {\displaystyle I_{\rm {acc}}(X:Y)=\sup _{{\Pi _{i}^{B}}_{i}}I(X:Y|{\Pi _{i}^{B}}_{i}),} $I_{\rm {acc}}(X:Y)=\sup _{{\Pi {i}^{B}}{i}}I(X:Y|{\Pi {i}^{B}}{i}),$ where

I ( X : Y

| {

}

i ) {\displaystyle I(X:Y|{\Pi _{i}^{B}}_{i})} $I(X:Y|{\Pi {i}^{B}}{i})$ is the classical mutual information of the joint probability distribution given by

i j

i Tr ⁡ (

i ) {\displaystyle p_{ij}=p_{i}\operatorname {Tr} (\Pi _{j}^{B}\rho _{i})} $p_{ij}=p_{i}\operatorname {Tr} (\Pi _{j}^{B}\rho _{i})$ . There is no known formula for the accessible information in general. However, there is always an upper bound

a c c ( X : Y ) ≤ χ ( η ) ≡ S

(

∑

i ) −

∑

i S (

i ) , {\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}),} $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}),$ where

η ≡ { (

i ,

i )

}

i {\displaystyle \eta \equiv {(p_{i},\rho _{i})}_{i}} $\eta \equiv {(p_{i},\rho {i})}{i}$ is the ensemble of states Alice uses to send information, and

S {\displaystyle S} $S$ is the von Neumann entropy. The quantity

χ ( η ) {\displaystyle \chi (\eta )} $\chi (\eta )$ is called the Holevo information or Holevo χ quantity.

The Holevo information is also equal to the quantum mutual information of the classical-quantum state corresponding to the ensemble:

χ ( η )

(

∑

| i ⟩

⟨ i

| ⊗

i ) , {\displaystyle \chi (\eta )=I\left(\sum _{i}p_{i}|i\rangle !\langle i|\otimes \rho _{i}\right),} $\chi (\eta )=I\left(\sum {i}p{i}|i\rangle !\langle i|\otimes \rho _{i}\right),$ where

I (

A B ) ≡ S (

A ) + S (

B ) − S (

A B ) {\displaystyle I(\rho _{AB})\equiv S(\rho _{A})+S(\rho _{B})-S(\rho _{AB})} $I(\rho _{AB})\equiv S(\rho _{A})+S(\rho _{B})-S(\rho _{AB})$ the quantum mutual information of the bipartite state

A B {\displaystyle \rho _{AB}} $\rho _{AB}$ . Holevo’s theorem can also be stated as a bound on the accessible information in terms of the quantum mutual information of a classical-quantum state.

Proof

Consider the composite system that describes the entire communication process, which involves Alice’s classical input

X {\displaystyle X} $X$ , the quantum system

Q {\displaystyle Q} $Q$ , and Bob’s classical output

Y {\displaystyle Y} $Y$ . The classical input

X {\displaystyle X} $X$ can be written as a classical register

X :=

∑

x

| x ⟩ ⟨ x

| {\displaystyle \rho ^{X}:=\sum \nolimits _{x=1}^{n}p_{x}|x\rangle \langle x|} $\rho ^{X}:=\sum \nolimits {x=1}^{n}p{x}|x\rangle \langle x|$ with respect to some orthonormal basis

{

| x ⟩

}

x

n {\displaystyle {|x\rangle }_{x=1}^{n}} ${|x\rangle }_{x=1}^{n}$ . By writing

X {\displaystyle X} $X$ in this manner, the von Neumann entropy

S ( X ) {\displaystyle S(X)} $S(X)$ of the state

X {\displaystyle \rho ^{X}} $\rho ^{X}$ corresponds to the Shannon entropy

H ( X ) {\displaystyle H(X)} $H(X)$ of the probability distribution

{

}

x

n {\displaystyle {p_{x}}_{x=1}^{n}} ${p_{x}}_{x=1}^{n}$ :

: S ( X ) = − tr ⁡

(

ρ

X
log
⁡

ρ

X
)
=
−
tr
⁡

(

∑

x
=
1

n

p

x
log
⁡

p

x

|
x
⟩
⟨
x

|
)
=
−

∑

x
=
1

n

p

x
log
⁡

p

x
=
H
(
X
)
.
{\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).}
![{\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

x {\displaystyle \rho _{x}} $\rho _{x}$ with probability

x {\displaystyle p_{x}} $p_{x}$ , is described by

: ρ

X
Q
:=

∑

x
=
1

n

p

x

|
x
⟩
⟨
x

|
⊗

ρ

x
.
{\displaystyle \rho ^{XQ}:=\sum \_{x=1}^{n}p\_{x}|x\rangle \langle x|\otimes \rho \_{x}.}
![{\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

Q {\displaystyle Q} $Q$ but not the input

X {\displaystyle X} $X$ , he receives a mixed state of the form

ρ :=

X ⁡

(

X Q )

∑

x

x {\displaystyle \rho :=\operatorname {tr} _{X}\left(\rho ^{XQ}\right)=\sum \nolimits _{x=1}^{n}p_{x}\rho _{x}} $\rho :=\operatorname {tr} _{X}\left(\rho ^{XQ}\right)=\sum \nolimits {x=1}^{n}p{x}\rho _{x}$ . Bob measures this state with respect to the POVM elements

{

}

y

m {\displaystyle {E_{y}}_{y=1}^{m}} ${E_{y}}_{y=1}^{m}$ , and the probabilities

{

}

y

m {\displaystyle {q_{y}}_{y=1}^{m}} ${q_{y}}_{y=1}^{m}$ of measuring the outcomes

y

1 , 2 , … , m {\displaystyle y=1,2,\dots ,m} $y=1,2,\dots ,m$ form the classical output

Y {\displaystyle Y} $Y$ . This measurement process can be described as a quantum instrument

: E

Q
(

ρ

x
)
=

∑

y
=
1

m

q

y

|
x

ρ

y

|
x
⊗

|
y
⟩
⟨
y

|
,
{\displaystyle {\mathcal {E}}^{Q}(\rho \_{x})=\sum \_{y=1}^{m}q\_{y|x}\rho \_{y|x}\otimes |y\rangle \langle y|,}
![{\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

| x

tr ⁡

(

x ) {\displaystyle q_{y|x}=\operatorname {tr} \left(E_{y}\rho _{x}\right)} $q_{y|x}=\operatorname {tr} \left(E_{y}\rho _{x}\right)$ is the probability of outcome

y {\displaystyle y} $y$ given the state

x {\displaystyle \rho _{x}} $\rho _{x}$ , while

| x

†

| x {\displaystyle \rho _{y|x}=W{\sqrt {E_{y}}}\rho _{x}{\sqrt {E_{y}}}W^{\dagger }/q_{y|x}} $\rho {y|x}=W{\sqrt {E{y}}}\rho {x}{\sqrt {E{y}}}W^{\dagger }/q_{y|x}$ for some unitary

W {\displaystyle W} $W$ is the normalised post-measurement state. Then, the state of the entire system after the measurement process is

: ρ

X

Q
′
Y
:=

[

I

X
⊗

E

Q
]

(

ρ

X
Q
)
=

∑

x
=
1

n

∑

y
=
1

m

p

x

q

y

|
x

|
x
⟩
⟨
x

|
⊗

ρ

y

|
x
⊗

|
y
⟩
⟨
y

|
.
{\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|.}
![{\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

X {\displaystyle {\mathcal {I}}^{X}} ${\mathcal {I}}^{X}$ is the identity channel on the system

X {\displaystyle X} $X$ . Since

Q {\displaystyle {\mathcal {E}}^{Q}} ${\mathcal {E}}^{Q}$ is a quantum channel, and the quantum mutual information is monotonic under completely positive trace-preserving maps,

S ( X :

Q ′ Y ) ≤ S ( X : Q ) {\displaystyle S(X:Q’Y)\leq S(X:Q)} $S(X:Q'Y)\leq S(X:Q)$ . Additionally, as the partial trace over

Q ′ {\displaystyle Q’} $Q'$ is also completely positive and trace-preserving,

S ( X : Y ) ≤ S ( X :

Q ′ Y ) {\displaystyle S(X:Y)\leq S(X:Q’Y)} $S(X:Y)\leq S(X:Q'Y)$ . These two inequalities give

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

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

: ρ

X
Y
:=

tr

Q
′
⁡

(

ρ

X

Q
′
Y
)
=

∑

x
=
1

n

∑

y
=
1

m

p

x

q

y

|
x

|
x
⟩
⟨
x

|
⊗

|
y
⟩
⟨
y

|
=

∑

x
=
1

n

∑

y
=
1

m

p

x
,
y

|
x
,
y
⟩
⟨
x
,
y

|
,
{\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|,}
![{\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

x , y

| x {\displaystyle p_{x,y}=p_{x}q_{y|x}} $p_{x,y}=p_{x}q_{y|x}$ . Clearly,

X Y {\displaystyle \rho ^{XY}} $\rho ^{XY}$ and

Y :=

X ⁡ (

X Y ) {\displaystyle \rho ^{Y}:=\operatorname {tr} _{X}(\rho ^{XY})} $\rho ^{Y}:=\operatorname {tr} _{X}(\rho ^{XY})$ , which are in the same form as

X {\displaystyle \rho ^{X}} $\rho ^{X}$ , describe classical registers. Hence,

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

Meanwhile,

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

: log ⁡

ρ

X
Q
=
log
⁡

(

∑

x
=
1

n

p

x

|
x
⟩
⟨
x

|
⊗

ρ

x
)
=

∑

x
=
1

n

|
x
⟩
⟨
x

|
⊗
log
⁡

(

p

x

ρ

x
)
=

∑

x
=
1

n
log
⁡

p

x

|
x
⟩
⟨
x

|
⊗

I

Q
+

∑

x
=
1

n

|
x
⟩
⟨
x

|
⊗
log
⁡

ρ

x
,
{\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},}
![{\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

Q {\displaystyle I^{Q}} $I^{Q}$ is the identity operator on the quantum system

Q {\displaystyle Q} $Q$ . Then, the right-hand side is

: S ( X : Q )

=
S
(
X
)
+
S
(
Q
)
−
S
(
X
Q
)

=
S
(
X
)
+
S
(
ρ
)
+
tr
⁡

(

ρ

X
Q
log
⁡

ρ

X
Q
)

=
S
(
X
)
+
S
(
ρ
)
+
tr
⁡

(

∑

x
=
1

n

p

x
log
⁡

p

x

|
x
⟩
⟨
x

|
⊗

ρ

x
)
+
tr
⁡

(

∑

x
=
1

n

p

x

|
x
⟩
⟨
x

|
⊗

ρ

x
log
⁡

ρ

x
)

=
S
(
X
)
+
S
(
ρ
)
+

tr
⁡

(

∑

x
=
1

n

p

x
log
⁡

p

x

|
x
⟩
⟨
x

|
)
⏟

−
S
(
X
)
+
tr
⁡

(

∑

x
=
1

n

p

x

ρ

x
log
⁡

ρ

x
)

=
S
(
ρ
)
+

∑

x
=
1

n

p

x

tr
⁡

(

ρ

x
log
⁡

ρ

x
)
⏟

−
S
(

ρ

x
)

=
S
(
ρ
)
−

∑

x
=
1

n

p

x
S
(

ρ

x
)
,
{\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}}}
![{\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.

References

^ 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.

* v * t * e Quantum information science
General	* DiVincenzo’s criteria * NISQ era * Quantum computing + timeline * Quantum information * Quantum programming * Quantum simulation * Qubit + physical vs. logical * Quantum processors + cloud-based
Theorems	* Bell’s * Eastin–Knill * Gleason’s * Gottesman–Knill * Holevo’s * No-broadcasting * No-cloning * No-communication * No-deleting * No-hiding * No-teleportation * PBR * Quantum speed limit * Threshold * Solovay–Kitaev * Schrödinger-HJW
Quantum communication	* Classical capacity + entanglement-assisted + quantum capacity * Entanglement distillation * Entanglement swapping * Monogamy of entanglement * LOCC * Quantum channel + quantum network * State purification * Quantum teleportation + quantum energy teleportation + quantum gate teleportation * Superdense coding
Quantum algorithms	* Algorithmic cooling * Amplitude amplification * Bernstein–Vazirani * BHT * Boson sampling * Deutsch–Jozsa * Grover’s * HHL * Hidden subgroup * Magic state distillation * Quantum annealing * Quantum counting * Quantum Fourier transform * Quantum optimization * Quantum phase estimation * Shor’s * Simon’s * VQE
Quantum complexity theory	* BQP * DQC1 * EQP * QIP * QMA * PostBQP
Quantum processor benchmarks	* Quantum supremacy * Quantum volume * QC scaling laws * Randomized benchmarking + XEB * Relaxation times + T1 + T2
Quantum computing models	* Adiabatic quantum computation * Continuous-variable quantum information * One-way quantum computer + cluster state * Quantum circuit + quantum logic gate * Quantum machine learning + quantum neural network * Quantum Turing machine * Topological quantum computer * Hamiltonian quantum computation
Quantum error correction	* Codes + 5 qubit + CSS + GKP + quantum convolutional + stabilizer + Shor + Bacon–Shor + Steane + Toric + gnu * Entanglement-assisted
Physical implementations
Quantum programming	* OpenQASM–Qiskit–IBM QX * Quil–Forest/Rigetti QCS * Cirq * Q# * libquantum * many others…
* Quantum information science * Quantum mechanics topics

GO Vault

Explorer

Holevo_Bound