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