#李鐵夫老師前沿科技·量子計算：筆記07#
主題：07 | 算法：如何讓量子計算機(jī)做最擅長的事？
目的：前沿科技、同學(xué)同進(jìn)步
前講內(nèi)容：怎樣去評估一個量子計算機(jī)的好壞，最核心的指標(biāo)是量子比特的數(shù)量。
此講內(nèi)容：算法和量子計算的關(guān)系。
（2019年10月23日的Nature雜志文章里描述的谷歌的量子計算機(jī)是53量子比特）
一、算力=物理系統(tǒng)+算法
【重點(diǎn)】量子計算機(jī)的算力由物理系統(tǒng)和算法以及兩者之間的匹配度決定。研發(fā)算法的難度與研發(fā)量子計算機(jī)硬件難度相當(dāng)。（“算力=物理系統(tǒng)+算法”）
【量子算法】
1. 1994年，破解密碼的量子算法— 肖爾算法出現(xiàn)。數(shù)學(xué)家彼得·肖爾（Peter Shor）的這個算法在數(shù)學(xué)上嚴(yán)格證明了，用量子計算機(jī)破解密碼的速度是能達(dá)到指數(shù)級別的提高。肖爾算法在破解RSA協(xié)議時表現(xiàn)得特別優(yōu)秀。
2. 1996年，計算機(jī)科學(xué)家格羅弗（Lov Grover）提出的在無序的數(shù)據(jù)庫中進(jìn)行搜索的量子算法，能帶來搜索速度的提升，但只能達(dá)到平方根的程度，比指數(shù)級加速差很多。
- 無序的數(shù)據(jù)庫中進(jìn)行搜索：相當(dāng)于在一個萬人的演唱會現(xiàn)場找到和自己生日相同的人。
- 一個10000年的運(yùn)算，平方根級的加速，完成需要155小時；指數(shù)加速只需要38秒。
4. 比特幣挖礦的基礎(chǔ)即是從無序數(shù)據(jù)中找到數(shù)據(jù)，這個算法是非常消耗算力的。格羅弗算法可以加速這個過程，但不能帶來指數(shù)級提升，所以即便是量子計算機(jī)現(xiàn)在已經(jīng)開始實(shí)用了，比特幣挖礦的基礎(chǔ)也并不會被破壞。
【總結(jié)】優(yōu)秀的量子算法不易產(chǎn)生。從1994年到現(xiàn)在，除了肖爾算法之外，沒有第二個算法如肖爾算法一樣有指數(shù)級別的速度提升。
二、量子算法需要充分發(fā)揮量子計算機(jī)的并行性
【重點(diǎn)】算法必須能夠和物理系統(tǒng)匹配才能提升算力。
1. 量子計算的物理系統(tǒng)具有量子特性，即用這個物理系統(tǒng)構(gòu)建起來的比特是會具有量子特性的：量子疊加性、量子糾纏，疊加狀態(tài)的并行演化。
2. 量子計算比經(jīng)典計算運(yùn)算更快，歸根到底都是它為并行處理信息提供了好的解決方案。
3. 一個算法沒能發(fā)揮并行處理信息這個優(yōu)勢，即便把這個算法強(qiáng)行運(yùn)行在量子計算機(jī)上，也不會帶來運(yùn)算速度的大幅提升，即匹配的程度不高就無法把物理系統(tǒng)的所有能力都發(fā)揮出來。
肖爾算法（指數(shù)級加速：匹配度高）
格羅弗算法（平方根級加速：匹配度低）
【密碼破解例】
現(xiàn)在的密碼系統(tǒng)之所以安全，是因?yàn)樗玫搅艘粋€特性，那就是“大數(shù)分解的不對等性”。
問題：整數(shù)527是哪兩個質(zhì)數(shù)相乘嗎？
質(zhì)數(shù)：只能被1和自己整除的數(shù)
結(jié)論：快速人工分解這個數(shù)很難。但給出17x31，就能算出來這是527。即從527推出17乘以31很難，反過來卻很容易，這就是不對等性。
想要破解密碼，就相當(dāng)于知道了一個數(shù)，要猜出來它等于哪兩個質(zhì)數(shù)相乘。
- 1024位RSA加密，用現(xiàn)在最好的經(jīng)典計算機(jī)和算法，需要大概1年才能破解。
- 2048位RSA加密，用經(jīng)典計算機(jī)破解就需要10億年。
如果用量子計算機(jī)，也沒有這么簡單。量子計算提高運(yùn)算速度，主要是通過增加了并行性做到的，但并不是所有的問題都可以被并行解決的。
例）計算“1000+10+10+10”
- 可以把這個問題拆分成兩個小問題
1）前面兩個數(shù)相加1000+10
2）后面兩個數(shù)相加10+10
- 這兩個小問題是可以同時計算的，這樣就可以節(jié)省時間。
- 這是4個數(shù)的加法。如果是40000個數(shù)相加，同樣拆分和并行計算，會大大提升計算速度的。
例）計算1000÷10÷10÷10，
- 不能拆分成“1000÷10”、“10÷10”，然后再合并，計算結(jié)果是100，不對。
- 對于連續(xù)除法不能并行計算，只能按部就班一步步來，最后答案等于1。
- 這個除法運(yùn)算，如果經(jīng)過數(shù)學(xué)處理的話也可以并行解決。但并不是所有的問題都能簡單地找到并行處理的方法，這就是開發(fā)量子算法困難的地方。
4. 破解密碼例中，如果老老實(shí)實(shí)去分解2048位大數(shù)，沒有辦法發(fā)揮出量子計算的優(yōu)勢。
5. 肖爾算法有效的原因：不是去直接去做分解2，而是利用了數(shù)學(xué)規(guī)律。（什么規(guī)律？）通過數(shù)學(xué)規(guī)律可以把分解大數(shù)問題轉(zhuǎn)化成了另外一個等價的問題。（什么等價問題？）這個等價的問題，它的核心環(huán)節(jié)可以充分利用量子計算機(jī)的并行計算優(yōu)勢。這個破解密碼的問題才能被量子計算機(jī)輕松解決掉。（需要延展閱讀）
三、經(jīng)典計算機(jī)和量子計算機(jī)搭配使用會更有效
1. 算法與物理系統(tǒng)匹配時才能發(fā)揮出最大的算力。
不是所有問題在未來都要用量子計算機(jī)來解決，有些問題用經(jīng)典計算機(jī)和經(jīng)典算法已經(jīng)能處理得非常好了。
等到量子計算機(jī)真的開始實(shí)用后，很可能的景象是：經(jīng)典計算機(jī)和量子計算機(jī)搭配使用，各自解決自己擅長的問題。
2. 量子算法艱難但科學(xué)家仍有信心
經(jīng)典計算機(jī)里的快速排序算法：是公認(rèn)最快的算法，是在第一臺電子計算機(jī)被發(fā)明后的十幾年之后才被發(fā)現(xiàn)的。
排序算法就是把沒有順序的數(shù)字，按照從小到大或是從大到小的順序排列起來。
而肖爾是在量子計算機(jī)產(chǎn)生之前提出的可行的量子算法。等到量子計算機(jī)真正實(shí)現(xiàn)之后，科學(xué)家可以真正地將算法運(yùn)行在量子計算機(jī)上時，量子算法將會大爆發(fā)。
延展閱讀：
1. 維基百科：肖爾算法
https://en.m.wikipedia.org/wiki/Shor%27s_algorithm
2. 維基百科：Grover algorithm
https://en.m.wikipedia.org/wiki/Grover%27s_algorithm
3. 油管視頻：
量子計算機(jī)如何破密：肖爾算法解釋
https://youtu.be/lvTqbM5Dq4Q
大數(shù)分解314191的過程
https://youtu.be/FRZQ-efABeQ
2019年11月3日
麗娟 記
