Last Updated on 2023-02-08 by Clay
加法的複雜性
量子電腦（quantum computer）的優勢在於，它極有可能解決一些傳統電腦所無法解決的問題。為了能夠了解實際上我們到底能使用量子電腦解決哪些問題，我們首先需要了解一個問題究竟具有多複雜的計算量。
首先，我們重新確認一下之前在 1.2 使用量子電路實作半加法器（Half Adder） 中看過的加法過程：
9213
+ 1854
= ????
在把兩個長度為 n 的數值做加總時，我們大概可以假設一共要做 n 次運算：
- 3 + 4
- 1 + 5
- 2 + 8
- 9 + 1
可以看到，在做長度為 4 的數值運算時，一共需要考慮大概 4 次的運算。這樣的情況，我們稱之為 c(n)。
假設最單純的情況就是我們不需要考慮進位（carry）的問題，這樣我們計算的次數就是 n 次；而最糟糕的情況就是我們總共需要考慮 n 次進位。從這些假設中我們可以知道，操作的次數大致上會落在 n <= c(n) <= 2n。
判斷時間複雜度的方法： Big-O
使用 Big-O 的符號表示法，我們可以把上面的複雜度簡單地表示成 c(n) = O(n)，這意味著我們直接描述了該複雜度是『線性』的，而不用描述細節。
簡單來說，無論 c(n) 實際上是 n、2n、3n... 我們都可以稱之為時間複雜度 O(n)。
這裡我們有一個隱藏的假設：當我們談到數字系統時，我們都假設這是一個特定的數字系統，擁有固定的位數，比如說十進制、二進制... 或其他的進制。
所以我們需要考慮不同數字系統的狀況！並保證 Big-O 的敘述對於所有進制都有效果。
從以上式子中我們可以看出，使用二進制的數學系統與十進制的數學系統，他們之間的計算次數存在著線性關係。也就是說，我們在使用 Big-O 時，可以順利兼顧不同的數學系統。
複雜度理論
複雜度理論是我們計算時所需要的『複雜度』相關的研究。好比我們已經很熟悉的『加法』，現在我們已經知道這是一個 O(n) 複雜度的計算了。
相對而言，『乘法』就複雜上許多了。目前我們日常所習慣的乘法運算若以複雜度來表示的話，則通常會寫成 O(n^2)。仔細想想就會知道，跟每個位數相加的加法不同，乘法需要我們把每一位的數值乘上待乘數的每一位，並且最終還要將其加總！
但即便我們認為『乘法』非常複雜，它也仍不為最複雜的計算；比方說，『質因數分解』就是一個遠比乘法更加複雜的計算，複雜度通常可以表示為 O(e^(n^1/3)) 但實際情況可能更糟 —— 質因數分解是一個複雜度呈指數成長的運算。
我們來舉個例子，來看看以下的 829 位數字。
rsa_250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937
如果我們使用手邊的電腦，對這個數字進行加法或是乘法，我們會在不到一秒內得到最終的結果；然而，若是我們要對這個數值做質因數分解，我們可能會需要 2,700 年、甚至更久的時間！
對於太大數值的質因數分解，我們常常需要超級電腦以宇宙年齡的時間為單位進行計算，這是不切實際的。
目前為止我們所考慮的，不外乎是 n 位的數值運算。實際上，無論是圖形渲染、搜尋資料庫、動力學模型、甚至是遊戲 —— 通通都可以使用複雜度理論來估計運算量。在各種情況下，我們都可以使用 Big-O 來表示複雜度。（舉例來說，具有 N 筆資料的資料庫其搜尋複雜度為 O(N)）
超越數值運算
儘管數位計算機（泛指現在的傳統電路電腦）是現在計算裝置的主流，但並非唯一的計算裝置種類。就好比在過去，類比式的計算機也曾經存在過，比方說指南車、算盤、日晷...... 都可以稱為廣義上的計算機。
然而實際上，我想人類一直都在追求完美的計算機，或許融合了類比式計算機和數位計算的理想計算模型是我們所追求的最終結果。這時候，量子力學就出場了。
量子位元（qubit）可以具有確定的 0 和 1 輸出，但又存在著可以使用連續參數描述的狀態，這就是量子系統中著名的『波粒二象性』的特例。這些量子/粒子不能被完全描述為確定或是連續的狀態，而是兩者的綜合。
It seems as though we must use sometimes the one theory and sometimes the other, while at times we may use either. We are faced with a new kind of difficulty. We have two contradictory pictures of reality; separately neither of them fully explains the phenomena...but together they do.
有時候我們必須使用一種理論、但有時候我們又必須使用另外一種。我們似乎存在有兩個相互矛盾的現實，單獨使用一種理論是無法完全解釋這些現象...... 但當我們同時使用這些理論時則可以。
by 愛因斯坦
而量子電腦就是這樣一個特殊的電腦，它的操作是由一些操作閘（gate）來操作量子位元（qubits），所以我們很難把它歸類到類比式或是數位式的電腦，只能認為它是獨特的。在後續的章節中，我們將會看到量子電腦解決數位電腦解決不了的複雜問題 —— 事實上，量子電腦是我們目前已知的唯一一種可以在某些特定任務上計算速度比傳統數位電腦更快的裝置與方法。
量子電腦可以將某些『特定的』複雜任務所需時間，從數年壓縮到數分鐘。當然我們還得面對一些問題，比方說我們需要研究如何進行量子位元的錯誤校正，以消除當前量子系統不完善的影響。
何時使用量子電腦
透過量子位元與量子閘，我們可以設計出與傳統電腦（無論是數位或是類比）截然不同的新型演算法。因此，我們會希望找到傳統電腦無法解決的任務的解決方法。
舉例來說，我們想像以下的場景：
如果我們有某些函數，我們想要確定他們的全域屬性（global property），例如我們想找到一個 x 值在函數 f(x) 時達到最小。
如果是傳統電腦要解決這個問題，最常見的一種做法就是可以『一次次地』嘗試不同的 x 輸入，好用來取得關於最小值的資訊。
但若是由量子電腦來解決這個問題，由於量子電腦中的量子位元具有疊加態，可以同時表示 0 和 1 的狀態，所以可以做到在同一時間多次嘗試不同的 x 輸入！當然，這並不意味著我們可以窮舉、嘗試出所有的 x 值可能性 —— 但是實際上，我們可以試圖誘導量子干涉現象，這或許能讓我們得到想要的解答。
目前許多已發現的量子演算法正是利用了這個特性。比方說 Grover 演算法，它把搜尋 n 個元素、複雜度原為 O(n) 的問題，降低至 O(n^1/2)！這種二次加速（quadratic speedup）在許多應用在非結構化資料的任務上都相當有用，比方說優化問題和機器學習。
Shor 演算法（常被譯為秀爾演算法）則取得了更令人印象深刻的加速。該演算法著眼於解決因式分解的任務，將原先的 O(n^3) 的複雜度降低至了 O(e^(1/3))。
另一種類的量子演算法是使用量子電腦來解決實際存在的量子問題。我們會在下一章節中看到，隨著量子位元數量的成長，需要用來表達量子位元狀態所需要的資訊量會指數型地成長，以致於到後來，光是要紀錄下 n-qubits 的狀態，對於傳統的數位電腦都是一項挑戰。
當然，對於 n-qubits 的問題，量子電腦相對只需要 n 個量子位元就能表達了。這樣我們就能更好地去研究量子系統，比方說原子或是分子。
因此，量子演算法在不同的行業可能都具備顛覆性的案例，其中包括藥物發現、機器學習、材料發現、期權定價、蛋白質折疊和供應鏈方面的突破。
這些特殊的量子演算法我們將在後續的章節中紀錄。不過在接下來的章節中（也就是舊版 textbook 中的第二章節 —— 終於紀錄完了第一章！）我們將不再只是討論單個量子位元，而是會花時間理解完整的量子閘（quantum gates）！