??學(xué)習(xí)量子計算、密碼學(xué)、Space等Web3前沿技術(shù)

??認(rèn)領(lǐng)Bounty，賺取賞金

??參與Hackathon，獲得資助

更多Web3精彩技術(shù)分享盡在Dōjō??

WeChat: @HackerDojo0

量子理論

1. 加法的復(fù)雜度

簡單地說，量子計算機可以解決一些經(jīng)典計算機無法解決的問題。要理解其中的原因，我們首先需要考慮解決某些問題需要多少計算工作量。

首先，我們回顧一下第一節(jié)中討論的算法:兩個數(shù)相加。

??$9213$

$+$?$1854$

$=$?$???$

兩個$\boldsymbol{n}$位數(shù)的和可以通過一組簡單的操作來完成，每個操作只包括兩個個位數(shù)的相加。為了分析這個程序的復(fù)雜度，我們可以考慮一下它需要做多少次基本的加法，以及這個次數(shù)與$\boldsymbol{n}$的關(guān)系。這個數(shù)我們記為$\boldsymbol{c(n)}$。

在最簡單的情況下，我們不需要在任何地方進(jìn)位1，只需要n個基本的加法。在最壞的情況下，我們將需要執(zhí)行n次進(jìn)位操作，每一次都需要額外的基本加法。根據(jù)這些考慮，我們可以得出結(jié)論$\boldsymbol{n≤c(n)≤2n}$.

2. 大O表示法

我們可以把這個結(jié)果總結(jié)為c(n)隨n線性增長。更一般地說，我們可以說，當(dāng)n很大時，可以找到一個關(guān)于n的線性函數(shù)，作為c(n)的上界。由于這是一個又長又啰嗦的句子，我們實際上不想經(jīng)常這樣說。相反，我們可以使用“大O表示法”更簡潔地表示它。

大O表示法很有用，因為它允許我們比較算法所需的資源/運行時間如何隨輸入大小變化，而不受特定平臺和算法實現(xiàn)的影響。下面是運行時間$\boldsymbol{N}$作為輸入大小$\boldsymbol{n}$的函數(shù)的常見比例因子的例子;顯然，對于一個足夠大的問題規(guī)模，$\boldsymbol{O(a^n)}$算法的運行時間將超過$\boldsymbol{O(n^b)}$算法的運行時間，其中$\boldsymbol{a}$和$\boldsymbol$是常數(shù)。

不同時間復(fù)雜度的比較。n是輸入的比特數(shù)，n是需要操作的次數(shù)。

使用這種表示法，上面描述的屬性可以簡單地表示為$\boldsymbol{c(n)=O(n)}$。這捕捉到了線性行為，而無需糾結(jié)于細(xì)節(jié)。因此，與$\boldsymbol{c(n)=n}$還是$\boldsymbol{2n}$或其他都無關(guān)，我們可以簡單地說$\boldsymbol{c(n)=O(n)}$。

到目前為止，我們所考慮的問題中有一個隱藏的假設(shè)。通過討論數(shù)字的數(shù)量，我們已經(jīng)假設(shè)使用了一個特定的數(shù)字系統(tǒng)。然而，數(shù)字的數(shù)量將取決于我們使用的數(shù)字系統(tǒng)，是十進(jìn)制，二進(jìn)制，還是其他。例如，表示一個數(shù)所需的位數(shù)$\boldsymbol{n_2}$與表示同一個數(shù)所需的十進(jìn)制位數(shù)$\boldsymbol{n_{10}}$相關(guān)，即

因為這也是一個線性關(guān)系，所以它不會改變我們使用大O表示法表示復(fù)雜度的方式。我們同樣可以說$\boldsymbol{c(n_2)=O(n_2)}$，$\boldsymbol{c(n_{10})=O(n_{10})}$，甚至$\boldsymbol{c(n_{10})=O(n_2)}$。正是由于這個原因，我們通?？梢院唵蔚卣f數(shù)字的數(shù)量n，而不需要指定使用什么數(shù)字系統(tǒng)。

3. 復(fù)雜性理論

復(fù)雜性理論研究的是運行任何算法所需的計算量。通過考慮解決給定問題的最佳算法，我們也可以研究解決該問題所固有的計算工作量。對于加法，我們已經(jīng)知道了最優(yōu)算法，因此我們知道這是一個$\boldsymbol{O(n)}$復(fù)雜度的問題。

乘法可沒這么簡單。你在學(xué)校里學(xué)過的兩個n位數(shù)相乘的算法需要$\boldsymbol{O(n^2)}$個基本運算，比如個位數(shù)的加法和乘法。雖然已經(jīng)發(fā)現(xiàn)了具有較低漸近復(fù)雜度的算法，但$\boldsymbol{O(n)}$復(fù)雜度的乘法運算被普遍認(rèn)為是不可能的。

即便如此，乘法還遠(yuǎn)不是最復(fù)雜的問題。一個復(fù)雜得多的問題是因數(shù)分解:取一個n位數(shù)并找出它的質(zhì)因數(shù)。在這種情況下，已知的最佳算法的復(fù)雜度高于$\boldsymbol{O(e^{n^{1/3}})}$。這里的指數(shù)意味著復(fù)雜度增長得非?？?，使得因式分解成為一個很難解決的問題。

為了用實際的計算時間來證明這一點，我們可以舉一個最近的例子?？紤]下面的829位數(shù)。

如果你嘗試使用計算機對這種大小的數(shù)字進(jìn)行加法或乘法運算，你會發(fā)現(xiàn)它可以很快地解決此類問題。如果你將計算機的處理器數(shù)量乘以它運行的秒數(shù)得到core-seconds，你肯定會發(fā)現(xiàn)需要的core-seconds遠(yuǎn)遠(yuǎn)小于1。

然而，對這個數(shù)字進(jìn)行因數(shù)分解需要一臺超級計算機和大約2700 core-years，最終得到以下兩個因子。

對于更大數(shù)字的因數(shù)分解，我們很容易達(dá)到這樣的程度:一個行星大小的超級計算機需要運行整個宇宙的年齡。顯然，任何這樣的問題實際上都是不可能的。

到目前為止，我們只考慮了$\boldsymbol{n}$位數(shù)的數(shù)學(xué)運算，其復(fù)雜度表示為所需的簡單個位數(shù)運算的次數(shù)。然而，復(fù)雜性理論可以用于分析任何類型問題的任何計算方法，如搜索數(shù)據(jù)庫、渲染圖像、模擬動態(tài)或穿越《塞爾達(dá)傳說》中的地下城。在每種情況下，我們都能夠找到一個或一組參數(shù)作為輸入大小，并使用大O表示法根據(jù)輸入大小表示復(fù)雜度。例如，搜索一個包含$\boldsymbol{N}$個條目的數(shù)據(jù)庫，其復(fù)雜度為$\boldsymbol{O(n)}$。

形式上，定義算法的復(fù)雜性取決于我們使用的計算的精確理論模型。每個模型都有一組基本操作，稱為原語操作(primitive operations)，任何算法都可以用它們來表示。對于布爾電路，如我們在第一節(jié)中所述，原語操作是邏輯門。圖靈機是艾倫·圖靈(Alan Turing)提出的一種假想的計算機形式，我們可以想象一個設(shè)備在磁帶上執(zhí)行并操作存儲在磁帶上的信息。RAM模型具有一組更復(fù)雜的原語操作，相當(dāng)于我們每天使用的計算機的理想化形式。所有這些都是基于離散值的離散化操作的數(shù)字計算模型。盡管它們看起來可能不同，但事實證明，它們中的每一個都很容易模擬另一個。這意味著在大多數(shù)情況下，計算復(fù)雜度并不明顯依賴于使用哪種模型。因此，我們可以簡單地談?wù)摂?shù)字計算機的復(fù)雜度，而不是專門描述RAM模型或圖靈機的復(fù)雜度。

4. 超越數(shù)字計算

雖然數(shù)字計算機現(xiàn)在占主導(dǎo)地位，但它們并不是唯一的計算形式。模擬計算機在過去也曾被廣泛研究和使用。與數(shù)字計算機的離散值不同，模擬計算機是基于對連續(xù)變化參數(shù)的精確操作。有時人們聲稱這樣的設(shè)備可以快速解決數(shù)字計算機難以解決的問題。然而，這樣的主張從未實現(xiàn)。模擬計算機的一個主要障礙是無法制造具有任意高精度的設(shè)備。在數(shù)字計算機中，離散化意味著誤差必須相對較大才能被注意到，然后才能實施檢測和糾正這種誤差的方法。然而，在模擬計算機中，誤差可以任意小且無法檢測，但它們的影響仍然可能破壞計算。

如果有人要提出一個理想的計算模型，它可能會尋求將數(shù)字計算機的魯棒性與模擬計算機的微妙操作相結(jié)合。要實現(xiàn)這一點，我們可以求助于量子力學(xué)。我們已經(jīng)看到，量子比特是一個具有離散輸出0和1的系統(tǒng)，但能夠以只能由連續(xù)參數(shù)描述的狀態(tài)存在。這是著名的“波粒二象性”概念的一個特例，是量子系統(tǒng)的典型。它們不能被完全描述為離散或連續(xù)，而是兩者的結(jié)合。正如愛因斯坦所說：

量子計算機的原語操作是應(yīng)用于量子比特的門，因此它既不是模擬的，也不是數(shù)字的，而是獨特的。在后續(xù)章節(jié)中，我們將探討這種獨特性質(zhì)的影響。我們將看到，量子計算機可以解決與數(shù)字計算機完全不同的復(fù)雜性問題。事實上，量子計算是目前已知的唯一能夠在某些任務(wù)上以指數(shù)級速度超過經(jīng)典計算機的技術(shù)，可能會將計算時間從幾年減少到幾分鐘。我們還將探索量子糾錯如何消除任何不完美的影響。

5. 何時使用量子計算機

有了量子比特和量子門，我們可以設(shè)計出與數(shù)字和模擬經(jīng)典算法根本不同的新算法。通過這種方式，我們希望找到經(jīng)典計算機難以解決的問題的解決方案。

其中一種方法是當(dāng)我們想要確定某個函數(shù)的整體性質(zhì)時。例如，如果我們想找到某個參數(shù)$\boldsymbol{x}$的值，使得某個函數(shù)$\boldsymbol{f(x)}$是最小值，或者是周期函數(shù)$\boldsymbol{f(x)}$的周期。數(shù)字計算機上的算法可能使用一個過程，在這個過程中，對各種不同的輸入計算$\boldsymbol{f(x)}$，以便獲得關(guān)于整體性質(zhì)的充分信息。然而，對于量子計算機，我們可以創(chuàng)建疊加態(tài)的事實意味著該函數(shù)可以同時應(yīng)用于許多可能的輸入。這并不意味著我們可以訪問所有可能的輸出，因為對這種狀態(tài)的測量只會給我們一個單一的結(jié)果。然而，我們可以轉(zhuǎn)而尋求誘導(dǎo)量子干涉效應(yīng)，這將揭示我們所需的整體性質(zhì)。

這個一般性的描述說明了許多已經(jīng)被發(fā)現(xiàn)的量子算法的工作原理。一個突出的例子是Grover算法，它將遍歷$\boldsymbol{N}$個元素項的復(fù)雜度從$\boldsymbol{O(N)}$降低到$\boldsymbol{O(N^{1/2})}$。這種平方加速應(yīng)用在許多可以表示為非結(jié)構(gòu)化搜索的任務(wù)中很有用，例如優(yōu)化問題和機器學(xué)習(xí)。

Shor算法獲得了更令人印象深刻的加速比，該算法分析了因數(shù)分解問題的核心周期函數(shù)。這就為一個復(fù)雜度為$\boldsymbol{O(N^3)}$的$\boldsymbol{n}$位數(shù)因數(shù)分解問題提供了量子解決方案。與數(shù)字計算機高于$\boldsymbol{O(e^{n^{1/3}})}$的復(fù)雜度相比，這是一個超多項式級的加速。

另一種使用量子算法的途徑是使用量子計算機解決量子問題。我們將在下一章中看到，表示一個量子態(tài)需要大量的信息，這些信息隨量子比特的數(shù)量呈指數(shù)級增長。因此，隨著$\boldsymbol{n}$的增加，僅寫下$\boldsymbol{n}$個量子比特的狀態(tài)就成為數(shù)字計算機的一項棘手任務(wù)。然而，對于量子計算機來說，我們只需要$\boldsymbol{n}$個量子比特就可以完成相同的工作。這種表達(dá)和操縱量子態(tài)的自然能力使我們能夠研究和更好地理解感興趣的量子系統(tǒng)，如分子和基本粒子。

因此，在不同行業(yè)中應(yīng)用和調(diào)整量子算法，有希望在商業(yè)和科學(xué)中實現(xiàn)顛覆性的用例。 這包括藥物發(fā)現(xiàn)、機器學(xué)習(xí)、材料發(fā)現(xiàn)、期權(quán)定價、蛋白質(zhì)折疊和供應(yīng)鏈方面的突破。3特別有希望的是那些經(jīng)典算法面臨固有的縮放限制，并且不需要加載大型經(jīng)典數(shù)據(jù)集的問題。對于量子優(yōu)勢，給定問題的答案需要強烈依賴于具有結(jié)構(gòu)的指數(shù)級多糾纏自由度，使量子力學(xué)演化為一個解決方案，而不需要經(jīng)過所有路徑。然而，請注意，對量子計算機來說“容易”的問題（可在多項式時間內(nèi)解決）和其他復(fù)雜性理論類之間的精確關(guān)系仍然是一個開放問題。

這只是對量子算法如何以獨特的方式進(jìn)行計算的一個嘗試。關(guān)于這些方法的更多細(xì)節(jié)可以在后面的章節(jié)中找到。但首先我們需要超越單一的量子比特，投入一些時間來理解我們將需要的全套量子門。這是下一章的重點。

6. 參考文獻(xiàn)

1. https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html

2. Albert Einstein, Leopold Infeld (1938). The Evolution of Physics: The Growth of Ideas from Early Concepts to Relativity and Quanta. Cambridge University Press.

3. Quantum computing is coming to your business | IBM

4. https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

5. Image: Cmglee / CC BY-SA (Creative Commons — Attribution-ShareAlike 4.0 International — CC BY-SA 4.0)

關(guān)于Hacker Dōjō?

由Hacker共建的加密、Web3前沿技術(shù)開源知識社區(qū)。Dōjō 會以直播/音頻/文字等形式定期組織分享session, 分享主題主要覆蓋L1和L2的共識算法，架構(gòu)，GitHub repo相關(guān)內(nèi)容，包括不限于以下話題：Scroll / Polygon zkEVM、 Eigen的混合證明系統(tǒng)、Starkware、azTec、 Optimism、Zecrey、Aptos、 Move、密碼學(xué)(零知識證明、公鑰加密、哈希函數(shù)、格密碼) 、 分布式系統(tǒng)、 以太坊協(xié)議棧、 量子計算和量子信息、衛(wèi)星通信系統(tǒng)和航天器系統(tǒng)設(shè)計等。

?Bounty詳情及認(rèn)領(lǐng)進(jìn)度詳情：https://innovative-laser af4.notion.site/174922df15884848b6ac8b57cb4f2fae?v=612e13dc6b9d44dd8197f755abb9fe9c

?加入 Dōjō 中文社區(qū)微信聯(lián)系：@HackerDojo0

有關(guān)DoraHacks

DoraHacks 是一個全球范圍內(nèi)的極客運動，全球黑客馬拉松組織者，也是全球最活躍的多鏈 Web3 開發(fā)者平臺之一。DoraHacks.io平臺使得世界各地的Hacker和開源開發(fā)者可以參與黑客馬拉松、Bounty、Grant、Grant DAO，以及公共物品質(zhì)押等加密原生協(xié)議和基礎(chǔ)設(shè)施進(jìn)行協(xié)作并獲得資助。到目前為止，DoraHacks 社區(qū)的 4000 多個項目已經(jīng)獲得了來自全球行業(yè)支持者超過 3000 萬美元的資助。大量開源社區(qū)、DAO 和 超過50個主要區(qū)塊鏈生態(tài)系統(tǒng)正在積極使用 Dora 的基礎(chǔ)設(shè)（DoraHacks.io）進(jìn)行開源融資和社區(qū)治理。

官網(wǎng)：https://dorahacks.io/