Last
First
個人首頁
帳號設定
登出
關於我們
最新消息
課程學習
興趣探索(測試版)
登入
立即開始
Last
First
個人首頁
帳號設定
登出
會員登入
歡迎進入量子學習的新紀元!
忘記密碼?
或
以 Google 帳號登入
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
新用戶?
立即註冊
,開啟您的量子學習之旅。
量子計算入門(下):量子演算法
・第
3
課
Deutsch 演算法(下)
作者:
林昱誠(Yu-Cheng Lin)
閱讀時間:
10
分鐘
# Deutsch 演算法(下) 在上篇文章中,我們簡要介紹 Deutsch 演算法在做什麼,這篇文章我們要逐步解析電路中每一個環節在做什麼。如果讀者對於以下數學證明沒有興趣,可以直接跳至下一篇文章。 回到上篇提到以下這電路圖,我們將這電路圖拆成四個部分,分別是 $|\psi_0\rangle$ 到 $|\psi_4\rangle$,接著我們一步一步用數學描述這四個部分發生什麼事。
## $|\psi_0\rangle$ 最一開始的狀態,即圖中的 $|\psi_0\rangle$ 為: \begin{split} |\psi_0\rangle&=|0\rangle |1\rangle \end{split} ## $|\psi_1\rangle$ 接著兩個 qubits 都經過 H gate 操作,先回顧 H gate 的作用: \begin{split} H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\\ H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 因此這兩個 qubits 的狀態變為: \begin{split} |\psi_1\rangle&=H|0\rangle \otimes H|1\rangle \\ &=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \\ &=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \end{split} 不管今天你要判斷的函數長什麼樣子,$|\psi_0\rangle$ 和 $|\psi_1\rangle$ 都長得一樣。 ## $|\psi_2\rangle$、$|\psi_3\rangle$ 與 $|\psi_4\rangle$
接下來的操作,會因為你要判斷的函數不同,而有不同的狀態。從上一篇文章可以得知 $f(x)$ 不管實際長什麼樣子,他的輸入與輸出只會有四種情況: 所以我們接著會分成四種情況做分別討論。建議你先準備個白紙與鉛筆,靜下心,喝杯咖啡後,專心把以下四個情況一次看完看懂,就解脫了。 ### 情況一 函數是: \begin{split} f(0)=f(1)=0 \end{split} 在經過 $U_f$ 之前,$|\psi_1\rangle$ 是四種狀態的疊加態: \begin{split} |\psi_1\rangle=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \end{split} 所以我們會再分成四種狀態做討論,之後的案例就會直接給出結果,留給讀者在紙上推敲 #### 當 $|\psi_1\rangle = |00\rangle$ 經過 $U_f$ 操作後,第一個 qubits 還是 $|0\rangle$,第二個 qubits 則為 $0\oplus f(0)$,在這裡,$f(0)=0$,所以 $0\oplus f(0)=0\oplus 0=0$,因此輸出 $|00\rangle$ #### 當 $|\psi_1\rangle = |01\rangle$ 同理,第一個 qubits 還是 $|0\rangle$,第二個 qubits 則為 $1\oplus f(0)=1\oplus 0=1$,因此輸出 $|01\rangle$ #### 當 $|\psi_1\rangle = |10\rangle$ 第一個 qubits 是 $|1\rangle$,第二個 qubits 會是 $0\oplus f(1)=0\oplus 0=0$,因此輸出 $|10\rangle$ #### 當 $|\psi_1\rangle = |11\rangle$ 第一個 qubits 是 $|1\rangle$,第二個 qubits 會是 $1\oplus f(1)=1\oplus 0=1$,因此輸出 $|11\rangle$ 綜合上述四種情況,得出: \begin{split} |\psi_2\rangle&=U_f |\psi_1\rangle \\ &=\frac{1}{2}U_f(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以就是沒變,第一個 qubits 經過 H gate 操作後,就變成 \begin{split} |\psi_3\rangle&=H|\psi_2\rangle \\ &=H[\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)] \\ &=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\ &=|0\rangle \end{split} 對 $|\psi\rangle$ 測量後得出 $0$,代表這函數是 "constant"。 ### 情況二 函數是: \begin{split} f(0)=f(1)=1 \end{split} 經過 $U_f$ 操作後,得出 \begin{split} |\psi_2\rangle&=U_f |\psi_1\rangle \\ &=\frac{1}{2}U_f(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{2}(|01\rangle-|00\rangle+|11\rangle-|10\rangle) \\ &= \frac{1}{2}(-|00\rangle+|01\rangle-|10\rangle+|11\rangle)\\ &=-\frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \end{split} 會發現這和 $|\psi_1\rangle$ 差一個負號,經過整理後: \begin{split} |\psi_2\rangle=-\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以測量第一個 qubits,得出來依然是 $|0\rangle$ ### 情況三 前面兩個情況都是 constant function,接下來要討論的兩種情況都是 balanced function,計算上會稍微難一點點點。 情況三的函數是: \begin{split} f(0)=0 \\ f(1)=1 \end{split} 經過 $U_f$ 操作後,得出 \begin{split} |\psi_2\rangle&=U_f |\psi_1\rangle \\ &=\frac{1}{2}U_f(|00\rangle-|01\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{2}(|00\rangle-|01\rangle+|11\rangle-|10\rangle) \\ &=\frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle) \end{split} 與 $|\psi_1\rangle$ 相比,會發現 $|10\rangle$ 和 $|11\rangle$ 前面的正負號(相位)剛好相法,這正負號是 DJ 演算法判斷函數是哪一種的關鍵。經過整理後: \begin{split} |\psi_2\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以,第一個 qubit 經過 H gate 操作後 \begin{split} |\psi_3\rangle&=H|\psi_2\rangle\\ &=H[\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)]\\ &=|1\rangle \end{split} 測量後得到 $1$,這函數是 balanced。 ### 情況四 撐住啊,最後一個案例了 \begin{split} f(0)=1 \\ f(1)=0 \end{split} 其實結果就跟案例三一樣,但差了一個負號 \begin{split} |\psi_2\rangle&=\frac{1}{2}(|01\rangle-|00\rangle+|10\rangle-|11\rangle) \\ &=\frac{1}{2}(-|00\rangle+|01\rangle+|10\rangle-|11\rangle) \\ &=-\frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle) \\ &=-\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以最後測量出也是 1。
用 Pennylane 建立量子電路
pennylane
4
Colab 與 Jupyter 介面介紹
pennylane
3
安裝 Pennylane
pennylane
2
Deutsch-Jozsa 演算法(下)
algorithm
5
Deutsch-Jozsa 演算法(上)
algorithm
4
量子演算法總覽
algorithm
1
Deutsch 演算法(下)
algorithm
3
Deutsch 演算法(上)
algorithm
2
量子計算概覽:當電腦遇上量子世界
basic-algorithm
1
自學資源與路線:入門量子計算的第一步
basic-algorithm
2
量子電路:量子邏輯閘的實踐
basic-algorithm
17
測量:讀取計算結果
basic-algorithm
16
量子邏輯閘(下):量子邏輯閘的特性
basic-algorithm
15
量子邏輯閘(中):多個量子位元的操作
basic-algorithm
14
量子位元 (下):量子糾纏
basic-algorithm
13
量子位元(中):多個量子位元
basic-algorithm
12
布洛赫球面 (下):解讀量子邏輯閘的運作
basic-algorithm
11
布洛赫球面(上):量子位元可視化
basic-algorithm
10
量子邏輯閘(上):單一量子位元操作
basic-algorithm
9
量子位元(上):量子計算的基本單位
basic-algorithm
8
重視經典電腦:過渡到量子電腦
basic-algorithm
7
Pennylane 簡介
pennylane
1
演算法複雜度
basic-algorithm
6
經典邏輯閘(下):邏輯閘的特性
basic-algorithm
5
經典邏輯閘(上):電腦運算的基礎
basic-algorithm
4
電腦的世界只有 0 與 1:二進位表示法
basic-algorithm
3
量子硬體總覽
hardware-general
1
第三題:Many-Body Quantum Dynamics
ibm-2023-spring
3
第二題:Quantum Random Walks and Localization
ibm-2023-spring
2
第一題:Trotterization
ibm-2023-spring
1
如何綜合評估量子電腦的表現
hardware-general
10
Qubit 狀態的壽命(相干時間):T2
hardware-general
9
Qubit 狀態的壽命(相干時間):T1
hardware-general
8
保真度(Fidelity):衡量量子邏輯閘的指標
hardware-general
7
附錄 C:絕熱通道
hardware-general
13
如何操作 Qubit:絕熱通道(Adiabetic passage)
hardware-general
6
附錄 B:拉比震盪
hardware-general
12
如何操作 Qubit:拉比震盪(Rabi Oscillation)
hardware-general
5
附錄 A:雙態系統
hardware-general
11
Deutsch 演算法
basic-algorithm
18
雙態系統(Two Level System):Qubit 的基礎
hardware-general
4
DiVincenzo Criteria:量子電腦的五大標準
hardware-general
3
自學資源與路線:入門量子電腦硬體的第一步
hardware-general
2
課程撰寫中
s
1
特徵向量和特徵值(eigenvector and eigenvalue)
linear-algebra
9
量子計算中的特殊矩陣
linear-algebra
8
張量積(Tensor product)
linear-algebra
7
Orthonormal Bases
linear-algebra
6
正交(Orthogonality)
linear-algebra
5
基(Basis)
linear-algebra
4
數學基礎:量子計算的起點
linear-algebra
2
量子計算的數學之鑰:線性代數入門
linear-algebra
1
什麼是量子電腦?
quantum-computer-basics
1
量子電腦如何改變世界
quantum-computer-basics
2
進入量子世界
quantum-computer-basics
4
量子糾纏
quantum-computer-basics
6
疊加態
quantum-computer-basics
5
電腦怎麼做計算
quantum-computer-basics
3
如何實現量子電腦
quantum-computer-basics
7
量子電腦現況與未來
quantum-computer-basics
9
狄拉克(Dirac)表示法
linear-algebra
3
自學資源與路線
quantum-computer-basics
8
上ㄧ課
#上一課課程名稱
下ㄧ課
#下一課課程名稱
課程目錄