大一下去修了一門量子計算的課，前面的概念跟線性代數有滿多相似的地方，後半部分才真正開始講量子演算法。
量子計算基礎簡介
量子電腦與傳統電腦的差別，在於傳統電腦儲存資訊的最小單位是位元（bit），量子電腦則是使用量子位元（qubit）。位元可以存在一種狀態，1 或是 0。量子位元特別的地方是，它在一個時間，可以同時是 1 也是 0。
量子在通訊上有很高的安全性，利用量子力學原理，能夠在兩方之間安全地分發加密密鑰。任何試圖竊聽的行為都會擾亂量子態，被接收方檢測到。
過去超大整數的質因數分解，即使傳統超級電腦的運算能力也無法在短時間破解。不過，量子演算法（Shor's Algorithm，可解質因數分解）能在合理時間內完成破解，會顛覆現在 RSA 等加密算法。
Classical v.s. Quantum
拆解質數
現在有個數字 ，由 兩個很大的質數構成。破解 RSA 的核心，就是從 找出 和 。
想要找到 的因數，只要不斷給定 ，透過 Euclid's Algorithm（歐幾里得演算法，又稱輾轉相除法）快速計算判斷，當 使得公因數 時，對於 RSA 來說就已經結束了。
但要找到 可以滿足上述條件其實並不容易，事實上真的只能一個一個猜 是多少。不過，我們可以將這個隨機猜測的數字 轉換成很有可能滿足條件的 。
為什麼是 ？
若給定兩個數 ，且 ，則存在一個正整數 使得 ，其中 為某個整數（根據歐拉定理）。
舉兩個例子來說：
Ex1
給定 ，則：
Ex2
給定 ，則：
因此，
將機會不大的數字 g 轉換成很有可能的 ，只要找到這樣的就好（要是偶數才能真正拆解喔！）
Classical
我們用個例子來想，要用傳統電腦找到一個 使得 ，可能會從 開始一個一個慢慢代入判斷，但如果現在給定 的 和 都很大呢？
對傳統電腦來說，就真的只能一個一個數字慢慢算，直到找到答案為止，這也就是為什麼現在能夠這麼廣泛地使用 RSA 加密。但是對量子電腦來說就不太一樣了……
Quantum
用量子來計算的好處是因為有疊加態（superposition）。
我們可以構建一個 的函數。若要計算 各自的函數值，對於傳統電腦來說，就是一個一個代入計算：
但在量子的世界，可以讓一個或多個量子位元處於疊加態：
然後將這個疊加態輸入設計好的 邏輯閘做平行運算，得到：
到這邊還需要先知道另一個 Shor's Algorithm 的核心概念。一樣目標是找到滿足條件的 。如果現在隨便找的一個 ，會得到 ，其中 是餘數，那麼很容易證明 也成立。
換句話說，對於某個週期 ， 模 的餘數會重複出現：
這個「週期性」就是 Shor's Algorithm 能有效率分解質因數的關鍵。只要能找到這個週期 ，就能透過 Quantum Fourier Transform（量子傅立葉變換）進一步拆解 。
前面提到，在量子的世界中，我們可以構建量子閘，讓所有輸入 的餘數 同時被計算出來：
這表示，當量子位元處於疊加態時，經過適當設計的量子閘後，所有 對應的 都會同時存在於量子態中。
從這些餘數當中，任取一個 ，可以經由適當的轉換，將其餘的 都變成 。最後透過 Fourier Transform 找出的 和 ，就可以利用前面提過的傳統方式，判斷 是否與 有公因數，將 拆解開來。
標準的 2048 位元 RSA 加密，就算用目前世界上最強的超級電腦（太湖之光，中國製），花費地球年齡的時間（46 億年）都無法破解。
如果量子電腦真的存在，能將運算時間由數十億年縮減為幾分、幾秒鐘，數字 都能快速被拆解成 兩個質數，現在的金融、通訊等都會受到嚴重的影響。但是現在還不需要擔心，因為目前的技術還沒辦法處理太多位元的數字，可能只能拆解 這種容易的而已。
單量子位系統 (Single-Qubit Quantum Systems)
在量子計算中，量子位元 (Qubit) 是最基本的資訊單位，類似於傳統計算中的位元 (Bit)。然而，與傳統位元只能處於 0 或 1 的狀態不同，量子位元可以同時處於 0 和 1 的疊加態。先來介紹一下量子計算所處於的空間定義：
Hilbert 空間 (Hilbert Space)
對於單量子位元系統，Hilbert 空間是一個複數 中的 inner product space，有向量加法、純量乘法，以及計算向量之間的內積。
If , , then .
在單量子位元系統當中，我們常用, 當作標準基底，而一個量子位元則可表示為 。
至於維度 (Dimension) 為 的向量空間，則會以 當作標準基底，也可以寫成 。
- 正規化 (Normalized)：
- 正交 (Orthogoral)：
因此：
Note：單量子位元系統的 Hilbert 空間是一個 的簡單空間，而複數量子位元系統的 Hilbert 空間維度會隨著量子位元數量增加而指數成長，例如 個量子位元系統的 Hilbert 空間維度為 。
範例
我們拿一個例子來說明好了，假設 , ，那麼可以做下列這幾個運算：
對偶向量 (Dual Vector)
內積 (Inner Product)
因此：
- (non-negative real)
向量範數 (Norm)
正規化向量 (Normalized Vector)
量子態必須是正規化的，以保證測量結果的機率總和為 1。
例如：
計算內積：
投影運算子 (Projection Operator)
此時算出的 和 就分別是 在 和 兩個基底的投影運算子。
崩塌 (Collapse)
我們前面說過， 是由維的基底所組成的。其中 在 出現的機率為 ，則。
在 當中， 出現的機率取決於 ，而此時的觀測是不可逆的。當測量完成後，量子態會崩塌到對應的基底態 ，並且無法回復到原本的疊加態。因此測量過程不可逆，且量子態的疊加性在測量後不復存在。
範例
在 出現的機率為
在 出現的機率為
量子態 (Quantum State)：
經典態 (Classical State)：
量子態在測量後會崩塌到某個基底態，而此時的經典態不再具有量子態的疊加性。
Bloch 球 (Bloch Sphere)
Bloch 球用於表示單量子位的狀態：
Bloch 球上的 I, X, Y, Z 運算子幾何意義
- I (單位運算子)：不改變 Bloch 球上的狀態（即不旋轉）。
- X 門（Pauli-X）：繞 軸旋轉 弧度（180°），將 和 互換。對應於 Bloch 球上的 軸翻轉。
- Y 門（Pauli-Y）：繞 軸旋轉 弧度（180°），將 和 互換，並帶有相位。對應於 Bloch 球上的 軸翻轉。
- Z 門（Pauli-Z）：繞 軸旋轉 弧度（180°），將 和 互換， 不變， 變號。對應於 Bloch 球上的 軸翻轉。
簡單來說，X, Y, Z 分別對應於 Bloch 球上繞 、、 軸的 180° 旋轉。
多量子位系統 (Multiple-Qubit Systems)
Hilbert 空間與張量積 (Tensor Product)
多量子位系統的 Hilbert 空間是單量子位空間的張量積：
假設：
- 第 0 個 ：
- 第 1 個 ：
Tensor Product
而此時：
為 的基底
範例
假設：
- 第 0 個 ：, , operator
- 第 1 個 ：, , operator
計算張量積：
運算子與單元矩陣
在多量子位系統中，運算子 和單位運算子 的結合可以用來描述量子態的演化。假設 和 是作用於不同量子位的運算子，若它們相等，即 ，則可以簡化為單一運算子 的作用。
單位運算子 的作用不會改變量子態，滿足以下關係：
其中，單位運算子 的矩陣形式為：
當運算子 作用於單一量子位的量子態時，可以表示為：
而當運算子 與單位運算子 結合，作用於多量子位系統的張量積態時，則可以表示為：
單位運算子：
單元矩陣 (Unitary Matrix)
假設 ：
則可發現
Note：共軛轉置 (conjugate)
是 Unitary Matrix
量子門與狀態轉換 (Quantum Gates and State Transformations)
常見量子門
的基本運算子為
基本運算子 - X (NOT)
其中：
基本運算子 - Y
其中：
是單元矩陣
基本運算子 - Z
糾纏態與測量
在中，
Bell State （貝爾態）
Bell State 是兩個 qubit 之間最純粹的糾纏態。
假設：
則它們的張量積
如果 ，則為 可分離態；否則為 糾纏態 (entanglement)。
糾纏測量
例如：
此時去做量子測量：
- 第 1 個質點測量到 ，則第 0 個質點就確定為
- 第 1 個質點測量到 ，則第 0 個質點就確定為
逆向計算 (Reverse Computation)
CNOT (Control NOT)
CNOT 門的運作如下：
CNOT 性質：
舉個例子：
 |  |
這是所有計算中最重要的一個運算門，並且可以延伸出 COPY、NOT 和 SWAP 三種操作：
| COPY | NOT | SWAP |
|---|---|---|
 |  |  |
CCNOT (Toffoli Gate)
CCNOT 門的運作如下：
CCNOT 性質：
邏輯運算門
AND
AND 的運作如下：
XOR
XOR 的運作如下：
NAND (NOT AND)
NAND 的運作如下：
NOT
NOT 也可以用 CNOT 的形式來表示：
OR
OR 的運作如下：
範例
以下是量子電路的等價性：
