20115
0
2020-03-17
2020-07-11
量子算法簡(jiǎn)介
量子計(jì)算近年來(lái)受到了極大關(guān)注,，根本原因在于其具有強(qiáng)大的并行性，可以在有效時(shí)間內(nèi)解決一些經(jīng)典計(jì)算機(jī)不能有效解決的問題,。例如,，Shor 算法可以在多項(xiàng)式時(shí)間內(nèi)解決大數(shù)因子分解問題,，從而對(duì)現(xiàn)代 密碼造成了極大威脅,。然而,，量子計(jì)算的并行性并非直接可以利用，而是需要根據(jù)所解決的問題經(jīng)過(guò)巧妙的算法設(shè)計(jì)才可能,。即便量子計(jì)算機(jī)研制成功,，如果沒有相應(yīng)的量子算法,，量子計(jì)算的潛能還是得不到實(shí)質(zhì)性發(fā)揮。因此,，要想利用量子計(jì)算解決實(shí)際問題,，能否設(shè)計(jì)出快速的量子算法是關(guān)鍵。不夸張的說(shuō),，量子算法的研究是推動(dòng)量子計(jì)算向前發(fā)展不可取代的力量源泉,。
本文嘗試為大眾提供一個(gè)有關(guān)量子算法的通俗性介紹，主要內(nèi)容如下：
量子計(jì)算并行性的根源
量子算法的基本框架
量子算法設(shè)計(jì)的困難性
量子算法研究簡(jiǎn)明進(jìn)程
關(guān)于量子算法的兩個(gè)疑問
總結(jié)
一,、量子計(jì)算并行性的根源
量子計(jì)算并行性的根源何在,？本文回答如下：
(1) 量子疊加帶來(lái)潛在的并行性。所謂量子疊加是指一個(gè)量子系統(tǒng)可以處于多個(gè)基態(tài)的線性組合形式,，例如一個(gè)量子比特可以處于狀態(tài)a|0>+b|1>,。由此，一次操作U可以并行作用于兩個(gè)態(tài)|0>和|1>上得到aU|0>+bU|1>,，即所謂的“一次操作同時(shí)完成多次計(jì)算”,。然而，這里在并行性前面加了定語(yǔ)“潛在的”,，即這種并行性并非直接就解決了問題,，還需要后續(xù)算法設(shè)計(jì)。正如量子計(jì)算知名學(xué)者Scott Aaronson在接受《麻省理工學(xué)院新聞》采訪時(shí)所說(shuō)“你要是光看報(bào),、讀雜志等,，你可能會(huì)覺得一個(gè)量子計(jì)算機(jī)可以通過(guò)‘并行地嘗試每一個(gè)可能的解’，然后‘在心臟跳一下的時(shí)間里解決NP完全問題’,。嗯,，大概那是門外漢們對(duì)于量子計(jì)算機(jī)最核心的錯(cuò)誤印象?！?/span>
(2) 干涉(interference)使得并行性得以利用成為可能,。中學(xué)物理課上大家都學(xué)習(xí)過(guò)一種物理現(xiàn)象叫做“雙縫干涉”，即一個(gè)單光源經(jīng)過(guò)雙縫之后會(huì)在后面的屏幕上留下明暗相間的條紋,。從數(shù)學(xué)上來(lái)看,，干涉可以簡(jiǎn)單理解為幾條不同的帶權(quán)重（權(quán)重可以取正、負(fù)數(shù)）的路徑匯合在一起的時(shí)候，權(quán)重可能相互抵消,，也可能相互疊加增大,。能否利用這種干涉現(xiàn)象使得量子計(jì)算并行性為我們所用，需要極具智慧的算法設(shè)計(jì),，關(guān)鍵就是要利用干涉現(xiàn)象使得我們想要的目標(biāo)路徑的權(quán)重增大,，而我們不希望出現(xiàn)的路徑權(quán)重抵消趨于零。
總結(jié)起來(lái)：量子疊加帶來(lái)潛在的并行性,，干涉使得并行性得以利用成為可能,，算法通過(guò)巧妙利用疊加與干涉發(fā)揮并行性解決實(shí)際問題。
二,、量子算法的基本框架
設(shè)計(jì)量子算法的關(guān)鍵在于：要保證算法的每一步驟符合量子力學(xué)的要求,，并最終保證其求解速度比經(jīng)典算法更快。 能發(fā)揮量子計(jì)算并行性快速解決的問題在數(shù)學(xué)上通常是關(guān)于函數(shù)的某種全局屬性,，所謂全局屬性即依賴于函數(shù)在某個(gè)區(qū)間中多個(gè)點(diǎn)處的函數(shù)值,，例如函數(shù)的周期、再如下圖中的P(f),。
上圖中給出了量子算法的一般性框架,，為了簡(jiǎn)約性圖中可能去掉了一些嚴(yán)謹(jǐn)?shù)募?xì)節(jié)。一個(gè)量子算法大致可以分為三個(gè)階段：
制備一個(gè)疊加態(tài),，它表示函數(shù)自變量值的線性組合,；
作用U_f(函數(shù)f所對(duì)應(yīng)的線性算子（矩陣）)，根據(jù)線性性,，它會(huì)分別作用在每一個(gè)基態(tài)上,，把函數(shù)對(duì)每一個(gè)自變量的值計(jì)算出來(lái)，即體現(xiàn)潛在的并行性,；
提取想要的信息,。通過(guò)巧妙的設(shè)計(jì)，利用干涉現(xiàn)象使得系統(tǒng)最后狀態(tài)能以很大的概率落到目標(biāo)點(diǎn)|P(f)>,。算法設(shè)計(jì)的巧妙性就體現(xiàn)在這一步。
三,、量子算法設(shè)計(jì)的困難性
要設(shè)計(jì)出好的量子算法并非易事,，甚至可以說(shuō)極具挑戰(zhàn)性。其困難性主要體現(xiàn)在以下兩點(diǎn)：
具有思想性的算法從來(lái)不容易,，即使在經(jīng)典計(jì)算領(lǐng)域也是如此,。任何一個(gè)原創(chuàng)性算法都是智慧的結(jié)晶。
量子力學(xué)的反直觀性使得在經(jīng)典世界積累的算法設(shè)計(jì)經(jīng)驗(yàn)可能不再適用,，而此時(shí)還要求設(shè)計(jì)出比經(jīng)典算法更好的量子算法,，從而變得雪上加霜。目前人們并不太清楚量子計(jì)算能加速解決的問題具有什么特征，進(jìn)行量子算法設(shè)計(jì)時(shí)基本上是摸著石頭過(guò)河,。
四,、量子算法研究簡(jiǎn)明進(jìn)程
雖然設(shè)計(jì)好的量子算法不易，但是研究者在這方面做了很多努力,，也取得了一系列成果,。經(jīng)常有一種說(shuō)法“現(xiàn)在就那么幾個(gè)量子算法”。這種說(shuō)法在某種程度是對(duì),，因?yàn)榫哂?/span>代表性的量子算法確實(shí)不多,。但換一個(gè)角度，以上說(shuō)法又不太正確,，因?yàn)槟壳搬槍?duì)不同應(yīng)用場(chǎng)景的量子算法有上百個(gè),，大家可以參考http://quantumalgorithmzoo.org/ 了解目前一些主要的量子算法。
如上圖所示,，追溯量子算法的歷史,，大致可分為三個(gè)階段：
（1）量子算法的第一階段（1985-1994），我們稱之為初始階段,，其特點(diǎn)是為量子而問題,，即為了展示量子計(jì)算優(yōu)勢(shì)而構(gòu)造了一些數(shù)學(xué)問題并為之設(shè)計(jì)量子算法，這些問題在當(dāng)時(shí)可能并沒有多少實(shí)用價(jià)值,。最早的量子算法可以追溯到1985年的Deutsch算法,。1985年David Deutsch在其關(guān)于量子圖靈機(jī)的開創(chuàng)性論文中給出了一個(gè)簡(jiǎn)單問題，并為之設(shè)計(jì)了一個(gè)量子計(jì)算過(guò)程,，通過(guò)利用量子疊加和干涉現(xiàn)象展現(xiàn)出了量子計(jì)算可能超越經(jīng)典計(jì)算的優(yōu)勢(shì),，這為后續(xù)量子算法設(shè)計(jì)埋下了思想的種子。雖然今天看來(lái),，Deutsch算法非常簡(jiǎn)單,，甚至?xí)?/span>覺得一切都是理所當(dāng)然的，但是在那前無(wú)古人的年代把第一個(gè)量子算法雛形設(shè)計(jì)出來(lái)是非常需要洞察力和創(chuàng)造力的,。后來(lái)的Deutsch-Jozsa算法,、Simon算法等進(jìn)一步考慮更復(fù)雜的問題并在某種意義下展現(xiàn)出了量子計(jì)算相對(duì)于經(jīng)典計(jì)算的指數(shù)加速優(yōu)勢(shì)。
關(guān)于Simon算法多說(shuō)幾句,。這可能是一個(gè)有點(diǎn)被外界忽略的量子算法,。事實(shí)上該算法的意義至少有以下兩方面：
Simon算法直接啟發(fā)了著名的Shor算法的發(fā)現(xiàn)，這一點(diǎn)無(wú)論是在Shor算法的原文還是在一些知名學(xué)者寫的量子計(jì)算方面的書里都有非常明確地指出來(lái),。
Simon算法近年在密碼破譯方面得到直接應(yīng)用,。雖然它所解決的問題在提出之初并未見明顯的應(yīng)用場(chǎng)景，然而近幾年基于Simon算法進(jìn)行密碼破譯的研究在不斷跟進(jìn),，在密碼學(xué)頂級(jí)會(huì)議Crypto上就有相關(guān)工作發(fā)表,。
有趣的是,，Simon算法的作者Daniel R. Simon似乎除了提出該算法之外并沒有其他關(guān)于量子計(jì)算的成果。或許他只是在量子計(jì)算的花園里丟下一顆種子就走的游客,，幸運(yùn)的是種子已經(jīng)發(fā)芽開花,。
（2）量子算法的第二階段（1994-2009），我們稱之為質(zhì)變階段,，其特點(diǎn)是為問題而量子,，即針對(duì)具有重要應(yīng)用價(jià)值的問題而設(shè)計(jì)量子算法。1994年,，Shor算法展示了大數(shù)分解問題可以被量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決,，而該問題在經(jīng)典計(jì)算機(jī)下的難解性是RSA公鑰密碼系統(tǒng)安全性的理論基礎(chǔ)。隨后,，1996年Grover發(fā)現(xiàn)了無(wú)序數(shù)據(jù)庫(kù)搜索的平方加速量子算法,，使得在無(wú)序數(shù)據(jù)庫(kù)中“大海撈針”成為可能。由于這些算法所解決的問題具有廣泛的應(yīng)用價(jià)值,，使得這些算法備受關(guān)注,，從而也大大推動(dòng)了整個(gè)量子計(jì)算領(lǐng)域的發(fā)展。后續(xù)不少研究就是聚焦于如何把以上兩個(gè)算法映射到更多具有實(shí)際價(jià)值的問題,。另外,，此階段提出的量子游走也是一類進(jìn)行量子算法設(shè)計(jì)的重要工具。
（3）量子算法的第三個(gè)階段（2009-至今）,，我們稱之為新的發(fā)展階段,，其特點(diǎn)是面向大數(shù)據(jù)環(huán)境。2009年解線性方程組量子算法（HHL算法）的提出標(biāo)志著量子算法進(jìn)入了第三階段,。或許HHL算法并不能與Shor算法或Grover算法媲美,，但是在大家苦苦等待新的量子算法出現(xiàn)達(dá)10多年之久，HHL算法不失為量子算法設(shè)計(jì)提供了一條新路徑,，它或許是把量子模擬應(yīng)用于數(shù)據(jù)處理的范例,。量子模擬是量子計(jì)算的一個(gè)重要方面，也涉及各種模擬算法的研究,，不過(guò)由于其與物理過(guò)程更相關(guān),，而本文更側(cè)重于利用量子技術(shù)進(jìn)行經(jīng)典數(shù)據(jù)處理，所以此處不作重點(diǎn)介紹,。
由于人工智能與大數(shù)據(jù)領(lǐng)域的諸多方法和技術(shù)都與解線性方程組有關(guān),，因此HHL算法的提出大力推動(dòng)了量子計(jì)算進(jìn)入機(jī)器學(xué)習(xí)與大數(shù)據(jù)處理等領(lǐng)域。量子計(jì)算與AI的結(jié)合近幾年成為熱點(diǎn)話題,，圖靈獎(jiǎng)得主姚期智先生也多次在報(bào)告中提及，毫無(wú)疑問這方面的交叉研究值得進(jìn)行深入探索,。
不過(guò)這里需要指出幾點(diǎn)：
HHL算法并未把方程組的解以經(jīng)典可讀取的方式呈現(xiàn)出來(lái),，而是把其編碼在量子態(tài)中,，需要經(jīng)過(guò)后續(xù)的算法設(shè)計(jì)來(lái)提取我們想要的信息。近年來(lái)出現(xiàn)的大量有關(guān)量子機(jī)器學(xué)習(xí)的研究主要就是基于HHL算法做后續(xù)算法設(shè)計(jì),。
目前一些量子機(jī)器學(xué)習(xí)方面的研究需要提供更嚴(yán)肅的理論分析,。
量子機(jī)器學(xué)習(xí)如果要面對(duì)實(shí)際數(shù)據(jù)處理問題，有待突破輸入/輸出瓶頸,。所謂輸入/輸出瓶頸是指,，目前大部分量子機(jī)器學(xué)習(xí)算法或者需要把大規(guī)模數(shù)據(jù)集編碼為量子態(tài)，或者只是把問題的解生成在量子態(tài)中,，因此輸入階段的前處理和信息提取階段的后處理將耗費(fèi)大量時(shí)間,，乃至抵消量子算法所節(jié)省的時(shí)間。
近期,，華裔學(xué)生 Ewin Tang 受量子推薦算法的啟發(fā)設(shè)計(jì)出了一個(gè)經(jīng)典算法,，它能以和量子算法相近的速度解決推薦問題，從而使得受量子啟發(fā)的經(jīng)典算法設(shè)計(jì)或者說(shuō)量子算法的經(jīng)典化進(jìn)入了更多學(xué)者的視野,。在某些問題上量子被證明相對(duì)于經(jīng)典有加速優(yōu)勢(shì),，而更多的問題并沒有蓋棺定論，如果量子算法思維能促進(jìn)經(jīng)典算法的發(fā)展,，這也將是量子計(jì)算研究意義的另一種體現(xiàn),。
五、關(guān)于量子算法的兩個(gè)疑問
筆者在平時(shí)交流中經(jīng)常被問及以下兩個(gè)問題,，特別是信息學(xué)背景的朋友問得比較多,，相關(guān)問題和回答如下：
（1）量子計(jì)算機(jī)沒造出來(lái)，有必要研究量子算法嗎,？
從經(jīng)典計(jì)算領(lǐng)域來(lái)看,，算法的研究遠(yuǎn)遠(yuǎn)早于計(jì)算機(jī)的出現(xiàn)。歐幾里德算法出現(xiàn)在古希臘時(shí)代,，而第一臺(tái)電子計(jì)算機(jī)是1946年生產(chǎn)的,。另外，圖靈機(jī)的提出正是為了嚴(yán)格地刻畫“算法”,。
沒有算法支持的量子計(jì)算機(jī)是否還能稱為計(jì)算機(jī)呢,？量子算法是量子計(jì)算機(jī)的必要軟件支撐，同時(shí)量子算法的研究也是推動(dòng)量子計(jì)算發(fā)展的強(qiáng)大動(dòng)力,，從Shor算法的歷史地位可見一斑,。
（2）沒有量子計(jì)算機(jī)，怎么研究量子算法,？怎么評(píng)價(jià)算法的好壞,？
抽象層次的算法設(shè)計(jì)從來(lái)不依賴于具體硬件平臺(tái)，在經(jīng)典計(jì)算領(lǐng)域就是如此,。算法本質(zhì)上是解決問題的一種方法,，量子算法是遵循量子力學(xué)規(guī)律的一種方法,。硬件平臺(tái)只是實(shí)現(xiàn)這種方法的一個(gè)工具。當(dāng)然,，軟硬件之間的互動(dòng)與交流對(duì)于設(shè)計(jì)更符合實(shí)際情況的算法非常必要,。
從算法與復(fù)雜性研究的角度來(lái)看，算法的好壞由復(fù)雜度衡量,，這依賴于嚴(yán)格的數(shù)學(xué)證明,，而不是在具體硬件平臺(tái)上的測(cè)試。目前量子算法主流的研究是如此,。
六,、總結(jié)
量子計(jì)算機(jī)相對(duì)與經(jīng)典計(jì)算機(jī)在哪些方面有優(yōu)勢(shì)？有多大程度的優(yōu)勢(shì),？這些問題目前遠(yuǎn)未搞清楚,，這意味著量子算法的研究有非常大的空間。大家都期待量子計(jì)算領(lǐng)域有更多具有創(chuàng)新性的算法出現(xiàn),，每一位量子算法研究者也都希望設(shè)計(jì)出一個(gè)代表性算法,。然而，羅馬不是一天建成的,，千里之行始于足下,。我們不應(yīng)只記住Shor算法的巧妙，而忘記前人的努力,。事實(shí)上,，Shor算法是站在Simon算法的肩上，而Simon算法源于那些看似沒用的Deutsch-Jozsa算法和Deutsch算法,。這個(gè)過(guò)程正好體現(xiàn)了科學(xué)研究的魅力：或許很多研究成果會(huì)被大浪淘沙,，但正是那些一點(diǎn)一滴的看似無(wú)用的研究一步一步孕育著一個(gè)新的發(fā)現(xiàn)！
最后一句：量子計(jì)算研究要“軟硬兼施“,！
研究團(tuán)隊(duì)介紹：
本文來(lái)自中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院量子計(jì)算實(shí)驗(yàn)室(http://htcdzsw999.com/team/quantumlab),，研究團(tuán)隊(duì)主要研究興趣為量子計(jì)算模型、算法與復(fù)雜性,，主要從計(jì)算機(jī)科學(xué)角度出發(fā),，圍繞”量子計(jì)算相對(duì)于經(jīng)典計(jì)算有何優(yōu)勢(shì)與本質(zhì)不同”這一中心問題開展研究。
中山大學(xué)計(jì)算機(jī)學(xué)科從2000年左右開始從事量子計(jì)算方面的研究,，是國(guó)內(nèi)計(jì)算機(jī)領(lǐng)域最早從事量子計(jì)算研究的力量之一,，已培養(yǎng)量子計(jì)算方面的研究生數(shù)十人，未來(lái)將一如既往地為量子計(jì)算的研究和人才培養(yǎng)做出努力,。如果您是對(duì)量子計(jì)算感興趣的學(xué)生,，歡迎一起來(lái)探索量子計(jì)算領(lǐng)域有趣的問題。如果您已學(xué)業(yè)有成,，歡迎加入中山大學(xué),，我們一直在致力于團(tuán)隊(duì)建設(shè),。期待有志青年加入，攜手共創(chuàng)未來(lái),！
研究團(tuán)隊(duì)招聘專任教師、特聘研究員,、副研究員,、博士后，歡迎從事量子計(jì)算相關(guān)研究的青年才俊加入,！招收博士,、碩士、高年級(jí)本科,。歡迎聯(lián)系咨詢（李綠周：[email protected]）,，同時(shí)可以搜索微信公眾號(hào)“中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院”了解相關(guān)招聘信息。
