--- # System prepended metadata title: 課程｜量子演算法 tags: [課程] --- # 量子演算法 [Colab Implementation](https://colab.research.google.com/drive/1YVZkxclImURvc_W8mBJRzfzkWGJcNBFv?usp=sharing) ## 量子計算 - ![](https://i.imgur.com/hvVpmTZ.png) - 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) 而不作任何運算 - 但是因為這樣對應的函數是雙變數，為了將其變成單變數，因此做乘法運算 - ![](https://i.imgur.com/AUL2M1T.png) - 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 - (1) State Space Postulate - 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 = 單位向量` - (2) Evolution Postulate - 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 矩陣` - (3) Measurement Postulate - 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$ - `觀測機率=係數平方` - `觀測即失去量子特性` - (4) Composition of System Postulate - 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)$ → ![](https://i.imgur.com/LZpBBsd.png) - `量子不可克隆定理`：不存在 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$ - ![](https://i.imgur.com/sG94hkg.png) - (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) ![](https://i.imgur.com/IhnpKvo.png) - (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\}$ - ![](https://i.imgur.com/Vs6GiS8.png) - `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\}$ - ![](https://i.imgur.com/TfhJNNI.png) - 演算法: - $|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.$ - ![](https://i.imgur.com/G87YWRB.png) - 演算法: - $|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}$ - ![](https://i.imgur.com/c55iKRj.png) ![](https://i.imgur.com/RTFIpOd.png) - $\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$ - ![](https://i.imgur.com/OnQVpuV.png) - 演算法: 為求簡潔，底下寫法省略 $|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\}$ - ![](https://i.imgur.com/TwjDSbA.png) - 演算法 - $|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$ - ![](https://i.imgur.com/chHYkKR.png) - 經過 SWAP 即得: ![](https://i.imgur.com/HOpQ2xN.png) - 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 - ![](https://i.imgur.com/pDnDGfe.png) - 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 - ![](https://i.imgur.com/0LzOfds.png) - 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 - ![](https://i.imgur.com/0O2XNR8.png) - 觀點一 - $|\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 - ![](https://i.imgur.com/McYouDo.png) - (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 - ![](https://i.imgur.com/mehrSN6.png) - (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$