9733
0
2020-05-07
2020-11-04
李綠周,，量子計(jì)算研究要“軟硬兼施”，《中國(guó)科學(xué)報(bào)》 (2020-05-07 第3版 信息技術(shù))
http://news.sciencenet.cn/sbhtmlnews/2020/5/354996.shtm
注：引用請(qǐng)注明以上出處,，全文如下：
近年來(lái),，量子計(jì)算受到了極大關(guān)注，根本原因在于其具有強(qiáng)大的并行性,，可以在有效時(shí)間內(nèi)解決一些經(jīng)典計(jì)算機(jī)不能有效解決的問(wèn)題,。
然而，量子計(jì)算的并行性并非直接可以利用,，而是需要根據(jù)所解決的問(wèn)題經(jīng)過(guò)巧妙的算法設(shè)計(jì)才可能,。即便量子計(jì)算機(jī)硬件研制成功，如果沒(méi)有相應(yīng)的量子算法,，量子計(jì)算的潛能還是得不到實(shí)質(zhì)性發(fā)揮,。因此，要想利用量子計(jì)算解決實(shí)際問(wèn)題，能否設(shè)計(jì)出快速的量子算法是關(guān)鍵,。當(dāng)然,，量子算法需要運(yùn)行在量子計(jì)算硬件平臺(tái)上才能起作用。
因此,，量子計(jì)算研究要“軟硬兼施”,。
量子算法的歷史階段
量子算法的第一階段（1985-1994），我們稱之為初始階段,，其特點(diǎn)是為量子而問(wèn)題，即為了展示量子計(jì)算優(yōu)勢(shì)而構(gòu)造了一些數(shù)學(xué)問(wèn)題并為之設(shè)計(jì)量子算法,，這些問(wèn)題在當(dāng)時(shí)可能并沒(méi)有多少實(shí)用價(jià)值,。
最早的量子算法可以追溯到1985年的Deutsch算法。1985年David Deutsch在其關(guān)于量子圖靈機(jī)的開(kāi)創(chuàng)性論文中給出了一個(gè)簡(jiǎn)單問(wè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í)X(jué)得一切都是理所當(dāng)然的,，但是在那前無(wú)古人的年代把第一個(gè)量子算法雛形設(shè)計(jì)出來(lái)是非常需要洞察力和創(chuàng)造力的,。后來(lái)的Deutsch-Jozsa算法、Simon算法等進(jìn)一步考慮更復(fù)雜的問(wèn)題并在某種意義下展現(xiàn)出了量子計(jì)算相對(duì)于經(jīng)典計(jì)算的指數(shù)加速優(yōu)勢(shì),。
Simon算法可能是一個(gè)有點(diǎn)被外界忽略的量子算法,。事實(shí)上該算法的意義至少有以下兩方面：一方面Simon算法直接啟發(fā)了著名的Shor算法的發(fā)現(xiàn)，這一點(diǎn)無(wú)論是在Shor算法的原文還是在一些知名學(xué)者寫(xiě)的量子計(jì)算方面的書(shū)里都有非常明確地指出來(lái),；另一方面Simon算法近年在密碼破譯方面得到直接應(yīng)用,。
量子算法的第二階段（1994-2009），我們稱之為質(zhì)變階段,，其特點(diǎn)是為問(wèn)題而量子,，即針對(duì)具有重要應(yīng)用價(jià)值的問(wèn)題而設(shè)計(jì)量子算法。1994年,，Shor算法展示了大數(shù)分解問(wèn)題可以被量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決,，而該問(wèn)題在經(jīng)典計(jì)算機(jī)下的難解性是RSA公鑰密碼系統(tǒng)安全性的理論基礎(chǔ)。隨后,，1996年Grover發(fā)現(xiàn)了無(wú)序數(shù)據(jù)庫(kù)搜索的平方加速量子算法,，使得在無(wú)序數(shù)據(jù)庫(kù)中“大海撈針”成為可能。
由于這些算法所解決的問(wèn)題具有廣泛的應(yīng)用價(jià)值,，因而備受關(guān)注,，從而也大大推動(dòng)了整個(gè)量子計(jì)算領(lǐng)域的發(fā)展。后續(xù)不少研究就是聚焦于如何把以上兩個(gè)算法映射到更多具有實(shí)際價(jià)值的問(wèn)題。另外,，此階段提出的量子游走也是一類(lèi)進(jìn)行量子算法設(shè)計(jì)的重要工具,。
量子算法的第三個(gè)階段（2009-至今），我們稱之為新的發(fā)展階段,，其特點(diǎn)是面向大數(shù)據(jù)環(huán)境,。2009年解線性方程組量子算法（HHL算法）的提出標(biāo)志著量子算法進(jìn)入了第三階段?；蛟SHHL算法并不能與Shor算法或Grover算法媲美,，但是在大家苦苦等待新的量子算法出現(xiàn)達(dá)10多年之久，HHL算法不失為量子算法設(shè)計(jì)提供了一條新路徑,，它或許是把量子模擬應(yīng)用于數(shù)據(jù)處理的范例,。
由于人工智能與大數(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)告中提及，這方面的交叉研究值得進(jìn)行深入探索,。
量子算法的問(wè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ù)處理問(wèn)題,，有待突破輸入/輸出瓶頸,。所謂輸入/輸出瓶頸是指，大部分量子機(jī)器學(xué)習(xí)算法或者需要把大規(guī)模數(shù)據(jù)集編碼為量子態(tài),，或者只是把問(wèn)題的解生成在量子態(tài)中,，因此輸入階段的前處理和信息提取階段的后處理將耗費(fèi)大量時(shí)間，乃至抵消量子算法所節(jié)省的時(shí)間,。
近期,，華裔學(xué)生Ewin Tang受量子推薦算法的啟發(fā)設(shè)計(jì)出了一個(gè)經(jīng)典算法，它能以和量子算法相近的速度解決推薦問(wèn)題,，從而使得受量子啟發(fā)的經(jīng)典算法設(shè)計(jì)或者說(shuō)量子算法的經(jīng)典化進(jìn)入了更多學(xué)者的視野,。如果量子算法思維能促進(jìn)經(jīng)典算法的發(fā)展，這也將是量子計(jì)算研究意義的另一種體現(xiàn),。
筆者梳理了有關(guān)量子算法的兩個(gè)常見(jiàn)問(wèn)題和回答,，以供參考。
問(wèn)：量子計(jì)算機(jī)還沒(méi)造出來(lái),，現(xiàn)在有必要研究量子算法嗎,？
答：首先,，從經(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)格地刻畫(huà)“算法”,。
其次，沒(méi)有算法支持的量子計(jì)算機(jī)還能稱為計(jì)算機(jī)嗎,？量子算法是量子計(jì)算機(jī)的必要軟件支撐,，同時(shí)量子算法的研究也是推動(dòng)量子計(jì)算向前發(fā)展的強(qiáng)大動(dòng)力，從Shor算法的歷史地位可見(jiàn)一斑,。所以研究量子算法也是研制量子計(jì)算機(jī)的重要環(huán)節(jié)之一,。
問(wèn)：沒(méi)有量子計(jì)算機(jī)，怎么研究量子算法,？怎么評(píng)價(jià)算法的好壞？
答：抽象層次的算法設(shè)計(jì)從來(lái)不依賴于具體硬件平臺(tái),，在經(jīng)典計(jì)算領(lǐng)域就是如此,。算法本質(zhì)上是解決問(wèn)題的一種方法，量子算法是遵循量子力學(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è)試,。目前量子算法主流的研究是如此。
隨著量子計(jì)算實(shí)驗(yàn)技術(shù)的發(fā)展,，有越來(lái)越多的量子算法得以在真實(shí)量子平臺(tái)上進(jìn)行原理性驗(yàn)證,。可能有時(shí)研究者會(huì)在經(jīng)典計(jì)算機(jī)上對(duì)量子算法進(jìn)行一定模擬以加深理解,，但那并非在經(jīng)典計(jì)算機(jī)實(shí)現(xiàn)了量子算法,。
千里之行始于足下
量子計(jì)算相對(duì)與經(jīng)典計(jì)算在哪些方面有優(yōu)勢(shì)？有多大程度的優(yōu)勢(shì),？這些問(wèn)題目前遠(yuǎn)未搞清楚,，這意味著量子算法的研究有非常大的空間。大家都期待量子計(jì)算領(lǐng)域有更多具有創(chuàng)新性的算法出現(xiàn),，每一位量子算法研究者也都希望設(shè)計(jì)出一個(gè)代表性算法,。
然而,，羅馬不是一天建成的，千里之行始于足下,。我們不應(yīng)只記住Shor算法的巧妙,，而忘記前人的努力。事實(shí)上,，Shor算法是站在Simon算法的肩上,，而Simon算法源于那些看似沒(méi)用的Deutsch-Jozsa算法和Deutsch算法。
這個(gè)過(guò)程正好體現(xiàn)了科學(xué)研究的魅力：或許很多研究成果會(huì)被大浪淘沙,，但正是那些一點(diǎn)一滴的看似無(wú)用的研究,，一步一步孕育著一個(gè)新的發(fā)現(xiàn)。
