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