量子計算應(yīng)用前景廣闊，但需更高效算法

文／田國敬 孫曉明

量子力學(xué)是上世紀(jì)最偉大的科學(xué)發(fā)現(xiàn)之一，其從根本上改變了人類對經(jīng)典物質(zhì)結(jié)構(gòu)及其相互作用的理解。量子調(diào)控技術(shù)的進(jìn)步有望推動第二次量子革命，從而對未來社會產(chǎn)生本質(zhì)的影響。

量子計算旨在利用量子力學(xué)特性來獲得比經(jīng)典計算在性能上潛在的提升，并已經(jīng)在一些計算問題上展示出了超越經(jīng)典計算的能力。首先，不同于經(jīng)典計算中的比特只能夠處在0或1之中一個確定的狀態(tài)，微觀粒子可以同時處于0和1——即0與1疊加的狀態(tài)。例如思想實驗中，在黑箱中的薛定諤貓?zhí)幱谏c死的疊加狀態(tài)，即同時是活的貓也是死的貓。但是一旦打開黑箱，這一疊加的狀態(tài)會塌縮為一個經(jīng)典的狀態(tài)，貓只能是生或死中確定的一種，即“觀測即改變”。

此外，不同于經(jīng)典世界中兩個比特之間的概率相關(guān)性，微觀世界中相距遙遠(yuǎn)的兩個微觀粒子可以處于糾纏的狀態(tài)，觀測其中一個可以瞬時影響另一個的狀態(tài)，這一過程的一個形象的比喻就像一對雙胞胎雖然分隔在兩地卻能與對方有“心靈感應(yīng)”。量子疊加和量子糾纏已經(jīng)被物理學(xué)家通過實驗多次反復(fù)驗證。

小學(xué)生可以很容易地知道11×17=187，也能夠計算出12347×34589的結(jié)果，對于再大一些的數(shù)相乘（例如兩個有100位數(shù)字的整數(shù)），計算機(jī)仍然可以立即給出答案。但是如果給一個有200位數(shù)字的整數(shù)，想要把它分解成為兩個100位整數(shù)的乘積，問題一下就困難了許多。這個問題被稱為整數(shù)素因子分解問題，是目前廣泛使用的RSA公鑰密碼（1977年由三位學(xué)者一起提出的，RSA是他們?nèi)诵帐祥_頭字母的縮寫）的根基。

目前，在經(jīng)典計算機(jī)上最好的算法需要指數(shù)量級的時間：在最快的超級計算機(jī)上分解一個有512位數(shù)字的整數(shù)需要數(shù)周時間，而分解一個有1024位數(shù)字的整數(shù)需要的時間將是一個天文數(shù)字。因此，通常認(rèn)為RSA公鑰密碼目前是安全的。

1994年，貝爾實驗室的彼得·肖爾（Peter Shor）提出了一個整數(shù)素因子分解的量子算法，可以在量子計算機(jī)上花費多項式量級時間內(nèi)完成整數(shù)的素因子分解，例如分解1024位數(shù)字的整數(shù)在通用量子計算機(jī)上只需要幾秒。這動搖了RSA公鑰密碼的理論根基，給密碼安全帶來了潛在的威脅。需要指出，這種威脅目前仍是理論層面的，要想破解1024位RSA公鑰密碼需要3000個以上的邏輯量子比特，而現(xiàn)階段的超導(dǎo)量子硬件設(shè)備大約可以達(dá)到50—70個物理量子比特。

另一方面，我們也需要看到量子實驗技術(shù)的發(fā)展非常迅速，事實上從研制5個超導(dǎo)量子比特到研制出50個超導(dǎo)量子比特只用了不到三年的時間。IBM等公司宣稱，將在2023年實現(xiàn)超過1000個量子比特的量子硬件設(shè)備。或許未來突破實驗瓶頸之后，不需要太久具有更多量子比特的量子硬件也將被研制出來。此外，肖爾量子算法主要針對整數(shù)素因子分解問題和離散對數(shù)問題。密碼學(xué)家很早就在尋找基于其他困難問題的密碼方案，即后量子密碼體系。但同樣是否也會有針對這些問題的快速求解量子算法呢？學(xué)者們?nèi)栽诜e極探索。

除了肖爾量子算法之外，另一個經(jīng)常被人們提到的量子算法是格羅弗量子搜索算法，該算法由同樣來自貝爾實驗室的洛夫·格羅弗（Lov Grover）提出，其利用了量子相干特性來加速在無結(jié)構(gòu)的數(shù)據(jù)庫中搜索目標(biāo)，比經(jīng)典搜索算法在時間上能夠有開平方數(shù)量級加速。譬如，有1億條無索引的記錄需要被處理，假設(shè)處理每條記錄的平均時間需要0.01秒，經(jīng)典算法總的處理時間大約需要12天，而量子算法只需要約100秒。

雖然格羅弗算法沒有像肖爾算法那樣能夠提供指數(shù)級別加速，但是由于搜索問題的應(yīng)用范圍和場景要比整數(shù)素因子分解問題廣泛得多，因此學(xué)者們在這一方向進(jìn)行了非常系統(tǒng)和深入的研究。例如：量子振幅放大算法能夠集成多個弱的算法變成一個更強(qiáng)的算法；量子局部搜索算法能夠更快地找到局部最優(yōu)解；量子游走算法能夠加速經(jīng)典的隨機(jī)游走算法等。該算法也可以直接被用來破解密碼或求解NP（即非確定性圖靈機(jī)在多項式時間內(nèi)可求解的問題）困難的組合優(yōu)化問題。

除了上述兩個經(jīng)常被提及的量子算法之外，學(xué)者們還研發(fā)了多個重要的量子算法，這些量子算法的提出，為量子特性在計算領(lǐng)域的應(yīng)用提供了非常有意義的指導(dǎo)和示范。雖然學(xué)者們已經(jīng)研發(fā)出了多個重要的量子算法，但是相較于浩如煙海的經(jīng)典算法，目前的量子算法可能還只是冰山一角。

量子計算要想充分發(fā)揮出其優(yōu)勢，既需要量子硬件的支撐，也需要量子算法的創(chuàng)新。在中大規(guī)模量子硬件設(shè)備即將到來之際，我們必須設(shè)計更多更高效的量子算法來解決數(shù)學(xué)、物理、化學(xué)、醫(yī)藥、金融等關(guān)乎國計民生的諸多重要問題，為人民群眾的美好生活作出貢獻(xiàn)。

目前，量子計算已經(jīng)成為世界各國學(xué)界和業(yè)界競相爭奪的新高地。在一些專門設(shè)計的任務(wù)上，量子優(yōu)勢已經(jīng)被實驗驗證。如何深刻理解量子特性本身，并設(shè)計更高效實用的量子算法，針對實際應(yīng)用問題去展示更具現(xiàn)實意義的量子優(yōu)勢，在真實量子硬件上實現(xiàn)實用量子算法的編譯優(yōu)化和高效運行，以及如何克服現(xiàn)階段實驗遇到的量子比特保真度低、相干時間短、噪聲和串?dāng)_高等困難和挑戰(zhàn)，研制中等規(guī)模量子硬件設(shè)備并能夠穩(wěn)定運行，將是未來一段時間需要重點突破的瓶頸。