Developer_HZH

量子信息导论 Chapter 0
量子信息导论内容很杂,包括了计算科学、信息论、密码学的一些知识;
扫描右侧二维码阅读全文
10
2018/09

量子信息导论 Chapter 0

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


计算理论的发展

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:March 5th, 2019 at 11:38 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment