Quantum Information and the Large Deviations / Sanov / Cramér¶
Job: develop the quantum information (von Neumann / Holevo / quantum capacity), the large deviations (Sanov / Cramér / Gärtner–Ellis), and the hypothesis testing (Chernoff–Stein / Chernoff–Hoeffding) — with the Sanov / Cramér as the worked example.
Core¶
The quantum information¶
| von Neumann / quantum MI / Holevo | Description |
|---|---|
| von Neumann entropy \(S(\rho)\) | \(S(\rho)=-\mathrm{Tr}(\rho\log\rho)\) (the quantum entropy, the NCG / operator algebras) |
| Quantum MI | \(I(A;B)=S(A)+S(B)-S(AB)\) (the quantum, the entanglement) |
| Holevo bound | \(I(X;B)\le S(\rho_B)-\sum p_x S(\rho_x)\) (the Holevo, the classical-quantum) |
The quantum channel capacity¶
| Quantum capacity / private / entanglement-assisted | Description |
|---|---|
| Quantum capacity \(Q\) | \(Q=\lim\frac1n\max I_{\mathrm{coh}}\) (the coherent information, the Lloyd–Shor–Devetak) |
| Private capacity \(P\) | the Devetak (the private, the \(P\) the secret key) |
| Entanglement-assisted \(C_E\) | the Bennett–Shor–Smolin–Thapliyal (the entanglement the assistance) |
The large deviations / Sanov / Cramér¶
| Sanov / Cramér / Gärtner–Ellis | Description |
|---|---|
| Sanov | the empirical measure \(\frac1n\sum\delta_{X_i}\to\mu\) the \(P(\hat\mu\approx\nu)\sim e^{-nD_{\mathrm{KL}}(\nu\|\mu)}\) (the Sanov) |
| Cramér | the \(\frac1n\sum X_i\) the \(P(\bar X\approx x)\sim e^{-nI(x)}\) the \(I(x)=\sup_\lambda(\lambda x-\log\mathbb{E}e^{\lambda X})\) (the Legendre) |
| Gärtner–Ellis | the non-i.i.d. the Gärtner–Ellis (the rate the Legendre–Fenchel, the measure theory / probability) |
The hypothesis testing and the Chernoff–Stein¶
| Chernoff–Stein / Chernoff–Hoeffding / ergodic | Description |
|---|---|
| Chernoff–Stein | the best type-II error exponent \(D_{\mathrm{KL}}(p\|q)\) (the foundations recalled) |
| Chernoff–Hoeffding | the Bayesian \(\min_{0\le s\le1}-\log\mathbb{E}_p^s\mathbb{E}_q^{1-s}\) (the Chernoff, the symmetric) |
| Large deviations & ergodic | the Sanov the empirical, the ergodic the Birkhoff (the ergodic / Ornstein the entropy) |
See it¶
Sanov \(P(\hat\mu\approx\nu)\sim e^{-nD_{\mathrm{KL}}(\nu\|\mu)}\) and Cramér \(P(\bar X\approx x)\sim e^{-nI(x)}\). The Sanov: the empirical measure \(\hat\mu_n=\frac1n\sum\delta_{X_i}\), the \(P(\hat\mu_n\approx\nu)\sim e^{-nD_{\mathrm{KL}}(\nu\|\mu)}\) (the rate the KL, the Sanov, the measure theory / probability). The Cramér: the \(\bar X_n=\frac1n\sum X_i\), the \(P(\bar X_n\approx x)\sim e^{-nI(x)}\) the \(I(x)=\sup_\lambda(\lambda x-\log M(\lambda))\) the Legendre (the \(M(\lambda)=\mathbb{E}e^{\lambda X}\) the MGF, the Cramér). The key point: the Sanov the empirical measure the KL rate, the Cramér the sample mean the Legendre rate — the large deviations the information-theoretic.
Check¶
Show that the Sanov rate is \(D_{\mathrm{KL}}(\nu\|\mu)\) and the Cramér rate is the Legendre \(I(x)=\sup_\lambda(\lambda x-\log M(\lambda))\).
The Sanov: the empirical \(\hat\mu_n\), the \(P(\hat\mu_n\approx\nu)\) the method of types (the \(|\mathrm{type}|\approx e^{nH(\nu)}\), the \(P(\mathrm{type}\approx\nu)\approx e^{-nD_{\mathrm{KL}}(\nu\|\mu)}\) the type the probability, the Sanov). The Cramér: the \(\bar X_n\), the \(P(\bar X_n\approx x)\) the Chernoff the \(\inf_{t>0}e^{-ntx}M(t)^n=e^{-n\sup_\lambda(\lambda x-\log M(\lambda))}\) (the Legendre, the \(M(\lambda)=\mathbb{E}e^{\lambda X}\) the MGF, the Cramér). The Sanov the empirical the KL, the Cramér the mean the Legendre.
Explain the Holevo bound and the quantum capacity.
The Holevo: the \(I(X;B)\le S(\rho_B)-\sum p_x S(\rho_x)=\chi\) (the Holevo information \(\chi\), the classical info the quantum). The quantum capacity: the \(Q=\lim\frac1n\max I_{\mathrm{coh}}\) (the coherent information \(I_{\mathrm{coh}}=S(B)-S(E)\), the Lloyd–Shor–Devetak, the NCG / operator algebras). The \(Q\) the quantum, the \(P\) the private, the \(C_E\) the entanglement-assisted (the Bennett–Shor–Smolin–Thapliyal). The Holevo the classical-quantum, the \(Q\) the quantum the LSD.
Pitfalls¶
- The von Neumann the quantum (the \(S(\rho)=-\mathrm{Tr}(\rho\log\rho)\), the NCG) — the quantum the entropy, the Holevo the classical-quantum.
- The quantum capacity the LSD (the Lloyd–Shor–Devetak, the \(I_{\mathrm{coh}}\), the entanglement) — the \(Q\) the quantum, the \(P\) the private, the \(C_E\) the entanglement.
- The Sanov the empirical (the \(P(\hat\mu\approx\nu)\sim e^{-nD_{\mathrm{KL}}}\), the method of types) — the Sanov the KL, the empirical the measure.
- The Cramér the Legendre (the \(I(x)=\sup_\lambda(\lambda x-\log M)\), the MGF) — the Cramér the Legendre, the MGF the rate.
- The Chernoff–Stein (the \(D_{\mathrm{KL}}(p\|q)\) the type-II exponent, the Chernoff the symmetric) — the Chernoff–Stein the KL, the Chernoff–Hoeffding the Bayesian.
Refs¶
- von Neumann, Mathematical Foundations of Quantum Mechanics; the \(S(\rho)\); Holevo, "Bounds for the amount of information" (1973)
- Lloyd–Shor–Devetak, the quantum capacity; Bennett–Shor–Smolin–Thapliyal, the entanglement-assisted
- Sanov, "On the probability of large deviations" (1957); Cramér (1938); Gärtner–Ellis (1977–1984)
- Chernoff (1952); Hoeffding (1965); the ergodic / Ornstein the entropy
Next¶
IT index · Foundations · Network Information · Rate-Distortion & Lossy · Finite-Blocklength & Dispersion · Ergodic / Ornstein · Measure theory / probability · NCG / operator algebras