量子信息导论内容很杂，包括了计算科学、信息论、密码学的一些知识；

计算理论的发展

19世纪及以前

算盘、计算尺的天下，做理论的物理学家申请经费基本是用来外出访问，剩下的用来买草稿纸和笔（笑）；

图灵机模型

1936年，Alan Turing提出了著名的图灵机模型，一个标准的图灵机，包含一个无限长的可读写的计算带、读写头和一个指令集团，每种图灵机可以处理一种类型的问题（指令集团就对应算法）；图灵机模型的伟大之处在于从无到有提出了一个计算模型，对计算机的产生起到了指导作用；更神奇的是，之后Turing & Church还联合证明了一个命题：存在一种Universal的图灵机，可以模拟其他任意图灵机，这是通用计算机的理论基础，后来的冯·诺依曼便是使图灵机变得可实现化；

这里有个小插曲，计算机被提出以后，1943年，IBM的CEO Thomas J.Watson曾经大胆预言——全世界只需要五台计算机就够了；emmm……这告诉我们不要把科学家的预言太当回事……

晶体管发明

1947年，世界上第一个晶体管在贝尔实验室诞生，使得电子器件的小型化成为可能；此后半导体产业蓬勃发展，Intel创始人之一的G. Morre也提出了著名的摩尔定律——当价格不变时，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍；当然，我们知道，这种毕竟是工业实践总结出的规律，实际上会遭遇一些困难；

两个困难

  • 热耗问题：随着计算性能的提升，计算芯片每秒执行的门操作数也不断增加，因此发热量也随之增加，如果散热能力小于发热，那么积累的热量便会损坏芯片，因此要想办法减少芯片的发热；Landauer解决了这个问题，他发现，计算时产生的热量来源于擦除比特的操作，每擦除单个比特，至少会释放出$k_BT\ln2$的热量，并且他还提出了可逆计算模型，原则上可以使得计算不产生热量；此时人们距离量子计算已经非常近了。
  • 量子效应：即使到现在，人们也很难想想能够自由地操纵亚原子结构，因此集成电路的密度不可能无限地高，摩尔定律也总有一天会失效；

量子多体系统的演化

精确计算多体系量子系统，用经典计算机是做不到的。

量子系统的维度不是线性加法的，对于$N$个量子系统，分别具有$n_1,n_2,...,n_N$的Hilbert空间维度，将它们合并成一个多体系统，总的Hilbert维度是$\Pi n_i$；以现今人类的计算能力，大约只能计算50个二维量子构成的系统；

Deutsch-Jolla算法

1985年，Deutsch构造了一种情形，使得N步可以求解的经典问题可以使用量子计算一步得到解答，这表明了在一些经典问题上，量子计算相比已有的算法可能会复杂度上具有优势；

Shor算法

一个非常重要的研究成果，Shor提出了一种使用量子计算分解质因数的方法，其复杂度比已知的所有算法都要低，现实地证明了量子计算在特殊问题上相对经典计算的巨大优势，并且严重威胁到了RSA加密算法的安全性，因为RSA算法的安全性是建立在无法有效地对大整数进行质因数分解上的，而这个命题对于经典计算机为真；

量子退相干

1995年，Urnuh详细研究了量子退相干相关的问题，所谓退相干，指的是由于环境的影响，量子态从纯态变成混态，而对纯态操作是量子计算的前提条件，否则量子计算并不能体现出相对于经典计算的优越性（为什么？期待后续讲解）；Urnuh发现，随着体系的增大，退相干的速率是指数增大的，这个和之前多体量子体系的Hilbert空间维数增长是相一致的，但这就限制了量子计算的算力提升——提高算力需要多体量子体系，然而多体量子体系又具有高的退相干速率；但是你看，传统计算也伴随着不断的错误（比特翻转等），但是经典计算机也不会因此而轻易崩溃，这是因为有纠错码的存在，使得计算机能够在一定程度上纠正部分错误，于是这时候Shor又跳出来了，他提出了第一个量子纠错码算法，可以采用9个量子比特的编码来纠正一个量子比特可能出现的随机错误；从那时一直到现在，人们几乎参考了经典计算机中所有的纠错算法，但仍然没有找到一个足够高效的纠错码算法，这也是目前量子计算的限制来源之一；

如今的量子计算的发展重点

  • 1、量子计算与量子模拟的物理实现：你们物理学家把量子计算吹得很好，很厉害，那能不能做出来给我看看?
  • 2、量子计算相关软件：从Shor算法被提出，人们在量子算法上几乎没有什么大的突破（虽然最近好像有人证明了存在量子算法能快于全部的经典算法）；请注意，虽然Shor算法已经是快于已有的任何算法，但我们并不知道存不存在比Shor算法更有效率的经典算法来实现大数的质因数分解；另外，从量子纠错码被提出之后，发展出了容错量子计算，在每一步置信度高于某个阈值的条件下，可以搭配量子纠错码边计算边纠错，并保证最后得到正确的结果；
  • 3、量子信息和物理的联系相关研究；（任意子？）

信息论

经典信息论

由香农提出，建立在香农三大定理之上（实际上这一部分根本没怎么讲，只提到了第一定理已经得到了量子情形下的对应，二还没有，因为量子信道没有线性加性，三根本没提；总之先搬运过来）：

  1. 可变长无失真信源编码定理

    • 设离散无记忆信源X包含N个符号$x_1,x_2,…,x_i,..,x_N$，信源发出$K$重符号序列，则此信源可发出$N^k$个不同的符号序列消息，其中第$j$个符号序列消息的出现概率为$P_{K_j}$，其信源编码后所得的二进制代码组长度为$B_j$，代码组的平均长度$B$为：

    $$B=P_{K_1}B_1+P_{K_2}B_2+…+P_{K_{N^k}}B_{N^k}$$

    • 当$K$趋于无限大时，$B$和信息量$H(X)$之间的关系为$\frac{B}{k}=H(X)$ when $K\to\infty$

  2. 有噪信道编码定理

    • 当信道的信息传输率不超过信道容量时，采用合适的信道编码方法可以实现任意高的传输可靠性，但若信息传输率超过了信道容量，就不可能实现可靠的传输。
    • 设某信道有$r$个输入符号，$s$个输出符号，信道容量为$C$，当信道的信息传输率$R<C$，码长$N$足够长时，总可以在输入的集合中（含有$r^N$个长度为$N$的码符号序列），找到$M$（$M\leq 2^{N(C-\epsilon)}$，a为任意小的正数）个码字，分别代表$M$个等可能性的消息，组成一个码以及相应的译码规则,使信道输出端的最小平均错误译码概率$P_{min}$达到任意小。

    $$C=B\log_2 (1+\frac{S}{N})$$

  3. 保失真度准则下的有失真信源编码定理

    • 只要码长足够长，总可以找到一种信源编码，使编码后的信息传输率略大于率失真函数，而码的平均失真度不大于给定的允许失真度，即$D'\leq D$;
    • 设$R(D)$为一离散无记忆信源的信息率失真函数，并且选定有限的失真函数，对于任意允许平均失真度$D\geq 0$，和任意小的$a>0$，以及任意足够长的码长$N$，则一定存在一种信源编码$W$，其码字个数为$M\leq e^{N[R(D)+a]}$，而编码后码的平均失真度$D'(W)\leq D+a$。

密码学

我们讨论的密码学，主要是公钥体系和私钥体系；

公钥

  • 安全性依托于数学问题的难解性；

私钥

  • 被证明存在完全安全的通讯方式，但需要有一种安全的手段向通讯双方分发大量的高质量随机数；而量子通讯，解决了随机密钥的分发问题；
Last modification：May 17, 2021
© Allow specification reprint
(๑´ڡ`๑)