文／田國(guó)敬 孫曉明

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

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

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

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

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

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

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

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

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

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

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

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