#李铁夫老师前沿科技·量子计算：笔记07#

主题：07 | 算法：如何让量子计算机做最擅长的事？

目的：前沿科技、同学同进步

前讲内容：怎样去评估一个量子计算机的好坏，最核心的指标是量子比特的数量。

此讲内容：算法和量子计算的关系。

（2019年10月23日的Nature杂志文章里描述的谷歌的量子计算机是53量子比特）

一、算力=物理系统+算法

【重点】量子计算机的算力由物理系统和算法以及两者之间的匹配度决定。研发算法的难度与研发量子计算机硬件难度相当。（“算力=物理系统+算法”）

【量子算法】

1. 1994年，破解密码的量子算法— 肖尔算法出现。数学家彼得·肖尔（Peter Shor）的这个算法在数学上严格证明了，用量子计算机破解密码的速度是能达到指数级别的提高。肖尔算法在破解RSA协议时表现得特别优秀。

2. 1996年，计算机科学家格罗弗（Lov Grover）提出的在无序的数据库中进行搜索的量子算法，能带来搜索速度的提升，但只能达到平方根的程度，比指数级加速差很多。

- 无序的数据库中进行搜索：相当于在一个万人的演唱会现场找到和自己生日相同的人。

- 一个10000年的运算，平方根级的加速，完成需要155小时；指数加速只需要38秒。

4. 比特币挖矿的基础即是从无序数据中找到数据，这个算法是非常消耗算力的。格罗弗算法可以加速这个过程，但不能带来指数级提升，所以即便是量子计算机现在已经开始实用了，比特币挖矿的基础也并不会被破坏。

【总结】优秀的量子算法不易产生。从1994年到现在，除了肖尔算法之外，没有第二个算法如肖尔算法一样有指数级别的速度提升。

二、量子算法需要充分发挥量子计算机的并行性

【重点】算法必须能够和物理系统匹配才能提升算力。

1. 量子计算的物理系统具有量子特性，即用这个物理系统构建起来的比特是会具有量子特性的：量子叠加性、量子纠缠，叠加状态的并行演化。

2. 量子计算比经典计算运算更快，归根到底都是它为并行处理信息提供了好的解决方案。

3. 一个算法没能发挥并行处理信息这个优势，即便把这个算法强行运行在量子计算机上，也不会带来运算速度的大幅提升，即匹配的程度不高就无法把物理系统的所有能力都发挥出来。

肖尔算法（指数级加速：匹配度高）

格罗弗算法（平方根级加速：匹配度低）

【密码破解例】

现在的密码系统之所以安全，是因为它用到了一个特性，那就是“大数分解的不对等性”。

问题：整数527是哪两个质数相乘吗？

质数：只能被1和自己整除的数

结论：快速人工分解这个数很难。但给出17x31，就能算出来这是527。即从527推出17乘以31很难，反过来却很容易，这就是不对等性。

想要破解密码，就相当于知道了一个数，要猜出来它等于哪两个质数相乘。

- 1024位RSA加密，用现在最好的经典计算机和算法，需要大概1年才能破解。

- 2048位RSA加密，用经典计算机破解就需要10亿年。

如果用量子计算机，也没有这么简单。量子计算提高运算速度，主要是通过增加了并行性做到的，但并不是所有的问题都可以被并行解决的。

例）计算“1000+10+10+10”

- 可以把这个问题拆分成两个小问题

1）前面两个数相加1000+10

2）后面两个数相加10+10

- 这两个小问题是可以同时计算的，这样就可以节省时间。

- 这是4个数的加法。如果是40000个数相加，同样拆分和并行计算，会大大提升计算速度的。

例）计算1000÷10÷10÷10，

- 不能拆分成“1000÷10”、“10÷10”，然后再合并，计算结果是100，不对。

- 对于连续除法不能并行计算，只能按部就班一步步来，最后答案等于1。

- 这个除法运算，如果经过数学处理的话也可以并行解决。但并不是所有的问题都能简单地找到并行处理的方法，这就是开发量子算法困难的地方。

4. 破解密码例中，如果老老实实去分解2048位大数，没有办法发挥出量子计算的优势。

5. 肖尔算法有效的原因：不是去直接去做分解2，而是利用了数学规律。（什么规律？）通过数学规律可以把分解大数问题转化成了另外一个等价的问题。（什么等价问题？）这个等价的问题，它的核心环节可以充分利用量子计算机的并行计算优势。这个破解密码的问题才能被量子计算机轻松解决掉。（需要延展阅读）

三、经典计算机和量子计算机搭配使用会更有效

1. 算法与物理系统匹配时才能发挥出最大的算力。

不是所有问题在未来都要用量子计算机来解决，有些问题用经典计算机和经典算法已经能处理得非常好了。

等到量子计算机真的开始实用后，很可能的景象是：经典计算机和量子计算机搭配使用，各自解决自己擅长的问题。

2. 量子算法艰难但科学家仍有信心

经典计算机里的快速排序算法：是公认最快的算法，是在第一台电子计算机被发明后的十几年之后才被发现的。

排序算法就是把没有顺序的数字，按照从小到大或是从大到小的顺序排列起来。

而肖尔是在量子计算机产生之前提出的可行的量子算法。等到量子计算机真正实现之后，科学家可以真正地将算法运行在量子计算机上时，量子算法将会大爆发。

延展阅读：

1. 维基百科：肖尔算法

https://en.m.wikipedia.org/wiki/Shor%27s_algorithm

2. 维基百科：Grover algorithm

https://en.m.wikipedia.org/wiki/Grover%27s_algorithm

3. 油管视频：

量子计算机如何破密：肖尔算法解释

https://youtu.be/lvTqbM5Dq4Q

大数分解314191的过程

https://youtu.be/FRZQ-efABeQ

2019年11月3日

丽娟 记