L1
Information, Entropy, and Computational Complexity¶
Shannon Entropy¶
the Shannon entropy of event \(x\) is \(-\log_{2}{P_x}\)
推导
\[
\begin{align*}
前提：&事件x的信息量仅依赖于其发生的概率\\
&连续性\text{:}I(p)是概率p的连续函数\\
&加性\text{:}I(p_x,p_y)
\end{align*}
\]
\[
\Rightarrow I(p_x^2)=2I(p_x)\,and\,I(p_x^s)=sI(p_x),其中s为整数
\]
下从整数推广到有理数
\[
对于p=p_x^t，有\text{：}\,I(p)=tI(p_x)
\]
\[
\Rightarrow I(p_x)=\frac{1}{t}I(p)
\]
\[
\Rightarrow I(p^{1/t})=\frac{1}{t}I(p)
\]
\[
对于有理数q=\frac{s}{t},有\text{：}
\]
\[
I(p_x^q)=I(p_x^{\frac{s}{t}})=sI(p_x^{1/t})=s(1/t)I(p_x)=qI(p_x)
\]
下从有理数推广到实数
\[
由连续性可以认为\,I(p_x^r)=rI(p_x)
\]
\[
I(p_x)=I({1/2}^{-\log_{2}{p_x}})=-\log_{2}{p_x}I(\frac 1 2)
\]
\[
因为I(\frac 1 2)为常数，我们可以认为带来实际价值的是-\log_{2}{p_x}
\]
推广到多个事件，求平均 $$ H=\langle I(p_i)\rangle=-\sum_{i=1}^{n}{p_i\log_2{p_i}} $$
理解
两件事情。
若\(p_1=\frac 1 2\,\)且\(\,p_2=\frac 1 2\)，则\(\,H=\frac 1 2+\frac 1 2=1\)
若\(p_1=0\,\)且\(\,p_2=1\)，则\(\,H=0+0=0\)
第二种情况中，事件2必然发生，即没有提供什么有价值的信息，因此认为\(\,H=0\)
应用：存储路径压缩
Computational Complexity¶
(1) P NP
(2)图灵机
(3)BPP BQP
研究量子计算机的目的：可能存在不属于BPP但属于BQP的问题，因此结合概率用量子算法可以在多项式时间内解决。
回顾历史¶
1982年：费曼提出量子计算概念
理查德·费曼（Richard Feynman）指出，传统计算机无法高效模拟量子系统，提出利用量子力学原理构建计算机的设想。
1994年：Shor算法（质因数分解，给出所有质因子）
彼得·肖尔（Peter Shor）提出量子质因数分解算法，证明量子计算机可破解RSA加密，引发密码学革命。
2018年：谷歌实现量子霸权
谷歌的Sycamore处理器在200秒内完成传统超算需1万年的任务，首次证明量子计算优势。
量子霸权
英文为Quantum supremacy，可以理解为量子计算优越性
2019年: IBM推出首台20量子比特商用量子计算机Q System One
各组织开始通过量子工程教育，为第二次量子革命着手准备。