---
title: 量子計算基礎
tags: Quantum Computing
description: 作者:林橋毅
---

本文感謝中原大學**黃琮暐**教授演講以及**SQCS**提供平台
本文中的Exercise若未註明皆出自於
*Michael A. Nielsen & Isaac L. Chuang*的*Quantum Computation and Quantum Information*
[本次課程錄影](https://www.youtube.com/watch?v=o5JdE3KU6Wo)
**先備知識:向量、矩陣、複數、一點點線代、一點點微積分**

# Stern-Gerlach 施特恩-格拉赫實驗

https://www.youtube.com/watch?v=rg4Fnag4V-E

https://zhuanlan.zhihu.com/p/102034180
## 單磁場
首先，這個實驗讓銀原子通過加熱爐(Oven)，再讓這個高溫銀原子通過一個不均勻的磁場，最後投射在屏上。
我們先做一次最簡單的實驗，簡稱單機版好了。
單機版我們將銀原子經過一個方向Z的不均勻磁場(簡稱:$SGz$)，投射在屏上，
在古典預測會像影片中，會隨機散布成一片，所有地方都有可能。

但實驗結果，屏上只出現兩種情況，**向上**與**向下**，證明了原子角動量投影是**量子化**的。
## 雙磁場
接著，將多個磁場裝置連在一起就會發生許多有趣的事。

首先，通過一個$SGz$會得到上下兩個結果，把往下的擋掉只留向上的結果，在通過一個$SGz$，會得到**100%往上**的結果。
## 三磁場
緊接著，讓原子通過$SGz$擋掉下面的，在通過$SGx$的磁場，就是在水平方向放一個磁場，在使原子通過$SGz$，結果會得到**50%向上、50%向下**。

## 解釋現象
加熱的時候 就會產生一個狀態，但是不帶任何座標軸
當我們做出操作後，他就會自動產生出座標軸
我們在實驗中通過$SGz$，他就會出現一個二維的座標軸，
一軸代表向上的結果，一軸代表向下的結果
(之所以垂直，是因為如果是向上就不會是向下)
當我們對他做測量，就是把他在座標軸上的投影量測出來
所以各**50%**

實驗中，當我們把向下的結果遮掉了
就等於在坐標軸中把一軸遮掉
在過一次$SGz$就等於用相同的座標做投影，結果不變

然後我們這次過一個$SGx$，就等於我們用一個新的坐標軸做投影
一樣在遮掉一個(紅色)然後再過一個$SGz$，就等於在用原本那個做投影
結果當然是一樣50%50%
# 原理
- 在量子力學中，用狀態描述物理系統，這個狀態就是向量

- 當我們做一個操作，就可以訂一個座標軸來描述

- 當我們測量，結果就是投影量

- 根據薛丁格方程式($𝑖ℏ \frac{𝜕}{𝜕𝑡}|\psi>=𝐻|\psi>$)，這個$\psi$這個向量，他不是在一個真實空間，而是在一個高維複數空間(Hilbert space)
所以我們需要線性代數
# 符號
* $z^*$:共軛複數 $(1+i)^* = (1-i)$
* $A^*$:共軛複數矩陣 $A=\begin{bmatrix} 1&2 \\ i&1-i \end{bmatrix} ,A^*=\begin{bmatrix} 1& 2 \\ -i&1+i \end{bmatrix}$
* $|\psi>$ = $(a,b)$:使用狄拉克符號表式向量(ket)
* $<\psi|$ = $(a^* ,b^*)$:做共軛複數、轉置共軛複數得到的向量(bra)
* $<\phi|\psi>$: $|\phi>$和$|\psi>$的內積(inner product)
* $|\phi>\bigotimes|\psi>= |\phi>|\psi> = |\phi\psi>$: $|\phi>$和$|\psi>$的張量積
* $\mathbf{A}^\mathrm{T}$ : 轉置矩陣 $A=\begin{bmatrix} 1&2 \\ i&1-i \end{bmatrix} ,\mathbf{A}^\mathrm{T}=\begin{bmatrix} 1& i\\2&1-i \end{bmatrix}$
* $A^†$:轉置矩陣後再共軛$A=\begin{bmatrix} 1&2 \\ i&1-i \end{bmatrix} ,A^†=\begin{bmatrix} 1& -i \\ 2&1+i \end{bmatrix}$
* $<\phi|A|\psi>$:$|\phi>$和$A|\psi>$的內積，也等於，$A^†|\phi>$和$|\psi>$的內積

# 向量的特性
我們把向量寫成一行，如果我們有n個尺度而且是複數空間就可以寫成這樣
這裡的$z$都是複數
$|\psi>=\begin{bmatrix}z_{1} \\z_{2}\\... \\z_{n} \end{bmatrix}$
- 向量加法，n要相同才可以加
$|\psi_1 >+|\psi_2 >=\begin{bmatrix}z_{1}\\...\\z_{n}\end{bmatrix}+\begin{bmatrix}{z_{1}}'\\ {z_{2}}'\\...\\ {z_{n}}'\end{bmatrix}=\begin{bmatrix}z_{1}+{z_{1}}'\\z_{2}+{z_{2}}'\\...\\z_{n}+{z_{n}}'\end{bmatrix}$
- 向量乘上一個常數
$C|\psi>=C\begin{bmatrix}z_{1}\\...\\z_{n}\end{bmatrix}=\begin{bmatrix}Cz_{1}\\ Cz_{2}\\...\\ Cz_{n}\end{bmatrix}$

# 基(basis)
就是向量$\psi$永遠可以寫成$v_i$的線性組合
$|\psi>=\sum_{i}a_i|v_i>$
$|0>=$
## 線性相依(linear dependent)
使得$a_1|v_1>+a_2|v_2>+...+a_n|v_n> = 0$
且只要有任意一個$a_i$ $!=0$就稱為**線性相依**
:::info
Exercise 2.1: (Linear dependence: example) Show that (1,−1), (1, 2) and (2, 1)are linearly dependent.
:::
:::spoiler
$x\begin{bmatrix}1\\-1\end{bmatrix}+y\begin{bmatrix}1\\2\end{bmatrix}+z\begin{bmatrix}2\\1\end{bmatrix} =\begin{bmatrix}0\\0\end{bmatrix}$

$\begin{cases}x+y+2z=0\\-x+2y+z=0\end{cases}$

由上可知x,y,z有無限多組解
所以不必等於0，所以它線性相依
:::

## 線性獨立(linear independent)
反之，使得$a_1|v_1>+a_2|v_2>+...+a_n|v_n> = 0$
且全部的$a_i ==0$就稱為**線性獨立**
:::info
補充Exercise 2.1
:::
:::spoiler
最簡單的想法就是我選了剛好的軸就會是線性獨立。
如果把上述的$z$刪掉，就會是線性獨立的
$x\begin{bmatrix}1\\-1\end{bmatrix}+y\begin{bmatrix}1\\2\end{bmatrix} =\begin{bmatrix}0\\0\end{bmatrix}$

$\begin{cases}&x+y=0\\&-x+2y=0\end{cases}$
這樣就只有唯一一組解
:::
# 線性操作和矩陣
如果$A$作用在向量$|\psi>$上，(A跟$|\psi>$可以是不同維度的ex.光譜線)
我們可以透過上述展開
$A|\psi> = A(\sum_{i}a_i|v_i>)=\sum_{i}a_iA|v_i>$
就會有兩種想法
* A作用在向量上
* A作用在座標軸上(作用在基上)

如果A可以讓向量旋轉，由下圖就可以看出
你要讓$v_1v_2$變成${v_{1}}'{v_{2}}'$，就是讓$|\psi>$旋轉，或者旋轉座標軸
## 包立矩陣(Pauli Matrix)
- $\sigma_0\equiv I\equiv\begin{bmatrix}1&0\\0&1\end{bmatrix}$
- $\sigma_1\equiv \sigma_x\equiv X\equiv\begin{bmatrix}0&1\\1&0\end{bmatrix}$
- $\sigma_2\equiv \sigma_y\equiv Y\equiv\begin{bmatrix}0&-i\\i&0\end{bmatrix}$
- $\sigma_3\equiv \sigma_z\equiv Z\equiv\begin{bmatrix}1&0\\0&-1\end{bmatrix}$
# 內積(inner product)
如果我們看$|v>$和$|\omega>$的內積$<v|\omega>$
* $<v|\sum_{i}\lambda_i|\omega_i> = \sum_{i}\lambda_i<v|\omega_i>$:可以寫成$|\omega>$跟坐標軸的展開
* $<v|\omega> = (<\omega|v>)^*$
* 如果$|v>=0 ,<v|v>=0$:$|v>$:自己和自己內積等於長度平方，所以如果$|v>>=0$長度就會大於等於零
* 如果$<v|w>=0$代表$v$和$w$是垂直的(正交的orthogoanl)
* 如果長度為1，就是單位向量
* 如果$|v> =|w>=1$且$<v|w>=0$，$|v>$和$|w>$就是正交規一的(orthonormal)
:::info
Exercise 2.7: Verify that |w >≡ (1, 1) and |v> ≡ (1, −1) are orthogonal. What are the normalized forms of these vectors?
:::
:::spoiler
$<w|v>=(1,1)\cdot(1,-1)=(1*1)+(1*-1)=0$
因為長度不等於1所以他不是**orthonormal**而是**orthogonal**
>如果要是**orthonormal**，$v$和$w$要是單位向量
>$|{v}'>=\frac{|v>}{\left\|v\right \||}=\frac{|v>}{\sqrt{2}}=\frac{1}{\sqrt{2}}\binom{1}{-1}$
>$|{w}'>=\frac{1}{\sqrt{2}}\binom{1}{1}$
:::
## 施密特正交歸一化
-https://www.youtube.com/watch?v=fYWXtWZ4OY4
假設有兩個向量$w_1$和$w_2$

找出$w_1$的單位向量$v_1$
這個${v_1}$就是$|v_1>\equiv\frac{|w1>}{||w1||}$
如何做出和${v_1}'$垂直的向量${v_2}$ 呢?
先做出$w_2$在$w_1$上的投影，這個投影就是$w_2$和$v_1$的內積$\sum{k}{i=1}<v_i|w_k+1>|v_i>$
這個向量在和$w_2$相減，就可以得到正交過後的$|v_2>$
整理過後並除掉它的長度
可以得到公式
$|𝑣_(𝑘+1)>\equiv\frac{|𝑤_(𝑘+1)> −\sum^{k}_{i=1}<v_i|w_(k+1)>|v_i}{|||w_(𝑘+1)>−\sum_{i=1}^{k}<𝑣_𝑖 |𝑤_(𝑘+1)>|𝑣_𝑖>||}$
二維成立，三度空間同樣的公式也會成立
如果有一個向量$w_3$想像它在$w_1$和$w_2$的平面上
所以如果在多維的也會成立
## 為甚麼要正交規一
$|v>=\sum_{i}v_i|i> |w>=\sum_{i}w_i|i>$
透過向量的表示法，我們可以把內積展開
$<v| = \sum_{i}v_{i}^*<i|>$
$<v|w> = \sum_{i}v_{i}^*<i|\sum_{j}w_j|j>=\sum_{i,j}v_u^*w_j<i|j>$
在這裡可以看到有兩個$\sum$，還有$i,j$，直接展開會很長
還好我是**orthonormal**的，因此要$i==j$成立，$<i|j>$才會有值
所以在這裡$<v|w>$可以整理出以下的東西
$<v|w> =\sum_{i}v_i^*<i|\sum_{j}w_j|j>=\sum_{i,j}v_i^*w_j<i|j>=\sum_iv_i^*w_i=[v_1^* ... v_n^*]\begin{bmatrix}w_1\\ ...\\ w_n\end{bmatrix}$

# 外積(outer product)
如果有一個向量$|v>$ 作用在一個V的空間，向量$|w>$作用在W的空間，外積就是$|w><v|$
如果對他們進行操作就可以變成這樣
$(|w><v|)|\psi>\equiv |w><v|\psi> = <v|\psi>|w>$
如果有一個正交規一(orthonormal)的向量
$|v> = \sum_i|i><i|v> = \sum_<i|v>|i>=\sum_iv_i|i>$

所以如果軸的數量，符合下面的關係式就是**linear independent**
$\sum_i|i><i|=I$
## Application of outer product

:::info
Exercise 2.9: (Pauli operators and the outer product) The Pauli matrices (Figure 2.2 on page 65) can be considered as operators with respect to an orthonormal basis |0>, |1> for a two dimensional Hilbert space. Express each of the Pauli operators in the outer product notation.
:::
:::spoiler
要解這題必須先知道0和1怎麼寫
$|0>=\begin{bmatrix}1\\0\end{bmatrix}$
$|1>=\begin{bmatrix}0\\1\end{bmatrix}$

$|0><0|=\begin{bmatrix}1\\0\end{bmatrix}\begin{bmatrix}1&0\end{bmatrix}=\begin{bmatrix}1&0\\0&0\end{bmatrix}$
$|1><1|=\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0&1\end{bmatrix}=\begin{bmatrix}0&0\\0&1\end{bmatrix}$
寫完你就會發現
$|0><0|+|1><1| = I = \begin{bmatrix}1&0\\0&1\end{bmatrix}$
接著完成X
$|0><1|=\begin{bmatrix}0&1\\1&0\end{bmatrix}$
$|1><0|=\begin{bmatrix}0&0\\1&0\end{bmatrix}$
$X=\begin{bmatrix}0&1\\1&0\end{bmatrix}=|0><1|+|1><0|$
>在量子電腦中
>$X|0>=|1>$
>$X|0>=(|0><1|+|1><0|)|0>$，因為$<0|0>$才有數字$<0|1>$是沒有數字的，因為你是正交歸一的，所以只剩下1
>或者代入上面的公式
>$X=(|0><0|+|0><1|+|1><0|+|1><1|)\begin{bmatrix}0&1\\1&0\end{bmatrix}(|0><0|+|0><1|+|1><0|+|1><1|)$
:::
## 科西不等式(Cauchy-Schwarz inequality)
因為$<a|b>=c <b|a>=c^*$所以$<v|i><i|v>$必定為正
第一個$|i>$basis是$\frac{|w>}{\sqrt{<w|w>}}$，剩下的跟$|w>$垂直
$|1>=\frac{|w>}{||w||}$
上面的比較廣義，在n度空間都會對
高中版:$(x_1x_2+y_1y_2)^2<=(x_1^2+y_1^2)(x_2^2+y_2^2)$
# 特徵值跟特徵向量(Eigenvalue and Eigenvector)
$A$是一個作用在向量$|v>$上
如果有一個A作用在一個向量，但這個向量不變
假設我們的作用用X舉例
$X=\begin{bmatrix}0&1\\1&0\end{bmatrix}$
如果向量$|v>=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}$
$X$作用在$|v>$上不變，所以我們稱這個向量為**Eigenvector**，而他變大變小的值稱為**Eigenvalue**
$A|v> = \lambda|v>$
這裡的$|v>$就是**Eigenvector**，$\lambda$就是**Eigenvalue**

:::info
Exercise 2.11: (Eigendecomposition of the Pauli matrices) Find the eigenvectors, eigenvalues, and diagonal representations of the Pauli matrices X, Y , and Z .
:::
:::spoiler
這裡先只做X
$X|v>=\lambda|v>$
$(X-\lambda I)|v>=0$
$\begin{bmatrix}-\lambda&1\\1&-\lambda\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}=0$

$\begin{cases}-\lambda a+b=0\\a-\lambda b=0\end{cases}$
要無限多組解，用克拉瑪公式解($\Delta=0$)
$\Delta \begin{vmatrix}-\lambda&1\\1&-\lambda\end{vmatrix}=0$
$\lambda^2-1=0$
所以這題的**Eigenvalue**就是$\lambda=1,-1$
把$\lambda$帶回去
$if \lambda =1$
$\begin{bmatrix}-1&1\\1&-1\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}=0$
故$a=b=1$
所以**Eigenvector**為$\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}$
$if \lambda=-1$
$\begin{bmatrix}1&1\\1&1\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}=0$
故$a=-b=1$
所以**Eigenvector**為$\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}$

我們來驗證一下，把$X$作用在Eigenvector上看看
$\begin{bmatrix}0&1\\1&0\end{bmatrix}\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}=1*\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}$

Y
eigenvalue +-1
Z
eigenvalue +-1
:::
# 伴隨矩陣和埃爾米特伴隨(Adjoints and Hermitian operators)
$A^†=(\mathbf{A}^\mathrm{T})^*$
$(AB)^†=B^†A^†$
$(|v>)^†=<v|$

- hermitian or self-adjoint operator$A^†=A$
- Normal operator $A^†A=AA^†$
- Unitary operator $A^†A=AA^†=I$

記住，在所有量子物理和量子計算，所有的操作和測量都是Hermitian或self-adjoint也是Normal也是Unitary的

所以你會發現$AA=I$，等同於在量子電腦的操作中，同一個gate執行兩次都會等於$I$就等於**不做事**
:::info
Exercise 2.17: Show that a normal matrix is Hermitian if and only if it has real eigenvalues.
:::
:::info
Exercise 2.19: (Pauli matrices: Hermitian and unitary) Show that the Pauli matrices are Hermitian and unitary.
:::
# 張量積(Tensor product)
張量積可以幫助你思考多個qubit的狀態
$\begin{bmatrix}1\\2\end{bmatrix}\bigotimes\begin{bmatrix}2\\3\end{bmatrix}=\begin{bmatrix}1*2\\1*3\\2*2\\2*3\end{bmatrix}=\begin{bmatrix}2\\3\\4\\6\end{bmatrix}$

操作:
1. $z(|v>\bigotimes|w>)=(z|v>)\bigotimes|w>=|v>\bigotimes z|w>$
2. $(v_1>+|v_2)\bigotimes |w>=|v_1>\bigotimes |w>+|v_2>\bigotimes|w>$
3. $|v>\bigotimes(|w_1>+|w_2>)=|v>\bigotimes|w1>+|v>\bigotimes|w_2>$
4. $(A\bigotimes B)(|v>\bigotimes|w>)=A|v>\bigotimes B|w>$
5. $|v>^2=|v>\bigotimes|v> |v>^k=|v>\bigotimes|v>...\bigotimes|v>$

如果只有一個qubit
$|0>=\begin{bmatrix}1\\0\end{bmatrix};|1>=\begin{bmatrix}0\\1\end{bmatrix}$
那如果有兩個qubit呢
$|00>=|0>\bigotimes|0>=\begin{bmatrix}1\\0\end{bmatrix}\bigotimes\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}1\\0\\0\\0\end{bmatrix}$
$|01>=|0>\bigotimes|1>=\begin{bmatrix}1\\0\end{bmatrix}\bigotimes\begin{bmatrix}0\\1\end{bmatrix}=\begin{bmatrix}0\\1\\0\\0\end{bmatrix}$
$|10>=|1>\bigotimes|0>=\begin{bmatrix}0\\1\end{bmatrix}\bigotimes\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}0\\0\\1\\0\end{bmatrix}$
$|11>=|1>\bigotimes|1>=\begin{bmatrix}0\\1\end{bmatrix}\bigotimes\begin{bmatrix}0\\1\end{bmatrix}=\begin{bmatrix}0\\0\\0\\1\end{bmatrix}$
回頭看一下內積，以上任兩個內積為0
如果你有兩個qubit，你就是在一個四度空間上

| #qubit | Dimension in complexs space | real sapce |
|:------:| --------------------------- |:----------:|
| 1 | 2 | 4 |
| 2 | 4 | 8 |
| 3 | 8 | 16 |
| 4 | 16 | 32 |
| 5 | 32 | 64 |
| n | $2^n$ | $2^(n+1)$ |

那為甚麼你會學到這顆球呢?
因為你在量子電腦的時候，你的向量一定是單位向量
因為你是單位向量，所以你在描述的時候可以少一軸，表就會變這樣

| #qubit | Dimension in complexs space | real sapce |
|:------:| --------------------------- |:-----------:|
| 1 | 2 | 4-1 |
| 2 | 4 | 8-1 |
| 3 | 8 | 16-1 |
| 4 | 16 | 32-1 |
| 5 | 32 | 64-1 |
| n | $2^n$ | $2^{n+1}-1$ |
:::info
Exercise 2.27: Calculate the matrix representation of the tensor products of the Pauli operators (a) X and Z ; (b) I and X ; (c) X and I . Is the tensor product commutative?
:::
:::spoiler
$\begin{bmatrix}0&1\\1&0\end{bmatrix}\bigotimes\begin{bmatrix}1&0\\0&-1\end{bmatrix}=\begin{bmatrix}0&0&1&0\\0&0&0&-1\\1&0&0&0\\0&-1&0&0\end{bmatrix}$
:::
:::info
Exercise 2.29: Show that the tensor product of two unitary operators is unitary.
:::
:::info
Exercise 2.30: Show that the tensor product of two Hermitian operators is Hermitian.
:::

# Operator functions
:::info
Exercise 2.34: Find the square root and logarithm of the matrix$\begin{bmatrix}4&3\\3&4\end{bmatrix}$
:::
:::info
Exercise 2.35: (Exponential of the Pauli matrices) Let 𝑣 ⃑ be any real, three-dimensional unit vector and θ a real number. Prove that
$exp(i\theta𝑣 ⃑∙𝜎 ⃑)=cos(\theta)O+isin(\theta)𝑣 ⃑∙𝜎 ⃑$
Where $𝑣 ⃑∙𝜎 ⃑=\sum^{3}_{i=1}𝑣 ⃑∙𝜎 ⃑$
:::
# Trace
$tr(A)\equiv\sum_i A_{ii}$
$tr(AB)=tr(BA)$
$tr(A+b)=tr(A)+tr(B)$
$tr(zA)=ztr(A)$
$tr(UAU^ϯ)=tr(UU^ϯA)=tr(A)$
$tr(A|\psi><\psi|)=< \psi|A|\psi>$

# Commutator and anti commutator
:::info
Exercise 2.40: (Commutation relations for the Pauli matrices) Verify the commutation relations
[ X, Y ] = 2 iZ ; [ Y, Z ] = 2 iX ; [ Z, X ] = 2 iY.
:::
:::info
Exercise 2.41: (Anti-commutation relations for the Pauli matrices) Verify the anti-commutation relations
{σi, σj } = 0
:::

-----
# 量子閘

-----
# the revolution of quantum state

# Deutsh Algorithm
處理布林函數(0+0=0,0+1=1,1+0=1,1+1=0)
定函數(f(0)==f(1))，則不定函數

1. 準備兩個qubit
2. 初始狀態為$|10>$
3. 將兩個qubit都套用H-Gate
4. insert Boolean f
5. H first -> measure
if first qubit is|1> (不定函數
if first qubit is|0> (定函數
上x下y
if the f(x) is cnot gate actually cnot is just f(x)=x

| y | x | y' | x' |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |

if the f(x) is I gate Identical actually is f(x)=0

| y | x | y' | x' |
| --- | --- | --- |:---:|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |

這個的意義可以說明古典電腦要做兩次量子只要做一次

# Deutsch-Jozsa
如果有n個位元問題
1. 準備n+1個qubit
2. 初始狀態為|10000...0>
3. 將所有qubit套用H-Gate
4. 放入布林函數$f$
5. 前n個套用H-GATE 如果前n個都是|0> 那就是定函數

| Y X | Y+f(x) X | Y X |
| ---- |:---------:| ---- |
| 0 00 | 0+1 00 | 1 00 |
| 0 01 | 0+1 01 | 1 01 |
| 0 10 | 0+1 10 | 1 10 |
| 0 11 | 0+1 11 | 1 11 |
| 1 00 | 1+1 00 | 0 00 |
| 1 01 | 1+1 01 | 0 01 |
| 1 10 | 1+1 10 | 0 10 |
| 1 11 | 1+1 11 | 0 11 |

這個最大的意義就是superposition的意義
等於一次把所有狀態丟進去，這個例子量子電腦只需要做一次

# 如何設計一個演算法

1. 向量的思維 - 對應到薛丁格方程式
2. 矩陣的思維 - 對應到海森堡矩陣力學
3. 物理/數學思維出發 - 傅立葉轉換、Path intergral

向量:
* 放大縮小 -> 在完美量子計算中，機率和為1
* 旋轉 -> 很常用
* 反射 -> Grover's重要啟發
* 內積 -> 測量的意義
* 張量積 -> 多個量子位元

# Grover's algorithm
Grover's Problem:
有n個物品，有1個是我要的，如何快速找到
有n個物品，有k個是我要的，如何快速找到

這種在遍歷問題，在古典電腦中最差就是$O(n)$，但在量子電腦中最差就是$O(\sqrt{n})$

因為在量子電腦中假設你有10個qubit，就會有1024個互相垂直的軸

那我們就把要得放一個軸剩下都在不同軸

利用疊加態，一次將所有物品放入(n個)
如過n>>k 就會靠近不要的軸
將這個疊加態對不要的軸反射
利用Oracle做反射
再對原本的疊加態反射，則可以快速靠近要得軸
所以，理論上如果只要n個找1個，只要做$\sqrt{n}$次

Code:


1. 準備$lon_{2} n$個qubit
2. 將所有qubit做H操作
3. 加入Oracle 就是對不要的態向量做反射，也可以看成要得態加一個富號
4. 加入Grover's操作

## 範例
1. 四個範例找一個|00>

2. 八個狀態找到|111>

3. 八個狀態找到|101>

# 傅立葉轉換

## 三角函數

sin 奇函數
cos 偶函數

$y=sin x$ is odd function
$y=cos x$ is even function

## 正交特性

積分一個週期都是0
從-pi 積到pi k是整數大於0 都是零

k>1 k in 整數
從pi積分到-pi都是0

cos sin 都是0
coscos k==k ==pi
sin sin k==k pi
sinxcos==0

## 對任一周期函數 都可以用sinkx+coskx表示

![Uploading file..._7hmyfxpzr]()

## 求$a_n$

## 範例

## 函數定義
f(-x)=-f(x) -- odd fountion
對稱原點

# Introduction to Shor's
$if X^{2a} = Nk +1$
$then X^{2a}-1 = Nk$
因此如果我們想要分解N我們需要找到a使$X^2a mod N=1$