Simple Algorithm
Quantum Computing · Excited State · 24 min

Quantum Information Theory

Entropy, channels and the ultimate limits of communication.

How many bits does a qubit hold? Infinitely many, if you count the real parameters of its state. Exactly one, if you ask how many you can get back out. Quantum information theory makes this precise with three tools: von Neumann entropy, quantum channels and the Holevo bound. From them it derives the ultimate rates for sending information through noisy quantum channels.

What you’ll learn

  • Compute Shannon and von Neumann entropies and state their operational meaning as compression rates.
  • Evaluate joint and conditional entropies and mutual information for quantum states, and interpret negative conditional entropy.
  • Write quantum channels in Kraus form and compute how depolarizing, dephasing and amplitude-damping noise act on the Bloch vector.
  • State the Holevo bound and use it to show that nn qubits carry at most nn classical bits.
  • Distinguish the classical, quantum and entanglement-assisted capacities, and evaluate all three for the erasure channel.

Shannon's two theorems

Classical information theory rests on one quantity. For a random variable XX with distribution p(x)p(x), the Shannon entropy is

H(X)=−∑xp(x)log⁡2p(x).H(X)=-\sum_x p(x)\log_2p(x).

For a biased coin it is the binary entropy h(p)=−plog⁡2p−(1−p)log⁡2(1−p)h(p)=-p\log_2p-(1-p)\log_2(1-p), which runs from 00 (certain) to 11 bit (fair).

Shannon (1948) gave entropy two operational meanings. Source coding: nn independent copies of XX can be compressed into about nH(X)nH(X) bits and recovered with vanishing error, and no fewer bits suffice. Channel coding: a noisy channel p(y∣x)p(y|x) carries information reliably at any rate below its capacity

C=max⁡p(x)I(X:Y),I(X:Y)=H(X)+H(Y)−H(XY),C=\max_{p(x)}I(X{:}Y),\qquad I(X{:}Y)=H(X)+H(Y)-H(XY),

and at no rate above it.

Predict before you look

A binary symmetric channel flips each bit with probability 11%11\%. Its capacity is 1−h(0.11)1-h(0.11). How many bits per channel use is that?

Show the answer

0.5 bits

h(0.11)=0.11log⁡210.11+0.89log⁡210.89≈0.350+0.150=0.50h(0.11)=0.11\log_2\tfrac{1}{0.11}+0.89\log_2\tfrac{1}{0.89}\approx0.350+0.150=0.50, so C≈0.50C\approx0.50. Not a coincidence you have seen before: the 11% BB84 threshold is where 1−2h(Q)1-2h(Q) vanishes, i.e. where h(Q)=12h(Q)=\tfrac12.

Von Neumann entropy

The von Neumann entropy of a state ρ\rho with eigenvalues λi\lambda_i is the Shannon entropy of its spectrum:

S(ρ)=−Tr⁡ ρlog⁡2ρ=−∑iλilog⁡2λi.S(\rho)=-\Tr\,\rho\log_2\rho=-\sum_i\lambda_i\log_2\lambda_i .
  • 0≤S(ρ)≤log⁡2d0\le S(\rho)\le\log_2d, with S=0S=0 iff ρ\rho is pure and S=log⁡2dS=\log_2d iff ρ=I/d\rho=\id/d.
  • S(UρU†)=S(ρ)S(U\rho U^\dagger)=S(\rho): entropy is basis-independent.
  • Concavity: S(∑ipiρi)≥∑ipiS(ρi)S\big(\sum_ip_i\rho_i\big)\ge\sum_ip_iS(\rho_i). Mixing never decreases entropy.
  • For a qubit with Bloch vector r⃗\vec r, the eigenvalues are 1±∣r⃗∣2\tfrac{1\pm\abs{\vec r}}{2}, so S=h(1+∣r⃗∣2)S=h\big(\tfrac{1+\abs{\vec r}}{2}\big).
DerivationMixing non-orthogonal states creates less entropy
  1. ρ=12∣0⟩ ⁣⟨0∣+12∣+⟩ ⁣⟨+∣=(3/41/41/41/4)\rho=\tfrac12\dyad0+\tfrac12\dyad{+}=\begin{pmatrix}3/4&1/4\\1/4&1/4\end{pmatrix}

    Alice flips a fair coin and sends ∣0⟩\ket0 or ∣+⟩\ket+.

  2. λ±=1±1/22=cos⁡2π8, sin⁡2π8≈0.854, 0.146\lambda_\pm=\frac{1\pm1/\sqrt2}{2}=\cos^2\tfrac\pi8,\ \sin^2\tfrac\pi8\approx0.854,\ 0.146

    Trace 1 and determinant 18\tfrac18. Equivalently, the Bloch vector is 12(z^+x^)\tfrac12(\hat z+\hat x), of length 1/21/\sqrt2.

  3. S(ρ)=h(0.146)≈0.60 bits < H(coin)=1 bitS(\rho)=h(0.146)\approx0.60\ \text{bits}\ <\ H(\text{coin})=1\ \text{bit}

    The overlap ∣⟨0∣+⟩∣2=12\abs{\braket{0|+}}^2=\tfrac12 hides part of the coin's randomness. In general S(∑xpx∣ψx⟩ ⁣⟨ψx∣)≤H(p)S\big(\sum_xp_x\dyad{\psi_x}\big)\le H(p), with equality iff the ∣ψx⟩\ket{\psi_x} are orthogonal.

Entropy of composite systems

For a bipartite state ρAB\rho_{AB} with marginals ρA,ρB\rho_A,\rho_B, define the conditional entropy and mutual information

S(A∣B)=S(AB)−S(B),I(A:B)=S(A)+S(B)−S(AB).S(A|B)=S(AB)-S(B),\qquad I(A{:}B)=S(A)+S(B)-S(AB).

Classically H(A∣B)≥0H(A|B)\ge0: knowing more cannot leave you more uncertain about AA than about the whole. Quantum mechanically this fails.

State of ABABS(A)S(A)S(B)S(B)S(AB)S(AB)S(A∣B)S(A|B)I(A:B)I(A{:}B)
∣0⟩∣0⟩\ket0\ket0 (product)00000
12∣00⟩ ⁣⟨00∣+12∣11⟩ ⁣⟨11∣\tfrac12\dyad{00}+\tfrac12\dyad{11} (classically correlated)11101
∣Φ+⟩=12(∣00⟩+∣11⟩)\ket{\Phi^+}=\tfrac{1}{\sqrt2}(\ket{00}+\ket{11}) (Bell state)110−1-12
A Bell pair is pure as a whole, yet each half is maximally mixed: the whole is less uncertain than its parts.
Check your understanding

A two-qubit state has S(A∣B)<0S(A|B)<0. What can you conclude?

  1. The state is mixed
  2. The state is entangled
  3. Subadditivity is violated
  4. Nothing: conditional entropy can be negative for classically correlated states too
Show the answer

B. The state is entangled

Every separable state has S(A∣B)≥0S(A|B)\ge0, so negative conditional entropy is a witness of entanglement. Operationally, −S(A∣B)-S(A|B) is the entanglement Alice and Bob gain when Alice transfers her share to Bob in quantum state merging (Horodecki, Oppenheim & Winter, 2005).

Quantum channels

A channel is the most general physical process taking states of AA to states of BB. Mathematically it is a linear, completely positive, trace-preserving (CPTP) map, and every such map has a Kraus representation

N(ρ)=∑kKkρKk†,∑kKk†Kk=I.\mathcal N(\rho)=\sum_kK_k\rho K_k^\dagger,\qquad \sum_kK_k^\dagger K_k=\id .

Equivalently (Stinespring), N\mathcal N is a unitary interaction with an environment EE that starts in a fixed state, followed by discarding EE: N(ρ)=Tr⁡E[U(ρ⊗∣0⟩ ⁣⟨0∣E)U†]\mathcal N(\rho)=\Tr_E\big[U(\rho\otimes\dyad0_E)U^\dagger\big]. Noise is information leaking into an environment you do not control.

ChannelKraus operatorsBloch vector (x,y,z)↦(x,y,z)\mapsto
Bit flip1−p I, p X\sqrt{1-p}\,\id,\ \sqrt p\,X(x, (1−2p)y, (1−2p)z)\big(x,\ (1-2p)y,\ (1-2p)z\big)
Phase flip (dephasing)1−p I, p Z\sqrt{1-p}\,\id,\ \sqrt p\,Z((1−2p)x, (1−2p)y, z)\big((1-2p)x,\ (1-2p)y,\ z\big)
Depolarizing (1−p)ρ+p I2(1-p)\rho+p\,\tfrac{\id}21−3p4 I, p2X, p2Y, p2Z\sqrt{1-\tfrac{3p}4}\,\id,\ \tfrac{\sqrt p}{2}X,\ \tfrac{\sqrt p}{2}Y,\ \tfrac{\sqrt p}{2}Z(1−p)(x,y,z)(1-p)(x,y,z)
Amplitude damping(1001−γ), (0γ00)\begin{pmatrix}1&0\\0&\sqrt{1-\gamma}\end{pmatrix},\ \begin{pmatrix}0&\sqrt\gamma\\0&0\end{pmatrix}(1−γ x, 1−γ y, γ+(1−γ)z)\big(\sqrt{1-\gamma}\,x,\ \sqrt{1-\gamma}\,y,\ \gamma+(1-\gamma)z\big)
Unital channels (the first three) shrink the Bloch ball toward its center. Amplitude damping, the T1T_1 process, also pushes it toward ∣0⟩\ket0.
DerivationAmplitude damping on the Bloch ball
  1. K0ρK0†+K1ρK1†=(ρ00+γρ111−γ ρ011−γ ρ10(1−γ)ρ11)K_0\rho K_0^\dagger+K_1\rho K_1^\dagger=\begin{pmatrix}\rho_{00}+\gamma\rho_{11}&\sqrt{1-\gamma}\,\rho_{01}\\\sqrt{1-\gamma}\,\rho_{10}&(1-\gamma)\rho_{11}\end{pmatrix}

    Multiply out. K1=γ∣0⟩ ⁣⟨1∣K_1=\sqrt\gamma\ketbra01 moves population from ∣1⟩\ket1 to ∣0⟩\ket0; K0K_0 damps the coherences.

  2. z′=ρ00′−ρ11′=z+2γρ11=z+γ(1−z)=γ+(1−γ)zz'=\rho'_{00}-\rho'_{11}=z+2\gamma\rho_{11}=z+\gamma(1-z)=\gamma+(1-\gamma)z

    Using ρ11=1−z2\rho_{11}=\tfrac{1-z}{2}.

  3. x′+iy′=2ρ10′=1−γ (x+iy)x'+iy'=2\rho'_{10}=\sqrt{1-\gamma}\,(x+iy)

    The coherences shrink by 1−γ\sqrt{1-\gamma}. With γ=1−e−t/T1\gamma=1-e^{-t/T_1} this is T1T_1 decay, and the fixed point is ∣0⟩\ket0.

Check your understanding

Which of these maps on a qubit is not a valid quantum channel?

  1. ρ↦I/2\rho\mapsto\id/2 (replace any input by the maximally mixed state)
  2. ρ↦∣0⟩ ⁣⟨0∣\rho\mapsto\dyad0 (reset to ∣0⟩\ket0)
  3. ρ↦ρT\rho\mapsto\rho^{\mathsf T} (transpose in the computational basis)
  4. ρ↦12ρ+12ZρZ\rho\mapsto\tfrac12\rho+\tfrac12Z\rho Z (complete dephasing)
Show the answer

C. ρ↦ρT\rho\mapsto\rho^{\mathsf T} (transpose in the computational basis)

The transpose maps every density matrix to a density matrix, so it is positive, but it is not completely positive: applied to one half of ∣Φ+⟩\ket{\Phi^+} it produces an operator with eigenvalue −12-\tfrac12. A physical process must stay valid when it acts on part of an entangled system.

The Holevo bound and channel capacities

The quantity χ\chi is the Holevo information of the ensemble. Return to the {∣0⟩,∣+⟩}\{\ket0,\ket+\} source: its states are pure, so χ=S(ρ)≈0.60\chi=S(\rho)\approx0.60 bits. The best single-copy measurement does even worse: measuring in the basis symmetric about the two states errs with probability sin⁡2π8≈0.146\sin^2\frac\pi8\approx0.146, giving 1−h(0.146)≈0.401-h(0.146)\approx0.40 bits, which for two equiprobable pure states is known to be optimal. The maximum over measurements, the accessible information, can be strictly below χ\chi.

Superdense coding sends 2 bits per transmitted qubit only because the receiver already holds the other half of a Bell pair: the Holevo bound then applies to the two-qubit system, allowing 2 bits.

CapacityTaskFormula (key theorem)Erasure channel, erasure prob. ε\varepsilon
CC, classicalSend bits through N\mathcal NRegularized Holevo information (Holevo–Schumacher–Westmoreland)1−ε1-\varepsilon
QQ, quantumSend qubits (or create entanglement)Regularized coherent information (Lloyd–Shor–Devetak)max⁡(0, 1−2ε)\max(0,\,1-2\varepsilon)
CEC_E, entanglement-assistedSend bits with unlimited shared entanglementMax mutual information I(R:B)I(R{:}B) (Bennett–Shor–Smolin–Thapliyal)2(1−ε)2(1-\varepsilon)
The erasure channel delivers the input intact with probability 1−ε1-\varepsilon and otherwise a flag "erased" (which Bob can see). Note Q=0Q=0 for ε≥12\varepsilon\ge\tfrac12: otherwise the environment, which receives the state at least as often as Bob, could decode too, and two parties would end up with the same unknown state, contradicting no-cloning.

Key takeaways

  • Von Neumann entropy S(ρ)=−Tr⁡ρlog⁡2ρS(\rho)=-\Tr\rho\log_2\rho is the Shannon entropy of the spectrum and the optimal rate of quantum data compression (Schumacher).
  • Quantum conditional entropy can be negative, S(A∣B)=−1S(A|B)=-1 for a Bell pair, which certifies entanglement; strong subadditivity underlies almost every theorem.
  • Channels are CPTP maps, N(ρ)=∑kKkρKk†\mathcal N(\rho)=\sum_kK_k\rho K_k^\dagger with ∑kKk†Kk=I\sum_kK_k^\dagger K_k=\id, equivalently a unitary on system plus environment followed by a partial trace.
  • Holevo bound: I(X:Y)≤χ=S(ρ)−∑xpxS(ρx)≤log⁡2dI(X{:}Y)\le\chi=S(\rho)-\sum_xp_xS(\rho_x)\le\log_2d, so nn qubits carry at most nn bits.
  • A quantum channel has several capacities (CC, QQ, CEC_E); for the erasure channel they are 1−ε1-\varepsilon, max⁡(0,1−2ε)\max(0,1-2\varepsilon) and 2(1−ε)2(1-\varepsilon).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

For the Bell state ∣Φ+⟩AB\ket{\Phi^+}_{AB}, what are S(A)S(A), S(AB)S(AB) and S(A∣B)S(A|B)?

  1. 1, 2, 11,\ 2,\ 1
  2. 0, 0, 00,\ 0,\ 0
  3. 1, 0, −11,\ 0,\ -1
  4. 1, 1, 01,\ 1,\ 0
Show the answer

C. 1, 0, −11,\ 0,\ -1

The global state is pure, so S(AB)=0S(AB)=0, while each marginal is I/2\id/2, so S(A)=S(B)=1S(A)=S(B)=1. Then S(A∣B)=0−1=−1S(A|B)=0-1=-1, impossible for classical variables.

Question 2

The depolarizing channel ρ↦(1−p)ρ+p I/2\rho\mapsto(1-p)\rho+p\,\id/2 with p=12p=\tfrac12 acts on ∣0⟩\ket0. What are the eigenvalues of the output?

  1. 12, 12\tfrac12,\ \tfrac12
  2. 34, 14\tfrac34,\ \tfrac14
  3. 1, 01,\ 0
  4. 58, 38\tfrac58,\ \tfrac38
Show the answer

B. 34, 14\tfrac34,\ \tfrac14

The Bloch vector shrinks from length 1 to 1−p=121-p=\tfrac12, so the eigenvalues are 1±1/22=34,14\tfrac{1\pm1/2}{2}=\tfrac34,\tfrac14. Directly: 12∣0⟩ ⁣⟨0∣+14I=diag⁡(34,14)\tfrac12\dyad0+\tfrac14\id=\diag(\tfrac34,\tfrac14).

Question 3

Alice encodes one of three equiprobable messages in the "trine": three pure qubit states 120°120° apart on a great circle of the Bloch sphere. How much classical information can Bob extract per qubit?

  1. log⁡23≈1.58\log_23\approx1.58 bits, one trit, with the right measurement
  2. Exactly 0, because the states are not orthogonal
  3. 2 bits, using a POVM with three outcomes
  4. At most 1 bit, by the Holevo bound
Show the answer

D. At most 1 bit, by the Holevo bound

The average state is I/2\id/2, so χ=S(I/2)=1\chi=S(\id/2)=1 bit, and no measurement can beat it. The optimal measurement actually extracts only log⁡232≈0.585\log_2\tfrac32\approx0.585 bits.

Question 4

What state does repeated amplitude damping drive any qubit toward?

  1. ∣0⟩\ket0
  2. The maximally mixed state I/2\id/2
  3. ∣1⟩\ket1
  4. It leaves the input unchanged up to a phase
Show the answer

A. ∣0⟩\ket0

Under z↦γ+(1−γ)zz\mapsto\gamma+(1-\gamma)z the fixed point is z=1z=1, and the coherences shrink by 1−γ\sqrt{1-\gamma} each time. Every state decays to ∣0⟩\ket0, the ground state: this is energy relaxation, T1T_1.

Question 5

For a quantum erasure channel with erasure probability ε=0.6\varepsilon=0.6, which statement is correct?

  1. Q=0.4Q=0.4 and C=0.4C=0.4
  2. C=0C=0, because most transmissions are erased
  3. Q=0Q=0, yet C=0.4C=0.4 and CE=0.8C_E=0.8
  4. Q=C=CE=0.4Q=C=C_E=0.4
Show the answer

C. Q=0Q=0, yet C=0.4C=0.4 and CE=0.8C_E=0.8

For ε≥12\varepsilon\ge\tfrac12 the quantum capacity vanishes (no-cloning), but classical bits still get through at 1−ε=0.41-\varepsilon=0.4, and shared entanglement doubles that to 2(1−ε)=0.82(1-\varepsilon)=0.8.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, Chapters 8, 11 and 12 (Cambridge, 10th anniv. ed., 2010).
  • M. M. Wilde, Quantum Information Theory, 2nd ed. (Cambridge, 2017).
  • J. Preskill, Lecture Notes for Physics 219: Quantum Computation, chapter on quantum Shannon theory (Caltech).
  • C. E. Shannon, "A mathematical theory of communication", Bell System Technical Journal 27, 379 and 623 (1948).