Lec1 信息与信息熵

阅读信息

615 字  3 分钟  本页总访问量 加载中...

引入

量子物理表明，世界是量子化的。是否能用量子信息表示量子化的世界？或者，若将世界视为牛顿力学下的经典世界，能否用量子信息表示？

经典信息	量子信息
只能取0或1	可取0和1的任何叠加态

量子系统有并行性，即能同时处理多个计算路径

量子计算机指直接利用量子的特性进行计算的计算机。量子态本质上是状态的叠加，噪声高，容易出错。

量子信息

信息的擦除是不可逆的，必然向环境中放热。

信息熵是关于某个事件出现概率的连续函数。对两个独立时间，希望其信息熵满足相加，即 \(I(p_x,p_y)=I(p_x)+I(p_y)\)。可推导出 \(I(p_x)=-\log_2(p_x)I(1/2)\)。因此，事件 \(x\) 的信息熵为 \(-\log_2(P_x)\)，事件发生概率越小，信息熵（代表的信息量）越大。

某种事件有不同的可能的状态，其信息熵为不同可能值的信息山的平均值：

\[ H=\langle I(p_i) \rangle \sim -\sum_{i=1}^n p_i\log_2 p_i \]

信息擦除指擦除到的状态概率为1，其余状态概率为0。擦除后信息熵变为0，即为熵减过程，不可逆。

信息熵的应用：衡量数据压缩的程度

Remarks

\[ S=k_B \ln 2 \]

\[ Q=T \Delta S \]

Remarks

一个独立同分布随机序列的“典型序列”数量大约是 \(2^{nH(X)}\)，因此最少需要 \(nH(X)\) 比特来编码。

---

如果有长度为 \(n\) 的序列：

\[ X_1, X_2, \dots, X_n \]

假设它们独立同分布，则联合概率等于乘积：

\[ P(X_1, \dots, X_n) = \prod_i P(X_i) \]

如果某个值 \(x\) 在序列中出现了 \(nP(X=x)\) 次，则那么联合概率近似为：

\[ \prod_x P(X=x)^{nP(X=x)} \]

代入信息量定义：

\[ -\log_2 P(X_1,\dots,X_n)= -n \sum_x P(X=x)\log_2 P(X=x) \]

而香农熵（Shannon Entropy）定义为：

\[ H(X)=-\sum_x P(X=x)\log_2 P(X=x) \]

它表示平均每个符号需要多少 bit

于是：

\[ P(X_1,\dots,X_n) \approx 2^{-nH(X)} \]

这意味着，如果一个典型序列概率是 \(2^{-nH(X)}\)，那能存在的典型序列个数最多约为 \(2^{nH(X)}\)（因为所有概率加起来 ≤ 1）

压缩含义：如果最多只有 \(2^{nH(X)}\) 种“常见序列”，要区分它们至少需要 \(\log_2(2^{nH(X)}) = nH(X)\) bit。即，熵是可压缩性的极限。

计算复杂性

随机性是否真的能提升计算能力？

BPP (Bounded-error Probabilistic Polynomial time，有界错误概率的随机多项式时间)：允许随机决策，运行时间为多项式，错误概率小于某个常数。显然 P \(\subset\) BPP，但不确定是否 P=BPP

BQP（Bounded-error Quantum Polynomial time，有界错误概率的量子多项式时间）：在量子计算模型上运行，运行时间为多项式，错误概率小于某个常数。显然 P \(\subset\) BPP \(\subset\) BQP，但不确定是否 BPP=BQP