（圖片來源：網(wǎng)絡(luò)）

編者按：量子計算機究竟有多大神奇的魔力？它有多大的能力？能否帶來計算的革命，是否能取代我們現(xiàn)在的經(jīng)典計算機？探尋量子優(yōu)勢是量子計算領(lǐng)域的核心問題之一，而量子優(yōu)勢的發(fā)揮有賴于量子算法。同時，要搞清楚量子計算與經(jīng)典計算的邊界，需要從算法復(fù)雜度的角度進(jìn)行深入研究。因此量子算法復(fù)雜度也是量子計算理論的核心內(nèi)容之一。

算法復(fù)雜度的定義

無論是量子計算機還是經(jīng)典計算機，具有共同的本質(zhì)，就是需要去解決數(shù)學(xué)問題或邏輯問題。這就需要去判斷哪些問題是可計算的，哪些是不可計算的。對于可計算的問題，計算機需要投入多少時間資源和內(nèi)存資源去求解，不同類型的計算機的效率如何比較，這些都涉及到可計算理論。

早在20世紀(jì)50年代，現(xiàn)代的電子計算機都還沒有很成型的時候，可計算性理論就已經(jīng)開始發(fā)展起來。可計算性理論旨在探索不同計算機器理論上的能力界限，判斷解決具體問題所設(shè)計的實際算法是否具備可行性，也就是在有限（內(nèi)存）空間和時間范圍內(nèi)，能夠在輸入后獲得最終的處理結(jié)果。

算法復(fù)雜度就是可計算理論的核心，它在數(shù)學(xué)上將算法與解決問題的“規(guī)?！睊煦^，讓問題“規(guī)?！迸c算法形成函數(shù)類的映射關(guān)系。以排序算法為例，對1萬個數(shù)進(jìn)行排序所需時間肯定比對10個數(shù)排序的時間長得多。但是這個時間長得多，能否有一個相對的比對關(guān)系作為衡量？復(fù)雜度理論就給出了這個比較關(guān)系，它包含兩方面的復(fù)雜度：

時間復(fù)雜度：用于評估執(zhí)行程序所消耗的時間，可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?/p>

空間復(fù)雜度：用于評估執(zhí)行程序所占用的內(nèi)存空間，可以估算出程序?qū)τ嬎銠C內(nèi)存的使用程度。

根據(jù)復(fù)雜度理論的研究成果，時間復(fù)雜度與空間復(fù)雜度之間是相互關(guān)系的。其結(jié)論是當(dāng)在時間復(fù)雜度上獲得利益的同時，必須在空間復(fù)雜度上做出妥協(xié)，時間與空間的開銷就像分別坐在蹺蹺板兩邊，一方面抬起，另一方面必然下沉，我們無法在兩個方面同時獲益。

算法復(fù)雜度的衡量

由于內(nèi)存空間的開銷好滿足，而時間上的開銷更加具有“剛性”，所以一般在算法復(fù)雜度中，主要討論的是時間復(fù)雜度的問題。時間復(fù)雜度并不是表示一個算法解決某個具體問題需要花多少時間，而是要衡量當(dāng)算法所處理的問題規(guī)模擴(kuò)大后，求解需要的時間長度對應(yīng)增長得有多快。

也就是說，對于某一個算法其處理某一系列特定數(shù)據(jù)的效率不能衡量該程序的好壞，而應(yīng)該看當(dāng)這個數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運行時間是否還是一樣，或者也跟著慢了數(shù)百倍，或者變慢了數(shù)萬倍。時間復(fù)雜度一般用O(大寫字母O)表示。

如果不管數(shù)據(jù)的規(guī)模如何增長，算法求解所需時間始終是不變的，我們就說這個算法很好，具有O(1)的時間復(fù)雜度，也稱常數(shù)級復(fù)雜度。如果數(shù)據(jù)規(guī)模變得有多大，求解時間也同比例變得有多長，比如找n個數(shù)中的最大值這個算法的時間復(fù)雜度就是O(n)，為線性級復(fù)雜度。而像排序等算法，數(shù)據(jù)擴(kuò)大2倍，所需時間變4倍的，時間復(fù)雜度就是O(n2)，為平方級復(fù)雜度。還有一些窮舉類的算法，所需時間長度成幾何階數(shù)上漲，這就是O(an?)的指數(shù)級復(fù)雜度，在組合問題中，甚至還有O(n!)的階乘級復(fù)雜度。

這樣，時間復(fù)雜度就可以用來衡量算法與算法之間、甚至是不同計算架構(gòu)之間的效率了。還是用排序算法來舉例，剛才說過簡單的排序算法是與排序數(shù)據(jù)量成平方關(guān)系，記作O(n2)，如果算法經(jīng)過優(yōu)化，其實能夠做到O(log2n）。

不會存在 O(2?n2)?的復(fù)雜度，因為前面的那個"2"是系數(shù)，根本不會影響到整個程序的時間增長。同樣地，O(n3+n2)的復(fù)雜度也就是O(n3)的復(fù)雜度。因此，我們會說，一個O(0.01*n3)的程序的復(fù)制度要高于比O(100*n2)的復(fù)雜度，因為盡管在n很小的時候，前者優(yōu)于后者，但后者時間隨數(shù)據(jù)規(guī)模增長得慢，最終 O(n3)的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過O(n2)。

再往前一步說，就算再大的多項式n10000，也不能和再小的指數(shù)函數(shù)1.0001n相比。因為總是存在一個M，當(dāng)n>M的時候，1.0001n會超過n10000，所以說，O(n10000)的復(fù)雜度小于O(1.0001n)的復(fù)雜度。

像O(1)，O(ln(n))，O(na)等，我們把它叫做多項式級復(fù)雜度，因為它的規(guī)模n出現(xiàn)在底數(shù)的位置。另一種像O(an)和O(n!)等，它是非多項式級的復(fù)雜度，其復(fù)雜度用經(jīng)典計算機往往不能承受。當(dāng)我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復(fù)雜度，非多項式級的復(fù)雜度需要的時間太多，使用經(jīng)典計算機求解往往需要超出實用性的時間。

經(jīng)典計算中的復(fù)雜度分類

1.?P類問題（Polynomial-time?problem）：能在多項式時間內(nèi)可解的問題。

2.?NP類問題（Nondeterministic polynomial-time?problem）：不確定能不能在多項式時間內(nèi)解決，但能在多項式時間驗證的問題。也就是說，不能判定這個問題到底有沒有解，而是猜出一個解來在多項式時間內(nèi)證明這個解是否正確。即該問題的猜測過程是不確定的，而對其某一個解的驗證則能夠在多項式時間內(nèi)完成。值得注意的是，P類問題屬于NP問題，但是否“NP=P?”，也即“是否所有能在多項式時間內(nèi)驗證得出正確解的問題，都是具有多項式時間求解算法的問題”，至今尚未有定論，是數(shù)學(xué)界的一個千禧年難題。

3.?NPC問題（Non-deterministic Polynomial complete problem ）：存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。其定義要滿足2個條件：①它是一個NP問題；②所有NP問題都能規(guī)約到它。

4.?NP難問題（Non-deterministic Polynomial hard problem）：NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的范圍廣，NP-Hard問題沒有限定屬于NP），即所有的NP問題都能約化到它，但是它不一定是一個NP問題。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決。

引入量子計算后的復(fù)雜度分類

量子計算作為一種顛覆性技術(shù)已經(jīng)引起了各界的廣泛關(guān)注。由于在量子計算中，量子比特的疊加態(tài)可以用作計算資源，算力可以隨著量子比特的數(shù)量呈指數(shù)型的增長，也因此對于某些在傳統(tǒng)計算機上呈現(xiàn)指數(shù)型時間復(fù)雜度的問題，理論上可能因為采用量子計算機獲得多項式時間復(fù)雜度的解決。

以質(zhì)因數(shù)分解問題為例：兩個大素數(shù)的乘積是很容易計算的，但是如果將這個乘積反過來分解成兩個大素數(shù)就沒有一個簡單的方式，它的算法復(fù)雜度是O(2n)，是指數(shù)增長的，因此這個分解大素數(shù)的算法是NP問題，現(xiàn)代密碼學(xué)的基礎(chǔ)——RSA加密算法就是基于此開發(fā)出來的。用經(jīng)典計算機去破解一個256位的RSA密碼，需要成千上萬年的時間，這就保證了密碼的安全性。

但是在1994年，量子計算機的專家肖爾（Peter Shor）提出一個以他的名字命名的算法，宣稱能夠用多項式算法復(fù)雜度解決大素數(shù)因式分解問題，在理論上對現(xiàn)代RSA密碼體系造成了極大威脅。

由此可見，量子計算設(shè)備是與經(jīng)典的電子計算機完全不同的計算工具，在求解一些“復(fù)雜問題”上有著明顯優(yōu)勢。所以在界定量子計算和量子算法的應(yīng)用范圍時，量子復(fù)雜度理論（Quantum complexity theory）也就應(yīng)運而生，它主要研究引入量子計算后計算復(fù)雜度，以及量子復(fù)雜度類與經(jīng)典復(fù)雜度類的關(guān)系。

在引入量子計算復(fù)雜度性后，不同計算復(fù)雜度問題集合機器之間的關(guān)系可由下圖表述：

?

圖1顯示了復(fù)雜度類及廣泛認(rèn)可的包含關(guān)系的示意圖。

?

量子復(fù)雜度中兩個比較重要的復(fù)雜度類分別是BQP及QMA，分別對應(yīng)經(jīng)典計算中的復(fù)雜度P及NP復(fù)雜度。值得注意的是，圖中的許多復(fù)雜類還沒有經(jīng)過數(shù)學(xué)證明：例如P是否等價于NP。而一些傳統(tǒng)認(rèn)為是NP難的問題，如質(zhì)因數(shù)分解，在引入量子計算后已經(jīng)證明使用Shor分解算法就能在多項式時間內(nèi)可解，因此歸于BQP類問題。

文：王凱/王衍

編輯：慕一