Lecture Note: Accessible Information, Data Compression
Based on Lecture 16 Content
November 18, 2025
1 Accessible Information, Data Compression
1.1 Concepts Covered
1. Information
2. Mutual Information.
3. Accessible Information, Data Compression
4. Holevo bound
5. Shannon’s Source Coding Theorem.
6. Schumacher’s Noiseless Channel Coding Theorem
7. Shannon’s Noisy Channel Coding Theorem.
8. HSW Theorem.
9. Channel Capacity (Classical)
2 Information
INFORMATION (or Information gain) may be defined as the reduction of uncertainty in our knowl-
edge of a system.
Assuming a System can exist in a set of states X = {x1 , . . . , xn } with associated probabilities
p1 , . . . , pn . If we consider a measurement that reveals the i-th state, our knowledge about the sys-
tem state is reduced by an amount that is a function of the probability pi . This ’gain’ of Information,
also called ’Surprisal’, can be quantified using a function, I, that satisfies the following axioms:
A1. The information function, I, depends only on the probability of the event (or state): I = I(pi ).
A2. Events that are Certain (p = 1) provide zero Information or Surprisal: I(1) = 0.
A3. Information gain when two independent events occur is the sum of Information gains of the two
events: I(p1 p2 ) = I(p1 ) + I(p2 ).
A4. I(p) is a monotonically decreasing function of p.
Axioms A1-A4 uniquely identify the Information function (proof in class) to be:
I(p) = k log(1/p)
The expected Surprisal or Information gain, on average, in a single determination of the random variable
X is, therefore, X
⟨I(p)⟩ = k pi log(1/pi )
i
The normalization constant k can be chosen to be 1 by taking the ⟨I(p)⟩ of a uniformly-random, binary
outcome experiment to be 1. By convention, we often use base 2 logarithm, and k = 1, giving the result
in bits. We denote the expected gain by H(⃗
p) for the probability vector p⃗ = (p1 , p2 , . . . , pn ). This is the
Shannon Entropy. X
p) = −
H(⃗ pi log pi
i
1
3 Mutual Information
Suppose Alice has a Random Variable (RV) X that takes values {0, . . . , n} with probabilities px . Bob
measures X and obtains outcomes Y (values {0, . . . , m}). We want to answer the question: How much
information can Bob gain about the RV X?
This is quantified by the Mutual Information of X and Y , denoted I(X : Y ) (or H(X : Y ) in
some notation).
The entropic quantities relevant to this question are:
1. Joint entropy: X
H(X, Y ) := − p(x, y) log p(x, y)
x,y
2. Conditional entropy:
H(X|Y ) := H(X, Y ) − H(Y ) (Entropy of X given Y )
H(Y |X) := H(X, Y ) − H(X) (Entropy of Y given X)
3. Mutual Information:
I(X : Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X)
I(X : Y ) = H(X) + H(Y ) − H(X, Y )
A visual aid to these entropies is the Venn diagram:
H(X) H(Y )
H(X|Y ) I(X : Y ) H(Y |X)
H(X, Y )
Figure 1: Venn Diagram Representation of Classical Entropies.
3.1 Properties of Information Measures
1. Symmetry: H(X, Y ) = H(Y, X) (Joint entropy is symmetric).
2. Symmetry: I(X : Y ) = I(Y : X) (Mutual Information is symmetric).
3. Upper Bound: H(Y |X) ≥ 0 ⇒ I(X : Y ) ≤ H(Y ) and I(X : Y ) ≤ H(X).
4. Subadditivity: H(X, Y ) ≤ H(X) + H(Y ).
5. Functional Dependence: If Y is a deterministic function of X, i.e., Y = f (X), then H(X) =
H(Y ) = H(X, Y ), which implies H(X|Y ) = 0. In this case, the Mutual Information is maximized:
I(X : Y ) = H(X). This means the measurement Y extracts the maximum possible information
about X.
2
3.2 Encoding Information in Quantum States
In the classical case, if Alice prepares classical states (e.g., 0 or 1) to encode her data, it is possible for
Bob to extract all the information that the RV X has, i.e., I(X : Y ) = H(X).
In the Quantum Case, this is not true in general, and I(X : Y ) < H(X) depending on how the
state is prepared by Alice and what measurements are performed by Bob.
If Alice uses quantum states {ρx } to encode her information, and Bob uses quantum measurements
(POVM) to extract that information, we seek the maximum extractable Information by Bob, which
is the Accessible Information encoded in the state prepared by Alice.
Due to the fact that non-orthogonal quantum states are not perfectly distinguishable (unlike classical
states), the accessible information is always less than or equal to the preparation entropy H(X).
I(X : Y ) ≤ H(X)
Equality is possible only when the encoding states are orthogonal, ⟨ϕ|ψ⟩ = 0. The difficulty in information
extraction from non-orthogonal states is a consequence of the No-Cloning Theorem.
4 The Holevo Bound
The above intuition is formalized by the Holevo Bound (Nielsen & Chuang, Sec 12.1.1), which tells us
the upper bound on the information extractable from a quantum state ensemble, {ρx , px }, prepared by
Alice. P
Alice prepares the state ρx with probability px , where x = 0, . . . , n. The average state is ρ = x px ρx .
Bob performs a measurement with POVM elements {Ey } = {E0 , . . . , Em }, obtaining outcome Y .
The Mutual Information I(X : Y ) between the preparation variable X and the measurement outcome
Y is bounded by the Holevo χ quantity:
Holevo Bound: I(X : Y ) ≤ χ
where the Holevo χ quantity is defined as:
X
χ = S(ρ) − px S(ρx )
x
• S(ρ) is the Von Neumann entropy of the average state ρ.
• S(ρx ) is the Von Neumann entropy of the individual state ρx .
The Holevo χ quantity is itself upper bounded by the preparation entropy H(X) of Alice:
χ ≤ H(X)
P
This follows from the property of Von Neumann entropy that S(ρ) ≤ x px S(ρx ) + H(⃗
p), where p⃗ is the
distribution {px }.
4.1 Maximizing Accessible Information
1. χ sets the limit on how much information Bob can extract from the quantum state ensemble
{ρx , px } using the best possible measurement scheme.
2. χ is maximized when Alice encodes her information using **Orthogonal (ON) projection states**
and Bob measures using **projective measurements** on the same orthonormal basis. * Alice uses
ρx = |x⟩⟨x|, where ⟨x|y⟩ = δxy . This means S(ρx ) = 0. * Bob measures using Ey = |y⟩⟨y|.
3. In this case, χ achieves its maximum value, the preparation entropy:
X
χ = S(ρ) − px S(ρx ) = S(ρ) − 0 = H(X)
x
5 Data Compression and Coding Theorems
Quantum information in a state can be compressed much like classical information using the idea of
Typical Sequences.
3
5.1 Typical Sequences (Classical)
For a source of independent and identically distributed (i.i.d.) Random Variables, long output strings
take values from a set of ’typical’ strings which have the expected number of 0’s and 1’s (or, more
generally, the expected proportion of each symbol).
If Xi takes 0 with probability p and 1 with probability (1 − p), a typical sequence x1 . . . xn of length
n will have approximately np zeros and n(1 − p) ones. The probability of obtaining such a sequence is
approximately:
P (x1 . . . xn ) ≈ pnp (1 − p)(1−p)n = 2−nH(X)
where H(X) is the entropy rate of the source.
The number of such typical sequences is approximately 2nH(X) .
5.2 Shannon’s Noiseless Channel Coding Theorem (Classical)
To reliably compress the data from a source of RVs, one needs a compression/decompression scheme. A
1-to-1 mapping from the set of typical sequences to labels can be used, which requires only nH(X) bits
of data.
Theorem: Suppose {Xi } is an i.i.d. source with entropy rate H(X).
• If the compression rate R satisfies R > H(X), then a reliable compression scheme of rate R exists
for the source (the error probability vanishes as n → ∞).
• Conversely, if R < H(X), no reliable compression scheme exists.
The minimum number of bits required to reliably encode the output of n uses of the source is nH(X).
5.3 Schumacher’s Quantum Noiseless Channel Coding Theorem
This is the quantum analogue of the Shannon’s coding theorem (NC, 12.2.2). It concerns compressing n
copies of a quantum state ρ.
Theorem: Let {ρ, pi } be an i.i.d. quantum source.
• If the rate R satisfies R > S(ρ), a reliable compression scheme of rate R exists, where S(ρ) is the
Von Neumann entropy of the state ρ.
• Conversely, if R < S(ρ), no reliable compression scheme exists.
The minimum number of qubits required to reliably encode the output of n uses of the source is nS(ρ).
Encoder Decoder
Compression: ρ⊗n −−−−−→ (qubits)⊗nS(ρ) −−−−−→ ρ⊗n