# 量子演算法
[Colab Implementation](https://colab.research.google.com/drive/1YVZkxclImURvc_W8mBJRzfzkWGJcNBFv?usp=sharing)

## 量子計算
- 
- Qubit ： 疊加狀態，呈現機率分布，可用量子物理的某些特性實現
- Quantum Gates ： Unitary 矩陣，改變 Qubit 的機率分布
- Measurements ： 觀測每個 qubit 使其 collapse 到其中一狀態
- 量子演算法本身，設計 Quantum Gates 使得觀測到答案的機率最大化

## 向量空間
- 線性代數考慮的問題大約分成兩大類
- 1.$R^n$ 當中的子空間(平直物件)
- 用基底看
- 用線性方程式的解看
- 2.子空間和子空間之間的轉換關係
- 可以表示成一個矩陣
- 我們考慮是 over $\mathcal{C}$ 的向量空間 $V_\mathcal{c}$
- 給定向量 $u,v$ 給定純量 $c,d$
- (0) $u+v\in V$、$cu\in V$
- (1) $u+v=v+u$
- (2) $(u+v)+w=u+(v+w)$
- (3) $\exists~0\in V$, $0+v=v$
- (4) $\forall~u$, $\exists~(-u)$, $u+(-u)=0$
- (5) $c(u+v)=cu+cv$
- (6) $(c+d)u=cu+du$
- (7) $c(du)=(cd)u$
- (8) $1u=u$
- 矩陣：
- Symmetric： $A^T=A$
- Hermitian： $A^*=A$
- Unitary： $A^*A=I_n$
- nonsingular 矩陣：下列敘述等價，都可作為定義
- (1) $rank(A) = \#pivots = n$
- (2) $A \mathbb{x} = \mathbb{b}$ 有唯一解
- (3) $A \mathbb{x} = \mathbb{0}$ 只有 $\mathbb{0}$ 解
- (4) $A^{-1}$ 存在
- (5) $det(A) \ne 0$
- (6) $\{A_1,~...,~A_n\}$ is a basis for $\mathcal{R}^n$
- (7) $\{\mathbb{a}_1,~...,~\mathbb{a}_n\}$ is a basis for $\mathcal{R}^n$
- (8) $N(A) = Ker(T_A) = \{ \mathbb{0} \} ~\iff~ T_A:\text{one to one}$
- (9) $I_m(A) = I_m(T_A) = \mathcal{R}^n ~\iff~ T_A:\text{on to}$
- (10) $0$ 不是 eigen value
- 可逆矩陣：
- 定義：$\exists~E$, $EA=EA=I_n$
- (1) $\Leftrightarrow$ nonsingular
- (2) $EA=I~\Rightarrow~AE=I$
- 基底和維度
- 對每個子空間而言，可以由 $k$ 個線性獨立的向量所張出
- 則維度為 $k$， 這 $k$ 個線性獨立的向量形成一組基底

## 線性轉換
- $V$ 維度 $n$，$W$ 維度 $m$
- $T:V\rightarrow W$ 是 linear
- $T(u+v)=T(u)+T(v)$
- $T(au)=aT(u)$
- 只要決定好 $V$ 的基底對應到誰，即決定好 $T$
- $L(V,W)=Hom(V,W)=\{~T~|~T:V\rightarrow W~\text{linear}~\}$
- (1) $T(0_v)=0_w$
- (2) $L(V,W)$ 是一個向量空間 (搭配正常函數定義)
- (3) $L(V,W)$ 維度是 $nm$
- 基底為 $\{T_{ij}\}$ ，其中 $T_{ij}(v_j)=w_i$
- (4) 子空間
- $I_m(T)\lhd W$
- $K_{er}(T)\lhd V$
- $K_{er}(T)=\{0\}~~\Leftrightarrow~~T:\text{1 to 1}$
- (5) $dimV=dimW=n~\rightarrow~V\cong W$
- (6) $L(V,W)\cong M_{m\times n}$
- $T \Leftrightarrow A=[T(e_1) T(e_2) ... T(e_n)]$
- $T(x)=Ax$
- Dual Space ： $\widehat{V}=L(V,\mathcal{C})$
- 維度為 $n$
- $V\cong \widehat{V}$
- 裡面的每一個函數，稱為線性泛函
- 舉例：
- $T=\begin{bmatrix}2 & 1\\1 & 3\end{bmatrix},~~~T(\begin{bmatrix}1\\0\end{bmatrix})=\begin{bmatrix}2\\1\end{bmatrix},~~~T(\begin{bmatrix}0\\1\end{bmatrix})=\begin{bmatrix}1\\3\end{bmatrix}$
- 原座標的 $(1,0)$ 被對應到原座標的 $(2,1)$
- 新座標的 $(1,0)$ 等同於原座標的 $(2,1)$
- $T=2T_{11}+1T_{21}+1T_{12}+3T_{22}$
- $T_{11}:\begin{bmatrix}1\\0\end{bmatrix}~\rightarrow\begin{bmatrix}1\\0\end{bmatrix}$
- $T_{21}:\begin{bmatrix}1\\0\end{bmatrix}~\rightarrow\begin{bmatrix}0\\1\end{bmatrix}$
- $T_{12}:\begin{bmatrix}0\\1\end{bmatrix}~\rightarrow\begin{bmatrix}1\\0\end{bmatrix}$
- $T_{22}:\begin{bmatrix}0\\1\end{bmatrix}~\rightarrow\begin{bmatrix}0\\1\end{bmatrix}$
- 座標變換
- 在原座標有一個轉換 $A$，在新座標想要找一個等價的 $A'$
- $A'=P^{-1}AP$
- $P$ 是把新座標變成原座標的轉換矩陣，以上例來說是 $\begin{bmatrix}2 & 1\\1 & 3\end{bmatrix}$
- $P^{-1}$ 是把原座標變成新座標的轉換矩陣
- 矩陣對角化
- 若給定 $A_{n\times n}$，以及 $Av_1=\lambda_1v_1$， ... ， $Av_n=\lambda_nv_n$
- 令 $P=[v_1,~...~,~v_n]$
- $P^{-1}AP=\begin{bmatrix}\lambda_1 & & \\ & \lambda_2 & \\ & & \lambda_n\end{bmatrix}$

## 內積空間
- 一個向量空間加上一個內積運算 $(V,\langle .\rangle)$
- (0) $\langle u,v\rangle\in \mathcal{C}$
- (1) $\langle u,v\rangle = \overline{\langle v,u\rangle}$
- (2) $\langle u,u\rangle\ge 0$ 且 $\langle u,u\rangle= 0\Leftrightarrow u=0$
- (3) $\langle u,av+bw\rangle=a\langle u,v\rangle+b\langle u,w\rangle$ 右線性
- 定義：
- Norm ： $||u||=\sqrt{\langle u,u\rangle}$
- Orthogonal ： $u\perp v \Leftrightarrow \langle u,v\rangle = 0$
- Orthonormal ： $\{v_1,..,v_n\}$ 同時是 normal 而且 orthogonal
- Hilbert Space ： 有限維向量空間
- Orthogonal Complement ： $W\lhd V$ 則 $W^{\perp}=\{v\in V~|~v\perp w,~\forall~w\in W\}$
- 定理：
- (1) $\langle u,v\rangle\in \mathcal{R}$
- (2) $\langle au+bv,w\rangle=\bar{a}\langle u,w\rangle+\bar{b}\langle v,w\rangle$
- (3) $||au||=|a|~||u||$
- (4) $|\langle u,v\rangle|\le||u||~||v||$ Schwartz 不等式
- (5) $||u+v||\le||u||+||v||$ 三角不等式
- (6) $W^{\perp}\lhd V$
- (7) $\{v_1,~...,~v_k\}$ 是 orthonormal basis
- 則 $w=a_1v_1+...+a_kv_k$ $\Rightarrow$ $a_i=\langle v_i,w\rangle$
- (8) Hilbert Space 存在 Orthonormal Basis (Gram Schmidt)
- (9) $\langle u,Av\rangle=\langle A^*u,v\rangle$ Cross the Product
- 定理：(1)(2)(3) 任兩個成立 $\Rightarrow$ 第三個成立, $A_{n\times n}$
- (1) unitary : $AA^*=I$
- (2) involution : $AA=I$
- (3) Hermitian : $A^*=A$
- 定理：$U_{n\times n}=[u_1,...,u_n]$，以下敘述等價
- (1) (unitary) $UU^*=I$
- (2) (各行/列 orthonormal) $\{u_1,...,u_n\}$ orthonormal
- (3) (保積) $\langle Ux,Uy\rangle=\langle x,y\rangle$
- (4) (保長) $||Ux||=||x||$
- (5) (保角)
- 定理：Spectral Theorem $A^*=A$
- (1) all eigen values $\in R$
- (2) $Ax=\lambda x$，$Ay=\mu y$
- 若 $\lambda\ne\mu$ 則 $x\perp y$
- (3) 存在 orthonormal eigen basis $\{u_1,...,u_n\}$
- (4) $A=P\Lambda P^*=\begin{bmatrix}u_1~u_2~...~u_n\end{bmatrix}\begin{bmatrix}\lambda_1 & & \\ & \lambda_2 & \\ & & \lambda_n\end{bmatrix}\begin{bmatrix}u_1^*\\u_2^*\\..\\u_n^*\end{bmatrix}$
- $=\lambda_1u_1u_1^*+\lambda_2u_2u_2^*+...+\lambda_nu_nu_n^*$

## Hilbert Space
- $(\mathcal{H}_n,+,．,\langle．,．\rangle)$
- $\mathcal{H}_n=\{a_0|0\rangle+...+a_n|n\rangle~|~a_i\in\mathcal{C}\}$
- $B_n=\{|0\rangle,~|1\rangle,~...,~|n\rangle\}$
- 向量：$|u\rangle=a|0\rangle+b|1\rangle+c|2\rangle=\begin{bmatrix}a\\b\\c\end{bmatrix}$，$|v\rangle=x|0\rangle+y|1\rangle+z|2\rangle=\begin{bmatrix}x\\y\\z\end{bmatrix}$
- 加法：$|u\rangle+|v\rangle=(a+x)|0\rangle+(b+y)|1\rangle+(c+z)|2\rangle$
- 係數乘法：$2|u\rangle=2a|0\rangle+2b|1\rangle+2c|2\rangle$
- 內積：$\langle u|v\rangle=\langle u,v\rangle=\bar{a}x+\bar{b}y+\bar{c}z$
- 外積：$|u\rangle\langle v|=\begin{bmatrix}a\bar{x} & a\bar{y} & a\bar{z}\\b\bar{x} & b\bar{y} & b\bar{z}\\c\bar{x} & c\bar{y} & c\bar{z}\end{bmatrix}$
- 張量積：$|uv\rangle=|u\rangle\otimes|v\rangle=\begin{bmatrix}ax\\ay\\..\\cz\end{bmatrix}_{9*1}$
- 對偶 dual：
- 對偶向量：$\langle u|=\begin{bmatrix}\bar{a}&\bar{b}&\bar{c}\end{bmatrix}$ 是 $|u\rangle$ 的對偶向量
- bra：長相如 $\langle u|=\begin{bmatrix}\bar{a}&\bar{b}&\bar{c}\end{bmatrix}$ 的對偶向量
- ket：長相如 $|u\rangle=\begin{bmatrix}a\\b\\c\end{bmatrix}$ 的向量
- 對偶空間：$\hat{\mathcal{H}_3}=L(\mathcal{H}_3,\mathcal{C})$ 是 $\mathcal{H}$ 的對偶空間
- 每個 $f\in\hat{\mathcal{H}_3}$，存在唯一的對偶向量 $\langle u_f|$
- $f(|x\rangle)=\langle u_f|x\rangle$

## Tensor Product $\otimes$
- 左邊的為主，把右邊的放到左邊
- $\begin{bmatrix}a\\b\end{bmatrix}\otimes\begin{bmatrix}c\\d\end{bmatrix}=\begin{bmatrix}ac\\ad\\bc\\bd\end{bmatrix}$
- $\begin{bmatrix}a&b\\c&d\end{bmatrix}\otimes\begin{bmatrix}e&f\\g&h\end{bmatrix}=\begin{bmatrix}ae&af&be&bf\\ag&ah&bg&bh\\ce&cf&de&ef\\cg&ch&dg&dh\end{bmatrix}$
- Tensor Product 的概念，是把兩個物件擺在一起 (Cartisian Product) 而不作任何運算
- 但是因為這樣對應的函數是雙變數，為了將其變成單變數，因此做乘法運算
- 
- Tensor Product 的性質 (矩陣、向量)：
- (1)
- $A\otimes (aB+bC)=a(A\otimes B)+b(A\otimes C)$
- $(aA+bB)\otimes C=a(A\otimes C)+b(B\otimes C)$
- (2) $(A\otimes B)\otimes C=A\otimes (B\otimes C)$
- (3) $(A\otimes B)(C\otimes D)=(AC)\otimes(BD)$
- (4)
- (i) $\overline{A\otimes B}=\overline A\otimes \overline B$
- (ii) $(A\otimes B)^T=A^T\otimes B^T$
- (iii) $(A\otimes B)^*=A^*\otimes B^*$
- (iv) $(A\otimes B)^{-1}=A^{-1}\otimes B^{-1}$
- (5) $I_n\otimes I_n=I_{mn}$
- (6) $A、B$ 是 unitary $~~\Rightarrow~~$ $AB、A\otimes B$ 也是
- (7) $A\otimes B\ne B\otimes A$
- (8) $||x\otimes y||=||x||~||y||$

## Tensor Product Of Hilbert Space
- 給定
- $U$ 是 Hilbert Space，Orthonormal Basis 為 $\{u_1,...,u_m\}$
- $V$ 是 Hilbert Space，Orthonormal Basis 為 $\{v_1,...,v_n\}$
- $U\otimes V=span(~\{u_i\otimes v_j\}_{1\le i\le m,~1\le j\le n}~)$
- $\{u_i\otimes v_j\}_{1\le i\le m,~1\le j\le n}$ 是 Orthonormal Basis
- $dim(U\otimes V)=mn$
- $(U\otimes V)\otimes W\cong U\otimes (V\otimes W)\equiv U\otimes V\otimes W$
- 舉例而言：
- $\mathcal{H}_2=span(~\{|0\rangle,~|1\rangle\}~)=span(~\{\begin{bmatrix}1\\0\end{bmatrix},~\begin{bmatrix}0\\1\end{bmatrix}\}~)$
- $\mathcal{H}_2\otimes \mathcal{H}_2\cong\mathcal{H}_4$
- $=span(~\{|00\rangle,~|01\rangle,~|10\rangle,~|11\rangle\}~)$
- $=span(~\{|0\rangle,~|1\rangle,~|2\rangle,~|3\rangle\}~)$
- $=span(~\{\begin{bmatrix}1\\0\\0\\0\end{bmatrix},~\begin{bmatrix}0\\1\\0\\0\end{bmatrix},~\begin{bmatrix}0\\0\\1\\0\end{bmatrix},~\begin{bmatrix}0\\0\\0\\1\end{bmatrix}\}~)$
- 存在 $x=\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{\sqrt{2}}|11\rangle$
- $x\in \mathcal{H}_2\otimes \mathcal{H}_2$
- $x\ne (a|0\rangle+b|1\rangle)\otimes(c|0\rangle+d|1\rangle)$

## Postulate Of Quantum Mechanics
- <font color="#3385FF">(1) State Space Postulate</font>
- The state of a closed quantumn system is described by a Hilbert Space $\mathcal{H}$
- A pure state of the system is described by a unit vector $|v\rangle\in\mathcal{H}$
- `State = 單位向量`
- <font color="#3385FF">(2) Evolution Postulate</font>
- The time-evolution of the state of a closed quantumn system is described by a unitary operator $\mathcal{U}$.
- If the initial state is $|v_1\rangle$, then after the evolution, the state of the system will be $|v_2\rangle=\mathcal{U}|v_1\rangle$
- `Quantom gate = Unitary 矩陣`
- <font color="#3385FF">(3) Measurement Postulate</font>
- Quantumn system state space $\mathcal{H}$, orthonormal basis $\mathcal{B}=\{|u_1\rangle,...,|u_n\rangle\}$. A Con Neuman measurement on system with state $|v\rangle=\sum\alpha_i|u_i\rangle\in\mathcal{H}$ outputs $i$ with probability $|\alpha_i|^2$ and leaves the system in state $|v_i\rangle$
- Measurement $=\{M_1,...,M_n\},~M_i\in \mathcal{H}^*,~\sum M_i^*M_i=I_n$. After measurement, system in state $|v_i\rangle=\frac{M_u|u\rangle}{\sqrt{p_i}}$ with probability $P_i=||M_i|u\rangle||^2=\langle uM_i^*M_i|u\rangle$
- `觀測機率=係數平方`
- `觀測即失去量子特性`
- <font color="#3385FF">(4) Composition of System Postulate</font>
- Two systems (state space $\mathcal{H}_1,\mathcal{H}_2$) are treated as one combined system. The state space of the combined system is $\mathcal{H}=\mathcal{H}_1\otimes\mathcal{H}_2$
- System 1 in state $|u_1\rangle$，System 2 in state $|u_2\rangle$, then combined system in state $|u_1\rangle\otimes|u_2\rangle\in \mathcal{H}$
- n systems: $\mathcal{H}=\mathcal{H}_1\otimes\mathcal{H}_2\otimes...\otimes\mathcal{H}_n$
- `用 tensor product 來增加維度`
- 糾纏態
- `Non-Entangled State` : 可以拆成不同 Quantum bit 做 tensor product
- e.g. $\frac{1}{\sqrt{2}}(|00\rangle+|10\rangle)$
- `Entagled State` : 不可拆成 Quantum bit 做 tensor product
- e.g. $\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$ → 
- `量子不可克隆定理`：不存在 assignment 的 quantum gate
- 不存在 $T$ 使得 $T(|u\rangle\otimes|e\rangle)=|u\rangle\otimes|u\rangle$
- $T(\frac{|0\rangle+|1\rangle}{\sqrt 2}\otimes|e\rangle)$
- (1) $=T(\frac{|0\rangle+|1\rangle}{\sqrt 2}\otimes \frac{|0\rangle+|1\rangle}{\sqrt 2})=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$
- (2) $=\frac{1}{\sqrt 2}T(|0\rangle\otimes|e\rangle)+\frac{1}{\sqrt 2}T(|1\rangle\otimes|e\rangle)=\frac{1}{\sqrt 2}(|00\rangle+|11\rangle)$
## Quantum Gate
- Quantum Gate $\Leftrightarrow$ Unitary 矩陣
- 定義
- (1) $U^*U=I$
- (2) $U$ 的行向量是 orthonormal basis
- (3) $U$ 保長， $||Ux||=||x||$
- (4) $U$ 保積， $\langle Ux,Uy\rangle=\langle x,y\rangle$
- 性質
- (1) 以下任二成立 $\Rightarrow$ 第三成立
- (a) (Unitary) $A^*A=I$
- (b) (Involution) $AA=I\Leftrightarrow A=A^{-1}$
- (c\) (Hermitian) $A=A^*$
- (2) 若 $A$ 是 Quantum Gate
- $A=A^*\Leftrightarrow AA=I\Leftrightarrow A=A^{-1}$
- (3) $A,B$ 是 unitary $\Rightarrow$ $A\otimes B$ (並聯)、$AB$ (串聯) 也是 unitary
- (4) 若 $A:\mathcal B\rightarrow \mathcal B$，其中 $\mathcal B$ 是 $\mathcal H$ 的一組 orthonormal basis
- (a) $A$ : one to one $\Rightarrow$ $A$ : onto $\Rightarrow$ A : unitary
- (b) $A^2=I$ $\Rightarrow$ $A$ : one to one $\Rightarrow$ A : unitary
- 基本 Quantum Gate
- Hadamard
- Pauli-X = Not
- Pauli-Y = (0 i -i 0)
- Pauli-Z = $R_{\pi}$
- $S=R_{\pi/2}$
- $T=R_{\pi/4}$
- Swap
- Controlled Not
- Toffoli = CCNOT
- 常見的 Quantum Gates
- $H\otimes H$
- $|00\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$
- $H\otimes H\otimes H$
- $|000\rangle=\frac{1}{2\sqrt 2}(|000\rangle+|001\rangle+|010\rangle+|011\rangle+|100\rangle+|101\rangle+|110\rangle+|111\rangle)$
- $CNOT(H\otimes I)$ 產生 entangled Bell State
- $|0y\rangle\Rightarrow\frac{1}{\sqrt 2}(|0y\rangle+|1\bar{y}\rangle)$
- $|1y\rangle\Rightarrow\frac{1}{\sqrt 2}(|0y\rangle-|1\bar{y}\rangle)$
- Quantum Gates 的`重要`性質:
- $|0,x\rangle-|1,x\rangle~=~(-1)^x(|0\rangle-|1\rangle)$
- $H^{\otimes n}|0\rangle=\frac{1}{\sqrt {2^n}}\sum\limits_{y\in B_n} |y\rangle$
- $H^{\otimes n}|x\rangle=\frac{1}{\sqrt {2^n}}\sum\limits_{y\in B_n} (-1)^{x\cdot y}|y\rangle$
- Quantum Gates 的其他性質
- Universal Quantum Gates : 可以組出所有 unnitary 轉換
- (1) $\{\text{all 1 qubit gates}\}\cup\{CNOT\}$: universal
- (2) $\{CNOT,H,T\}$: 近似 universal
- (3) $\{CNOT,H,S,CCNOT\}$: 近似 universal
- (4) $\{H,CCNOT\}$: 近似 universal 對 orthogonal 轉換
- `(5)` $\{CCNOT\}$: universal 對 boolean f
- 因為 $|x,y,1\rangle\Rightarrow|x,y,\neg(x\land y)\rangle$
- $HXH=Z$、$HZH=X$
- $XZX=-Z$、$ZXZ=-X$
- $H^{\otimes 2}CNOT_{(c,t)}H^{\otimes 2}=CNOT_{(t,c)}$
- `實作量子黑箱` BlackBox $U_f$
- 給定一個 $f:B^n\rightarrow B^m$，實作 $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$
- 任何 boolean function 都可以用 quantum circuit 實作 BlackBox $U_f$
- 
- (1) $U_f:basis~\rightarrow basis$
- (2) $U_f^2=I$
- (3) 可以用 $CCNOT$ 和輔助位實作
- (4) $U_f:Unitary、Involution、Hermitian$
- (5) `Goal of Quantum Algorithms`:
- Given $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$ where $f$ promises property $P$.
- Design a quantum circuit to find $P$.
- (6) 
- (1) `Deutsch-Jozsa`: $f:B^n\rightarrow B$，問 $f$ constant or balanced
- (2) `Grover`: $f:B^n\rightarrow B$, $f(x_0)=1$，問 $x_0$
- (3) `Bernstein-Varizani`: $f:B^n\rightarrow B$，$f(x)=ax$，問 $a$
- (4) `Simon`: $f:B^n\rightarrow B^n$，$f(x)=f(x\oplus a)$，問 $a$
## Deutsch Algorithm
- 給定一個 $U_f$，決定裡頭的布林函數 $f$ 是 balanced 還是 constant
- (1) $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$
- (2) $f:~\{0,1\}\rightarrow \{0,1\}$
- 
- `U_f` 搭配 $|-\rangle$ 可用做 `Phase Kickback`
- $|x\rangle\otimes(|0\rangle-|1\rangle)~~\Rightarrow~~(-1)^{f(x)}~|x\rangle~(|0\rangle-|1\rangle)$
- $f(x)=0$: $~~|x\rangle|-\rangle~~\Rightarrow~~~~~~~|x\rangle|-\rangle$
- $f(x)=1$: $~~|x\rangle|-\rangle~~\Rightarrow~~-|x\rangle|-\rangle$
- 傳統上 call oracle 2 次，這裡只要 call oracle 一次
- 觀測結果
- 若 $f$ 是 constant: $|+-\rangle~~\Rightarrow~~\pm|+-\rangle$，觀測到 $|0\rangle$
- 若 $f$ 是 balanced: $|+-\rangle~~\Rightarrow~~\pm|--\rangle$，觀測到 $|1\rangle$
## Deutsch-Jozsa Algorithm
- 給定一個 $U_f$，決定裡頭的布林函數 $f$ 是 balanced 還是 constant
- (1) $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$
- (2) $f:~\{0,1\}^n\rightarrow \{0,1\}$
- 
- 演算法:
- $|0\rangle^{\otimes n}~~|1\rangle$
- $H^{\otimes n+1}~\Rightarrow~\frac{1}{\sqrt {2^n}}\sum\limits_x|x\rangle~~|-\rangle$
- $U_f~~~~\Rightarrow~\frac{1}{\sqrt {2^n}}\sum\limits_x(-1)^{f(x)}|x\rangle~~|-\rangle$
- $H^{\otimes n}~\Rightarrow~\frac{1}{2^n}\sum\limits_x(-1)^{f(x)}(\sum\limits_y(-1)^{x\cdot y}|y\rangle)~~|-\rangle=\frac{1}{2^n}\sum\limits_y\sum\limits_x(-1)^{x\cdot y+f(x)}|y\rangle~~|-\rangle$
- 特定 $|y\rangle$ 的係數為 $\frac{1}{2^n}\sum\limits_x(-1)^{x\cdot y+f(x)}$，考慮觀測 $|0\rangle$
- 若 $f$ 是 constant: 係數為 $\frac{1}{2^n}\sum\limits_x(-1)^{f(x)}=1$
- 若 $f$ 是 balanced: 係數為 $\frac{1}{2^n}\sum\limits_x(-1)^{f(x)}=0$
- 觀測結果
- 若 $f$ 是 constant: 觀測到 $|0\rangle$ 機率為 1
- 若 $f$ 是 balanced: 觀測到 $|0\rangle$ 機率為 0

## Grover Algorithm (Quantum Search)
- 給定一個 $U_f$，找出布林函數 $f$ 取值為 1 的 input
- (1) $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$
- (2) $f(x):\left\{
\begin{aligned}
1 & & x = x_0 \\
0 & & x \ne x_0 \\
\end{aligned}
\right.$
- 
- 演算法:
- $|0\rangle^{\otimes n}~~|1\rangle$
- $H^{\otimes n+1}~\Rightarrow~\frac{1}{\sqrt{2^n}}\sum\limits_x|x\rangle~~|-\rangle$
- $G^{k}~\Rightarrow~|x_0\rangle~~|-\rangle$
- 觀測結果
- 觀測到 $|x_0\rangle$ 機率為 1
- 觀測到其他機率為 0
- Components 說明
- (1) $|\psi\rangle=\begin{pmatrix}\frac{1}{\sqrt n}\\...\\ \frac{1}{\sqrt n}\end{pmatrix}=\begin{pmatrix}cos\theta\\sin\theta\end{pmatrix}$，$\langle\psi|=\begin{pmatrix}\frac{1}{\sqrt n}~...~\frac{1}{\sqrt n}\end{pmatrix}=\begin{pmatrix}cos\theta~~ sin\theta\end{pmatrix}$
- (2) $2|0^n\rangle\langle 0^n|-I_n$
- $\left\{
\begin{aligned}
|x\rangle & & x = 0^n \\
-|x\rangle & & x \ne 0^n \\
\end{aligned}
\right.$
- (3) $2|\psi\rangle\langle\psi|-I_n$ : `Grover Diffusion Gates`
- $H^{\otimes n}~(~2|0^n\rangle\langle 0^n|-I_n~)~H^{\otimes n}$
-  
- $\sum\limits_k a_k|k\rangle~~\Rightarrow~~2\frac{1}{\sqrt N}\sum\limits_k|k\rangle\frac{1}{\sqrt N}\sum\limits_k a_k~-~\sum\limits_k a_k|k\rangle~~=~~\sum\limits_k (2\bar{a}-a_k)|k\rangle$
- $|\psi\rangle=\frac{1}{\sqrt N}\sum\limits_k|k\rangle$
- $\langle\psi|k\rangle=\frac{1}{\sqrt N}$
- (5) $G=(2|\psi\rangle\langle\psi|-I_n)~~U_f$
- 先把目標加負號，再對平均取鏡反射
- $(2\begin{bmatrix}cos\theta\\sin\theta\end{bmatrix}\begin{bmatrix}cos\theta~sin\theta\end{bmatrix}-\begin{bmatrix}1&0\\0&1\end{bmatrix})\begin{bmatrix}1&0\\0&-1\end{bmatrix}=\begin{bmatrix}cos2\theta & -sin2\theta\\sin2\theta & cos2\theta\end{bmatrix}$
- 執行次數 $k=\begin{bmatrix}\frac{\pi}{4}\sqrt n-\frac{1}{2}\end{bmatrix}$
- $\begin{pmatrix}cos\theta~~ sin\theta\end{pmatrix}\rightarrow\begin{pmatrix}cos\theta~~ -sin\theta\end{pmatrix}\rightarrow\begin{pmatrix}cos3\theta~~ sin3\theta\end{pmatrix}$
- $\begin{pmatrix}cos3\theta~~ sin3\theta\end{pmatrix}\rightarrow\begin{pmatrix}cos\theta~~ -sin3\theta\end{pmatrix}\rightarrow\begin{pmatrix}cos5\theta~~ sin5\theta\end{pmatrix}$

## Bernstein-Varizani Algorithm
- 給定一個 $U_f$，找出布林函數 $f$ 當中的 $a$
- (1) $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$
- (2) $f(x)=ax=a_1x_1+...+a_nx_n$
- 
- 演算法: 為求簡潔，底下寫法省略 $|1\rangle$ 以及係數 $\frac{1}{\sqrt {2^n}}$
- $|0\rangle^{\otimes n}~~|1\rangle$
- $H^{\otimes n+1}~\Rightarrow~\frac{1}{\sqrt {2^n}}\sum\limits_x|x\rangle~~|-\rangle$
- $U_f~~~~\Rightarrow~\frac{1}{\sqrt {2^n}}\sum\limits_x(-1)^{ax}|x\rangle~~|-\rangle$
- $H^{\otimes n}~\Rightarrow~\frac{1}{2^n}\sum\limits_x(-1)^{ax}(\sum\limits_y(-1)^{x\cdot y}|y\rangle)~~|-\rangle=\frac{1}{2^n}\sum\limits_y\sum\limits_x(-1)^{x\cdot y+ax}|y\rangle~~|-\rangle$
- 特定 $|y\rangle$ 的係數為 $\frac{1}{2^n}\sum\limits_x(-1)^{x\cdot y+ax}$，考慮觀測 $|a\rangle$
- 係數為 $\frac{1}{2^n}\sum\limits_x(-1)^{ax+ax}=1$
- 觀測結果
- 觀測到 $|a\rangle$ 機率為 1
- 觀測到其他機率為 0
## Simon Algorithm
- 給定一個 $U_f$，找出布林函數 $f$ 當中的 $a$
- (1) $U_f:~|x,y\rangle\rightarrow |x,y\oplus f(x)\rangle$
- (2) $f:B^n\rightarrow B^n$ 是 2 to 1 function
- $f(x)=f(y)~~\iff~~x\in\{y,y+a\}$
- 
- 演算法
- $|0^n\rangle~~|0^n\rangle$
- $H^{\oplus n}I_n~\Rightarrow~\frac{1}{\sqrt {2^n}}\sum\limits_x|x\rangle~~|0^n\rangle$
- $U_f~~\Rightarrow~\frac{1}{\sqrt {2^n}}\sum\limits_x|x\rangle~~|f(x)\rangle$
- 觀測後 $n$ bits $\Rightarrow~\frac{1}{\sqrt 2}~(~|z\rangle~|f(z)\rangle~+~|z+a\rangle~|f(z+a)\rangle~)$
- 只取前 $n$ bits $\Rightarrow~\frac{1}{\sqrt 2}~(~|z\rangle~+~|z+a\rangle~)$
- $H^{\oplus n}~\Rightarrow~\frac{1}{\sqrt {2^{n+1}}}~(~\sum\limits_y(-1)^{yz}|y\rangle~+~\sum\limits_y(-1)^{y(z+a)}|y\rangle~)$
- $=\frac{1}{\sqrt {2^{n+1}}}~\sum\limits_y~[~(-1)^{yz}+(-1)^{y(z+a)}~]~|y\rangle$
- $=\frac{1}{\sqrt {2^{n+1}}}~\sum\limits_y~(-1)^{yz}~(~1+(-1)^{ya}~)~|y\rangle$
- 特定 $|y\rangle$ 的係數為 $\frac{1}{\sqrt {2^{n+1}}}(-1)^{yz}~(~1+(-1)^{ya}~)$
- 若 $ay=0$ ，則係數為 $\frac{2}{\sqrt {2^{n+1}}}(-1)^{yz}$
- 若 $ay=1$ ，則係數為 $0$
- 每次量測到 $y$ 都滿足 $ay=0$，蒐集夠多線性獨立的 $y$ 解聯立推得 $a$

## Quantum Fourier Transform
- 單位根
- $w=cos\theta+isin\theta=e^{i\theta}$
- $w^{-1}=\overline{w}$
- $w_N=e^{\frac{2\pi}{N}i}$
- $x^5=1$ 的解為: $1,w_5,w_5^2,w_5^3,w_5^4$
- $x^4+x^3+x^2+x+1=0$ 的解為: $w_5,w_5^2,w_5^3,w_5^4$
- $x^{12}=1$ 的解為: $1,w_{12},...,w_{12}^{11}$
- $x^{12}+x^{11}+...+1=0$ 的解為: $w_{12},...,w_{12}^{11}$
- $w_{12}^{10}+w_{12}^{8}+...+w_{12}^{2}+1=0$
- $w_{12}^{9}+w_{12}^{6}+w_{12}^{3}+1=0$
- QFT 矩陣: $n=lnN$ 個 qubit，$w=w_N=e^{\frac{2\pi}{N}i}$
- $QFT_N=\frac{1}{\sqrt N}\begin{pmatrix}1&1&1&...&...&1\\1&w&w^2&&&w^{N-1}\\1&w^2&w^4\\.&&&w^{i+j}\\.\\1&w^{N-1}&&&&w^{(N-1)(N-1)}\end{pmatrix}$
- QFT 性質
- (1)舉例
- $N=2$ ， $w_2=e^{\frac{2\pi}{2} i}=-1$ ， $QFT_2=\frac{1}{\sqrt 2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$
- $\begin{pmatrix}a\\b\end{pmatrix}~\mapsto~\frac{1}{\sqrt 2}\begin{pmatrix}a+b\\a-b\end{pmatrix}$
- $|0\rangle~\mapsto~\frac{1}{\sqrt 2}(|0\rangle+|1\rangle)$
- $|1\rangle~\mapsto~\frac{1}{\sqrt 2}(|0\rangle-|1\rangle)$
- $N=4$ ， $w_4=e^{\frac{2\pi}{4} i}=i$ ， $QFT_4=\frac{1}{\sqrt 4}\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{pmatrix}$
- $\begin{pmatrix}a\\b\\c\\d\end{pmatrix}~\mapsto~\frac{1}{\sqrt 4}\begin{pmatrix}a+b+c+d\\a+ib-c-id\\a-b+c-d\\a-ib-c+id\end{pmatrix}$
- $|00\rangle~\mapsto~\frac{1}{\sqrt 4}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$
- $|01\rangle~\mapsto~\frac{1}{\sqrt 4}(|00\rangle+i|01\rangle-|10\rangle-i|11\rangle)$
- $|10\rangle~\mapsto~\frac{1}{\sqrt 4}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)$
- $|11\rangle~\mapsto~\frac{1}{\sqrt 4}(|00\rangle-i|01\rangle-|10\rangle+i|11\rangle)$
- (2)`非 basis`:
- $\begin{pmatrix}a_0\\a_1\\.\\a_{N-1}\end{pmatrix}~\mapsto~\begin{pmatrix}c_0\\c_1\\.\\c_{N-1}\end{pmatrix}$，則 $c_k=\frac{1}{\sqrt N}\sum\limits_jw^{kj}a_j$
- $\sum\limits_{k=0}^{N-1}a_k|k\rangle~\mapsto~\sum\limits_{k=0}^{N-1}c_k|k\rangle$，則 $c_k=\frac{1}{\sqrt N}\sum\limits_jw^{kj}a_j$
- (3)`是 basis`:
- $|j\rangle~\mapsto~\frac{1}{\sqrt N}\begin{pmatrix}1\\w^j\\.\\w^{(N-1)j}\end{pmatrix}=\frac{1}{\sqrt N}\sum\limits_{k=0}^{N-1}w^{kj}|k\rangle$
- $N=2^n$，$e^{2\pi ik}=1$
- $|j_{n-1}...j_1j_0\rangle~\mapsto~\frac{1}{\sqrt {2^n}}\sum\limits_{k=0}^{2^n-1}e^{\frac{2\pi}{2^n}i(k_{n-1}2^{n-1}+...+k_12+k_0)(j_{n-1}2^{n-1}+...+j_12+j_0)}|k_{n-1}...k_1k_0\rangle$
- $=\frac{1}{\sqrt {2^n}}\sum\limits_{k_{n-1}=0}^1...\sum\limits_{k_{1}=0}^1\sum\limits_{k_{0}=0}^1~e^{2\pi ik_{n-1}\frac{j_0}{2}}e^{2\pi ik_{n-2}(\frac{j_1}{2}+\frac{j_0}{2^2})}...e^{2\pi ik_{0}(\frac{j_{n-1}}{2}+\frac{j_{n-2}}{2^{2}}+...+\frac{j_{0}}{2^{n}})}$
- $|k_{n-1}\rangle\otimes...\otimes|k_1\rangle\otimes|k_0\rangle$
- $=\frac{1}{\sqrt 2}\sum\limits_{k_{n-1}=0}^1e^{2\pi ik_{n-1}\frac{j_0}{2}}|k_{n-1}\rangle~\otimes...\otimes\frac{1}{\sqrt 2}\sum\limits_{k_{0}=0}^1e^{2\pi ik_{0}(\frac{j_{n-1}}{2}+\frac{j_{n-2}}{2^{2}}+...+\frac{j_{0}}{2^{n}})}|k_{0}\rangle$
- $=\frac{1}{\sqrt 2}(|0\rangle+e^{2\pi i\frac{j_0}{2}}|1\rangle)~\otimes...\otimes\frac{1}{\sqrt 2}(|0\rangle+e^{2\pi i(\frac{j_{n-1}}{2}+\frac{j_{n-2}}{2^{2}}+...+\frac{j_{0}}{2^{n}})}|1\rangle)$
- $=\frac{1}{\sqrt 2}(|0\rangle+(-1)^{j_0}|1\rangle)~\otimes...\otimes\frac{1}{\sqrt 2}(|0\rangle+(-1)^{j_{n-1}}e^{2\pi i(\frac{j_{n-2}}{2^{2}}+...+\frac{j_{0}}{2^{n}})}|1\rangle)$
- QFT 量子電路
- $R_a=R_{\frac{2\pi}{2^a}}$
- $|0\rangle~\mapsto~|0\rangle$
- $|1\rangle~\mapsto~e^{\frac{2\pi i}{2^a}}|1\rangle$
- 
- 經過 SWAP 即得: 
- QFT 性質
- (4)Untitary 矩陣 (行向量為 orthornormal)
- (5)Linear Shift
- 若 $QFT\begin{pmatrix}a\\b\\c\\d\end{pmatrix}=\begin{pmatrix}a'\\b'\\c'\\d'\end{pmatrix}$ ，則$QFT\begin{pmatrix}d\\a\\b\\c\end{pmatrix}=\begin{pmatrix}a'\\w~b'\\w^2c'\\w^3d'\end{pmatrix}$
- 因為 $|w|=1$，Linear Shift 不影響觀測機率分布
- (6)Period / WaveLength
- $QFT_{12}~:~~\frac{1}{\sqrt 4}(|0\rangle+|3\rangle+|6\rangle+|9\rangle)~~\Rightarrow~~\frac{1}{\sqrt 3}(|0\rangle+|4\rangle+|8\rangle)$

## Shor Algorithm 質因數分解
- Shor Algorithm
- Input: $M$
- Output: $p,q$
- (1) 隨機選取 $a\perp M$
- 若 $(a,M)\ne 1$，則找到質因數分解
- (2) 求 $a$ 的週期 $r$，最小 $r$ 使得 $a^r=1$ mod M
- 若 $r$ 是奇數或 $a^{r/2}+1=0$，重新選 $a$
- (3) $r$ 是偶數且 $a^{r/2}+1\ne 0$
- $p=(a^{r/2}+1,M)$
- $q=(a^{r/2}-1,M)$
- 說明: 根據 $r$ 是週期，$a^r-1=0$
- $(a^{r/2}+1)(a^{r/2}-1)=0$
- $a^{r/2}-1\ne 0$

## Period Finding Algorithm
- 
- Period Finding Algorithm
- Input: $a,M$
- Output: $a$ 的週期 $r$，最小 $r$ 使得 $a^r=1~mod~M$
- 1.根據 $a,M$ 設計上方的電路
- (1)Qubit 數量: $lnN+lnM$
- Wiki 建議 $N\sim M^2$，因為週期 $r$ 頂多 $M/2$
- 疊加態為 $\sum\limits_{x=0}^{M^2}|x\rangle$，每個 $f(x)$ 至少有 $2M$ 個疊加態對應
- (2)設計 $U_f$ 使得 $U_f|x,1\rangle=|x,a^x~mod~M\rangle$
- 設計 $U$ 使得 $U|y\rangle=|ay~mod~M\rangle$
- 設計 $U^i$ 使得 $U|y\rangle=|a^iy~mod~M\rangle$
- 設計 $U_f$ 為用 $x$ 的每個 bit 控制那些 $U^i$
- (3)設計 $QFT_N$
- 把週期從 $r$ 變成 $m=\frac{N}{r}$
- (4)指定輸入為 $|0,1\rangle$
- 2.執行電路
- $|0,1\rangle$
- $H^{\otimes n}\rightarrow\frac{1}{\sqrt N}\sum\limits_{x=0}^{N-1}|x,1\rangle$
- $U_f\rightarrow\frac{1}{\sqrt N}\sum\limits_{x=0}^{N-1}|x,f(x)\rangle$
- 觀察 reg2. $\rightarrow \frac{1}{\sqrt m}\sum\limits_{j=0}^{m-1}|rj+b\rangle\otimes|f(b)\rangle$
- 週期為 $r$， $m=\lfloor\frac{N}{r}\rfloor$ 或 $\lceil\frac{N}{r}\rceil$ 個疊加
- 取 reg1. 做 $QFT_{N}\rightarrow\frac{1}{\sqrt m}\sum\limits_{j=0}^{m-1}\frac{1}{\sqrt N}\sum\limits_{k=0}^{N-1}w^{(rj+b)k}|k\rangle$
- $=\frac{1}{\sqrt m}\frac{1}{\sqrt N}\sum\limits_{k=0}^{N-1}w^{bk}\sum\limits_{j=0}^{m-1}w^{rjk}|k\rangle$
- 週期近似 $m$， $r$ 個疊加
- 3.觀測機率
- $|k\rangle$ 的係數為 $\frac{1}{\sqrt m}\frac{1}{\sqrt N}w^{bk}(w^0+w^{rk}+w^{2rk}+...+w^{(m-1)rk})$
- Case 1: 若 $r|N$，則 $rm=N$
- $|0\rangle$ 係數 $\frac{1}{\sqrt m}\frac{1}{\sqrt N}w^{0}(w^0+w^{0}+w^{0}+...+w^{0})=\frac{1}{\sqrt r}w^0$
- $|m\rangle$ 係數 $\frac{1}{\sqrt m}\frac{1}{\sqrt N}w^{bm}(w^0+w^{rm}+w^{2rm}+...+w^{(m-1)rm})=\frac{1}{\sqrt r}w^{bm}$
- $|2m\rangle$ 係數 $\frac{1}{\sqrt m}\frac{1}{\sqrt N}w^{2bm}(w^0+w^{2rm}+w^{4rm}+...+w^{2(m-1)rm})=\frac{1}{\sqrt r}w^{2bm}$
- 因此，等機率觀測到 $|0\rangle,|m\rangle,...,|(r-1)m\rangle$
- 量測 1st reg. 得到 $dm$
- 定理：$\phi(r)=\theta(\frac{r}{loglogr})$
- 觀測到互質的 $d$ 機率為 $\frac{\phi(r)}{r}=O(loglogr)=O(loglogM)$
- 檢驗 $\frac{dm}{N}$ 的最簡分母是否為週期
- 分母為 $\frac{N}{gcd(N,dm)}$
- 若不是週期，同一電路重新量測 $dm$
- e.g. $N=32,r=4,m=8$，量測到 $|dm\rangle=|0\rangle\text{ or }|16\rangle$
- Case 2: 若 $r\nmid N$，令 $m=\lfloor\frac{N}{r}\rfloor$ 或 $\lceil\frac{N}{r}\rceil$
- 觀測到 $|k\rangle$ 的機率為 $\frac{1}{mN}|\frac{1-w^{mrk}}{1-w^{rk}}|^2=\frac{1}{mN}|\frac{sin\frac{mrk\pi}{N}}{sin\frac{rk\pi}{N}}|^2$
- 量測 1st reg. 得到 $k\approx d\frac{N}{r}$
- 定理：觀察到 $|k\rangle$ 使得 $|k-d\frac{N}{r}|\le\frac{1}{2}$ 的機率 $\ge\frac{\pi^2}{4}$
- 不論 $m=\lfloor\frac{N}{r}\rfloor$ 或 $\lceil\frac{N}{r}\rceil$ ，此定理都對
- 檢驗 $\frac{k}{N}$ 最接近的連分數，分母是否為週期
- 使用連分數遞迴關係，依序找出 $p_n$、$q_n$ 及最接近連分數
- 若不是週期，同一電路重新量測 $k$
- 定理：若 $|\psi_d|=\frac{1}{\sqrt r}(|1\rangle+\frac{1}{w^d}|a\rangle+\frac{1}{w^{2d}}|a^2\rangle+...+\frac{1}{w^{(r-1)d}}|a^{r-1}\rangle)$，其中 $0\le d< r$
- (1) $U|\psi_d\rangle=w^d|\psi_d\rangle$
- (2) $\frac{1}{\sqrt r}\sum\limits_{d=0}^{r-1}|\psi_d\rangle=|1\rangle$

## 連分數 Continued Fraction
- 分數 $\leftrightarrow$ 序列
- $3\frac{7}{8}=3+\frac{1}{\frac{8}{7}}=3+\frac{1}{1+\frac{1}{7}}\leftrightarrow[3,1,7]$
- $\frac{p_n}{q_n}\leftrightarrow[a_0,a_1,...,a_n]$
- 定理一: 給定序列 $[a_0,a_1,...,a_n]$
- $(p_0,q_0)=(a_0,1)$
- $(p_1,q_1)=(a_0a_1+1,a_1)$
- $(p_n,q_n)=(a_np_{n-1}+p_{n-2},a_nq_{n-1}+q_{n-2})$
- 定理二: 對任意分數 $x\leftrightarrow[a_0,a_1,...,a_m]$，存在 $0\le n\le m$ 使得
- $|x-\frac{p_n}{q_n}|\le\frac{1}{q_n^2}$
- $\frac{p_n}{q_n}$ "某種程度上" 近似 $x$
- 舉例而言，$x=\frac{27}{32}$，找出最接近連分數
- $0+\frac{27}{32}~~~~~~~\rightarrow[0]\rightarrow\frac{0}{1}，不滿足$
- $0+\frac{1}{1+\frac{5}{27}}~~~\rightarrow[0,1]\rightarrow\frac{1}{1}，不滿足$
- $0+\frac{1}{1+\frac{1}{5+\frac{2}{5}}}~\rightarrow[0,1,5]\rightarrow\frac{5}{6}，滿足~|\frac{27}{32}-\frac{5}{6}|\le\frac{1}{6^2}$
- 因此以 $\frac{5}{6}$ 來代表 $x=\frac{27}{32}$
## Phase Estimation Algorithm
- 
- Phase Estimation Algorithm
- **Input**: 量子電路 $U$ 及其特徵向量 $|\psi\rangle$
- $U|\psi\rangle=\lambda|\psi\rangle=e^{2\pi i\theta}|\psi\rangle$
- $=e^{\frac{2\pi i}{N}N\theta}|\psi\rangle=w^{N\theta}|\psi\rangle$
- $\theta=0.\theta_1...\theta_n\theta_{n+1}...$
- **Output**: $\lfloor2^n\theta\rfloor=\theta_1...\theta_n$，特徵值的 $\theta$ 前 $n$ 位
- 1.根據 $U,|\psi\rangle$ 設計上方的電路
- (1)Qubit 數量: $n+m$
- $n$ 為 $\theta$ 準確度
- $m$ 為 $|\psi\rangle$ 大小
- (2)設計 $U_f$ 使得 $U_f|x,\psi\rangle=\lambda^x|x\rangle\otimes|\psi\rangle$
- $U$ 滿足 $U|\psi\rangle=\lambda|\psi\rangle$
- 設計 $U^2$ 使得 $U^2|\psi\rangle=\lambda^2|\psi\rangle$
- 設計 $U_f$ 為用 $x$ 的每個 bit 控制那些 $U^i$
- (3)設計 $QFT_N^{-1}$
- (4)指定輸入為 $|0^n,\psi\rangle$
- 2.執行電路
- $|0^n,\psi\rangle$
- $H^{\otimes n}\rightarrow\frac{1}{\sqrt N}\sum\limits_{x=0}^{N-1}|x,\psi\rangle$
- $U\rightarrow\frac{1}{\sqrt N}\sum\limits_{x=0}^{N-1}|\lambda^xx\rangle\otimes|\psi\rangle=\frac{1}{\sqrt N}\sum\limits_{x=0}^{N-1}w^{N\theta x}|x\rangle\otimes|\psi\rangle$
- 取 reg1. 做 $QFT_{N}^{-1}\rightarrow\frac{1}{\sqrt N}\sum\limits_{x=0}^{N-1}w^{N\theta x}\frac{1}{\sqrt N}\sum\limits_{k=0}^{N-1}w^{-kx}|k\rangle$
- $=\frac{1}{N}\sum\limits_{k=0}^{N-1}\sum\limits_{x=0}^{N-1}w^{(N\theta-k) x}|k\rangle$
- 3.觀測機率
- $|k\rangle$ 的係數為 $\frac{1}{N}\sum\limits_{x=0}^{N-1}w^{(N\theta-k) x}$
- Case 1: 若 $N\theta$ 是整數
- $|N\theta\rangle$ 係數 $\frac{1}{N}(w^0+w^{0}+w^{0}+...+w^{0})=1$
- 因此觀測到 $|N\theta\rangle$
- Case 2: 若 $N\theta$ 不是整數
- 觀測到 $|k\rangle$ 的機率為 $\frac{1}{N^2}|\frac{1-w^{N(N\theta-k)}}{1-w^{N\theta-k}}|^2$ $=\frac{1}{N^2}|\frac{sin\frac{\pi N(N\theta-k)}{N}}{sin\frac{\pi (N\theta-k)}{N}}|^2$
- 定理：觀察到 $|k\rangle$ 使得 $|k-N\theta|=|\epsilon|\le\frac{1}{2}$ 的機率 $\ge\frac{\pi^2}{4}$
- $\frac{1}{N^2}|\frac{1-e^{\frac{2\pi i}{N}N|\epsilon|}}{1-e^{\frac{2\pi i}{N}|\epsilon|}}|^2\ge\frac{1}{N^2}|\frac{\frac{2}{\pi}2\pi|\epsilon|}{\frac{2\pi}{N}|\epsilon|}|^2=\frac{4}{\pi^2}$
- 定理：$\frac{2}{\pi}\theta\le|1-e^{i\theta}|<\theta$，當 $\theta\in[0,\pi]$ 恆成立
- 根據 $1<\frac{\theta}{|1-e^{i\theta}|}\le\frac{\pi}{2}$，以及 $\frac{x}{sinx}\le\frac{\pi}{2}成立當x\in(0,\pi]$
- 比較 Period Finding 與 Phase Estimation
- Period Finding：給定 $a,M$
- 設計 $U$ 使得 $U|y\rangle=|ay~mod~M\rangle$
- 設計 $U_f$ 使得 $U_f|x,1\rangle=|x,a^x~mod~M\rangle$
- Phase Estimation：給定 $U,|\psi\rangle$
- $U$ 本身滿足 $U|\psi\rangle=\lambda|\psi\rangle$
- 設計 $U_f$ 使得 $U_f|x,\psi\rangle=\lambda^x|x\rangle\otimes|\psi\rangle$
- Period Finding 設計的量子電路，可以用 Phase Estimation 來檢驗
- Period Finding 限定 $U|y\rangle=|ay~mod~M\rangle$，但 Phase Estimation 是任意的 $U$
- 兩演算法中的 $U^i$ 都可用 $U..U$ 實現，但實務上應使用較少 gate 的等價電路
- 若給定 $a,M$ 及週期 $r$，則 Period Finding 量子電路中的 $U$ 滿足
- $U|y\rangle=|ay~mod~M\rangle$
- $U|\psi_d\rangle=w^d|\psi_d\rangle=e^{\frac{2\pi i}{r}d}|\psi\rangle$
- $U|\psi\rangle=\lambda|\psi\rangle=e^{2\pi i\theta}|\psi\rangle$
- $U^i|y\rangle=|a^iy~mod~M\rangle$
- $U^i|\psi\rangle=\lambda^i|\psi\rangle$
- 根據 Phase Estimation 的觀察來驗證 Period Finding 設計的量子電路
- 比較 $U|\psi\rangle$，$U|\psi_d\rangle$，以及 $\frac{1}{\sqrt r}\sum\limits_{d=0}^{r-1}|\psi_d\rangle=|1\rangle$
- 推論 reg2. 的輸入與觀測結果間的關係
- (A) 輸入：$|\psi\rangle$ ，觀測結果：$|N\theta\rangle \rightarrow \theta$
- (B) 輸入：$|\psi_d\rangle$ ，觀測結果：$|N\frac{d}{r}\rangle \rightarrow \frac{d}{r}$
- (C\) 輸入：$|1\rangle$ ，觀測結果：$\frac{1}{\sqrt r}\sum\limits_{d=0}^{r-1}|N\frac{d}{r}\rangle \rightarrow \frac{d}{r}$ 對某個 $d$
- 推論觀測結果的機率
- (A) 輸入：$|\psi\rangle$ ，觀察到 $|k\rangle$ 使得 $|k-N\theta|\le\frac{1}{2}$ 的機率 $\ge\frac{\pi^2}{4}$
- (B) 輸入：$|\psi_d\rangle$ ，觀察到 $|k\rangle$ 使得 $|k-N\frac{d}{r}|\le\frac{1}{2}$ 的機率 $\ge\frac{\pi^2}{4}$
- (C\) 輸入：$|1\rangle$ ，觀察到 $|k\rangle$ 使得 $|k-d\frac{N}{r}|\le\frac{1}{2}$ 的機率 $\ge\frac{\pi^2}{4}$

## Quantum Information Theory
- Bell States
- 
- 觀點一
- $|\beta_{00}\rangle=\frac{1}{\sqrt 2}(|00\rangle+|11\rangle)$
- $|\beta_{01}\rangle=\frac{1}{\sqrt 2}(|01\rangle+|10\rangle)$
- $|\beta_{10}\rangle=\frac{1}{\sqrt 2}(|00\rangle-|11\rangle)$
- $|\beta_{11}\rangle=\frac{1}{\sqrt 2}(|01\rangle-|10\rangle)$
- 觀點二
- $|00\rangle=\frac{1}{\sqrt 2}(|\beta_{00}\rangle+|\beta_{10}\rangle)$
- $|01\rangle=\frac{1}{\sqrt 2}(|\beta_{01}\rangle+|\beta_{11}\rangle)$
- $|10\rangle=\frac{1}{\sqrt 2}(|\beta_{01}\rangle-|\beta_{11}\rangle)$
- $|11\rangle=\frac{1}{\sqrt 2}(|\beta_{00}\rangle-|\beta_{10}\rangle)$
- (1) $|\beta_{xy}\rangle$ 是糾纏態，不可拆成兩個 single qubit 做 tensor product
- (2) $\{|\beta_{00}\rangle,|\beta_{01}\rangle,|\beta_{10}\rangle,|\beta_{11}\rangle\}$ 是 orthornormal basis
- Pauli Operators
- $I=\begin{bmatrix}1 &0\\0 &1\end{bmatrix}，\begin{bmatrix}a\\b\end{bmatrix}\rightarrow\begin{bmatrix}a\\b\end{bmatrix}$
- $X=\begin{bmatrix}0 &1\\1 &0\end{bmatrix}，\begin{bmatrix}a\\b\end{bmatrix}\rightarrow\begin{bmatrix}b\\a\end{bmatrix}$
- $Z=\begin{bmatrix}1 &0\\0 &-1\end{bmatrix}，\begin{bmatrix}a\\b\end{bmatrix}\rightarrow\begin{bmatrix}a\\-b\end{bmatrix}$
- $iY=\begin{bmatrix}0 &1\\-1 &0\end{bmatrix}，\begin{bmatrix}a\\b\end{bmatrix}\rightarrow\begin{bmatrix}b\\-a\end{bmatrix}$
- **Superdense Coding**: 藉由傳送一個 qubit，來傳送兩個 classical bits
- 
- (1)用 $E$ 產生 $|\beta_{00}\rangle=\frac{1}{\sqrt 2}(|00\rangle+|11\rangle)$，事先雙方各拿一個 qubit，$q_A、q_B$
- (2)$A$ 根據 $x,y$ 操作 $|q_A\rangle$，則糾纏態會一起改變
- $I:|\beta_{00}\rangle\rightarrow|\beta_{00}\rangle$
- $X:|\beta_{00}\rangle\rightarrow|\beta_{01}\rangle$
- $Z:|\beta_{00}\rangle\rightarrow|\beta_{10}\rangle$
- $iY:|\beta_{00}\rangle\rightarrow|\beta_{11}\rangle$
- (3)$A$ 傳送操作後的 $|q_B\rangle$
- (4)$B$ 用 $E^{-1}$ 解碼 $|\beta_{xy}\rangle$ 得到 $|xy\rangle$，觀察即得
- **Quantum Teleportation**: 藉由傳送兩個 classical bits，來傳送一個 qubit
- 
- (1)用 $E$ 產生 $|\beta_{00}\rangle=\frac{1}{\sqrt 2}(|00\rangle+|11\rangle)$，事先雙方各拿一個 qubit，$q_A、q_B$
- 這時候，根據量子 phase kickback，$(a|0\rangle+b|1\rangle)|\beta_{00}\rangle$
- $=\frac{1}{2}[~|\beta_{00}\rangle(a|0\rangle+b|1\rangle)+|\beta_{01}\rangle(a|1\rangle+b|0\rangle)$
- $~~~~+|\beta_{10}\rangle(a|0\rangle-b|1\rangle)+|\beta_{11}\rangle(a|1\rangle-b|0\rangle)~]$
- (2)$A$ 對 $|q_A\rangle$ 取 $E^{-1}$，得到 $x,y$
- (3)$A$ 傳送 $x,y$
- (4)$B$ 根據 $x,y$ 操作 $|q_B\rangle$，即得
- $I:a|0\rangle+b|1\rangle\rangle\rightarrow a|0\rangle+b|1\rangle$
- $X:a|1\rangle+b|0\rangle\rangle\rightarrow a|0\rangle+b|1\rangle$
- $Z:a|0\rangle-b|1\rangle\rangle\rightarrow a|0\rangle+b|1\rangle$
- $iY:a|1\rangle-b|0\rangle\rangle\rightarrow a|0\rangle+b|1\rangle$