# 初探量子電腦

## 從bit到qubit

- 古典電腦：使用單純的0和1 (分別代表通路和斷路)
- 量子電腦：使用位元 |0> 及 |1> 以向量的方式表示在Bloch sphere (Hillbert Space) 上面。

一量子位元可以表示成 $|\psi$>$=\alpha|0$>$+\beta|1$> ， 其中|0>代表$\pmatrix {1\\0}$， |1>代表$\pmatrix {0\\1}$
而且 $\alpha,\beta\in \mathbb{C},|\alpha|^2+|\beta|^2=1$ 。於是我們可以設 $\alpha=e^{i\psi}cos\frac{\theta}{2}$、$\beta=e^{i(\psi+\phi)}sin\frac{\theta}{2}$，

得到$|\psi$>$=e^{i\psi}(cos\frac{\theta}{2}|0$>$+e^{i\phi}sin\frac{\theta}{2}$|1>$)$

[課程截圖](https://i.imgur.com/t5c31oP.png)

然而，對於 $e^{i\psi}$ 無法得到觀測結果，因此我們可任意取$\alpha$為實數，剩下兩個自由度：

$\alpha=cos\frac{\theta}{2}$

$\beta=e^{i\phi}sin\frac{\theta}{2}$

其中 $|\alpha|^2$ 以及 $|\beta|^2$ 分別代表 |0> 及 |1> 的機率。

注意：Bloch sphere 只能表示單一位元qubit的狀態，涉及多位元則無法表示(參見Q sphere)

# 基本數學概念

## 內積與正交規一性 (Inner Product & Orthonormality)

cf維基：

*正交是線性代數的概念，是垂直這一直觀概念的推廣。作為一個形容詞，只有在一個確定的內積空間中才有意義。若內積空間中兩向量的內積為0，則稱它們是正交的。如果能夠定義向量間的夾角，則正交可以直觀的理解為垂直。*

### 正交規一性 (Orthonormality)

在線性代數裏，假若，內積空間的兩個向量是互相正交的，並且，兩個向量的範數都是 1 ，則稱這兩個向量互相具有正交規範性，又譯單範正交性、正交歸一性。

## 張量積 (Tensor Product)

範例：

高等數學上，向量空間$b$與$a$的張量積為一被賦予從笛卡爾積進行雙線性映射的向量空間。而在量子位元的計算中，張量積被廣泛運用在量子位元的相乘，用於考慮多個位元的狀態。

基本操作(cf電神林橋毅)：
- $z(|v$>⨂$|w$>$)=(z|v$>)⨂$|w$>$=|v$>⨂$z|w$>
- $(|v_1$>$+|v_2$>)⨂$|w$>$=|v_1$>⨂$|w$>$+|v_2$>⨂$|w$>
- $|v$>⨂$(|w_1$>$+|w_2$>$)=|v$>⨂$|w_1$>$+|v$>⨂$|w_2$>
- $(A$⨂$B)(|v$>⨂$|w$>$)=A|v$>⨂$B|w$>
- $|v$>$^2=|v$>⨂$|v$>
- $|v$>$^k=|v$>⨂$|v$>$...$⨂$|v$>

## 特徵值與特徵向量 (Eigenvalue & Eigenvector)

舉例：考慮一矩陣 $A$ 。如果其特徴向量 $\overrightarrow{v}$ 使得 $A\overrightarrow{v} = \lambda \overrightarrow{v}$ 則稱純量 $\lambda$ 為特徵值。

### 矩陣計算

如果說 $\lambda$ 是矩陣 $A$ 的特徵值，等價於線性系統 $(A-\lambda I) \overrightarrow{v} = 0$ ，也就是說 $det(A-\lambda I)=0$

## 轉置矩陣與么正矩陣

### 轉置矩陣 (Transposition)

設一矩陣為 $A$ ，其轉置矩陣 $A^T$ 為原矩陣 $A$ 的行列互換。

例：

$\pmatrix{1 & 2\\3 & 4}^T = \pmatrix{1 & 3\\2 & 4}$

### 么正矩陣 (Unitary Matrix)

一個么正矩陣 $U$ 滿足以下性質：

$U^*U = UU^* = I_n$

其中 $U^*$ 為 矩陣 $U$ 的共軛轉置矩陣，許多量子邏輯閘具有這項特質。

# 量子位元運算 (Qubit Operation)

## 量子邏輯閘 (Quantum Logic Gate)

### Pauli-X Gate

$X=\pmatrix{0 & 1\\1 & 0}$

對於單一qubit,一個Pauli-X Gate 可以將|0>變成|1>，而將|1>變成|0>。此動作等同於在Bloch Sphere上的X軸上旋轉$\pi$弧度而對應到Z軸上，因此又被稱為"Bit Flip"(類似古典電腦的NOT閘)。

### Pauli-Y Gate

$Y=\pmatrix{0 & -i\\i & 0}$

對於單一qubit,一個Pauli-Y Gate 可以將|0>變成$i$|1>，而將|1>變成-$i$|0>。此動作等同於在Bloch Sphere上的Y軸上旋轉$\pi$弧度。

### Pauli-Z Gate

$Z=\pmatrix{1 & 0\\0 & -1}$

對於單一qubit,一個Pauli-Z Gate 可以將|0>保持不變，而將|1>變成-|1>。此動作等同於在Bloch Sphere上的Z軸上旋轉$\pi$弧度，因此又被稱為"Phase Flip"。

---

Note: $X^2=Y^2=Z^2=-iXYZ=I$

---

### Hadamard Gate

$H=\frac{1}{\sqrt{2}}\pmatrix{1 & 1\\1 & -1}$

對於單一qubit,一個Hadamard Gate 可以將|0>變成$\frac{|0>+|1>}{\sqrt{2}}$而將|1>變成$\frac{|0>-|1>}{\sqrt{2}}$。這意謂著測量的結果得到|0>以及|1>各有一半的機率，也就是在$(\hat x+\hat z)/\sqrt{2}$的軸上旋轉$\pi$弧度。

注意：$H$是一個么正矩陣，也就是說 $HH^\dagger=I$(其他量子邏輯閘也是如此)

### Controlled-Not Gate (CNOT Gate)

$CNOT=\pmatrix{1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0}$

對於兩個qubit，只有當第一個qubit是|1>的時候才會對第二個qubit執行 $NOT$ 的運算，其餘不變。

|q1|q2|q1'|q2'|
|--|--|---|---|
|0 |0 |0 |0 |
|1 |0 |1 |1 |
|0 |1 |0 |1 |
|1 |1 |1 |0 |

### SWAP Gate

$SWAP=\pmatrix{1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1}$

## 量子糾纏 (Quantum Entanglement)


將$|q_0$>加上一個Hadamard閘，再以$|q_0$>為Controlled Qubit，連接$|q_0$>成為 $CNOT$ 閘。最後整個線路變成量子糾纏的狀態，也就是當你知道第一個位元的狀態後，便馬上可以推得第二個位元的狀態。

最簡單的量子糾纏可為 Basic Bell States 的其中一個：





以Hadamard閘與 $CNOT$ 閘產生的糾纏態便是 Basic Bell States 中的 $|\Phi^+$>

# 演算法

## Grover's Algorithm

(圖片來源：維基)

Grover's Algorithm 可以用 $O(\sqrt{N})$ 的時間複雜度來完成一維條目的搜尋。

## Shor's Algorithm

(圖片來源：維基)

Shor's Algorithm 可以用 $O((log{N})^3)$ 的時間複雜度來完成整數的質因數分解。

## Deutch-Josza's Algorithm

(圖片來源：維基)

Deutch-Josza's Algorithm 可以用 $O(1)$ 的時間複雜度來判斷函數為平衡函數還是常數函數。