Last
First
個人首頁
帳號設定
登出
關於我們
最新消息
課程學習
興趣探索(測試版)
登入
立即開始
Last
First
個人首頁
帳號設定
登出
會員登入
歡迎進入量子學習的新紀元!
忘記密碼?
或
以 Google 帳號登入
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
新用戶?
立即註冊
,開啟您的量子學習之旅。
No items found.
・第
18
課
Deutsch 演算法
作者:
林昱誠(Yu-Cheng Lin)
閱讀時間:
10
分鐘
# Deutsch Algorithm 英國物理學家 David Deutsch 在 1985 年提出 Deutsch 演算法,他的學生 Richard Jozsa 將老師的想法延伸,於 1992 年提出 Deutsch-Jozsa 演算法,簡稱 DJ 演算法,這期,我們將先介紹 Deutsch 演算法,在下一篇我們把概念延伸,介紹 DJ 演算法。 ## 要解決什麼問題? Deutsch 想要解決一項數學問題,假使有一個函數(function),可以輸入 0 或 1,函數會輸出 0 或 1 \begin{split} f:\{0,1\}\rightarrow\{0,1\}\ \end{split} 如果不管輸入 0 還是 1,函數都輸出 0,這函數我們歸類在 "constant function",同理,如果都輸出 1,也被歸類在此。
如果輸入 0 則輸出 0,輸入 1 則輸出 1,或是相反,輸入 0 得出 1,輸入 1 得出 0,這種函數我們歸類在 "balance constant"。 假設有一個函數是 \begin{split} f(x)=x \end{split} 輸入 0 會得出 0,輸入 1 會得出 1,按照前面所述,這函數是 balance function。 Deutsch 演算法,或說是 DJ 演算法就是應用在此,判定一個函數是 constant 還是 balance。 ## 經典電腦解法 同樣的問題,你眼前的電腦或手機會怎麼解這問題呢?很簡單,就是先代入 0 得出結果 1,在代入 1 得出結果 2,比較兩個結果一不一樣,一樣則這函數是 constant,不一樣則為 balance。 \begin{split} \text{Step 1: }&f(0)=a \\ \text{Step 2: }&f(1)=b \\ \text{Step 3: } &\text{if }a = b \text{ constant} \\ &\text{if }a \neq b \text{ balance} \end{split} 總共需要兩個步驟,加上最後比較結果的話,共 3 個步驟,那量子電腦的解法呢? ## 量子電腦解法
先別看到圖就怕,等等會一步一步帶您解析,Deutsch 提供的解法如上圖,準備兩個 qubits,一個是 0,一個是 1,兩個都做 H gate 後,再做 $U_f$ 操作,這邊先不細談 $U_f$ 究竟長什麼樣子,但經過這一番操作後,第二個 qubits 輸出的值會是 $y$ 與 $f(x)$ 的二進位加法,最後對第一個 qubit 做 H gate 後測量,如果量測出來的值是 0,這函數為 constant,反之,是 1 的話就是 balance。因此,量子電腦的解法只需要一個步驟就能得知函數是哪一種。 接下來,我們將細談這演算法怎麼運作 ## 量子演算法解析 最一開始的狀態,即圖中的 $|\psi_0\rangle$ 為: \begin{split} |\psi_0\rangle=|0\rangle |1\rangle \end{split} 兩個都經過 H gate 操作後: \begin{split} |\psi_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$ 都長得一樣,接下來的操作,會因為你代入的函數不同,而有不同的狀態,所以接下來,會分成 4 個 case 做討論(在此例中,函數也只有會 4 種) 建議你先準備個白紙與鉛筆,靜下心,喝杯咖啡後,專心把以下四個案例一次看完看懂,就解脫了。 ### 案例一 函數是: \begin{split} f(0)=f(1)=0 \end{split} 在 $|\psi_1\rangle$ 的時候,系統是四種狀態的疊加態,所以我們會先分成四種狀態做討論,之後的案例就會直接給出結果,留給讀者在紙上推敲 #### 00 第一種狀態就是 $|00\rangle$,經過 $U_f$ 操作後,第一個 qubits 還是 $|0\rangle$,第二個 qubits 則為 $0\oplus f(0)=0\oplus 0=0$,因此輸出 $|00\rangle$ #### 01 同理,第一個 qubits 還是 $|0\rangle$,第二個 qubits 則為 $1\oplus f(0)=1\oplus 0=1$,因此輸出 $|01\rangle$ #### 10 第一個 qubits 是 $|1\rangle$,第二個 qubits 會是 $0\oplus f(1)=0\oplus 0=0$,因此輸出 $|10\rangle$ #### 11 第一個 qubits 是 $|1\rangle$,第二個 qubits 會是 $1\oplus f(1)=1\oplus 0=1$,因此輸出 $|11\rangle$ 綜合上述,得出 \begin{split} |\psi_2\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=|0\rangle \end{split} 根據前述,測量出 0 就代表函數是 constant。 ### 案例二 函數是: \begin{split} f(0)=f(1)=1 \end{split} 經過 $U_f$ 操作後,得出 \begin{split} |\psi_2\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$ ### 案例三 函數是 \begin{split} f(0)=0 \\ f(1)=1 \end{split} 經過 $U_f$ 操作後,得出 \begin{split} |\psi_2\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$ 相比,會發現 $|10\rangle$ 和 $|11\rangle$ 前面的正負符號(相位)剛好相法,這也是這演算法判斷函數是哪一種的關鍵。經過整理後: \begin{split} |\psi_2\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \end{split} 所以,第一個 qubit 測量出的狀態為 \begin{split} |\psi_3\rangle=|1\rangle \end{split} 此函數為 balance。 ### 案例四 撐住啊,最後一個案例了 \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。 ## 範例 恭喜你細心看完以上詳細的解析,可是,我們還是沒有提 $U_f$ 究竟是什麼,因此我們就有最一開始提到的函數作為範例 \begin{split} f(x)=x \end{split} 根據前面介紹,我們知道 Deutsch 演算法最基本會長這樣
而我們要 gate 湊出 $U_f$ 的功能,因此我們要先畫出一個表格,輸入什麼到 $U_f$,$U_f$ 會輸出什麼:
現在,給你幾分鐘想想什麼樣的 gate 能做到一樣的功能... 沒錯 就是 CNOT gate,回想一下 CNOT gate。因此,完整的演算法長這樣:
Deutsch 演算法只有 2 個 qubits,僅能判斷只有一個位元的函數,在下一篇我們會介紹 Jozsa 提出的演算法,將他老師的想法延伸應用到多位元的函數。
本文章採用創用 CC「姓名標示-相同方式分享 4.0 國際」授權條款
用 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
上ㄧ課
#上一課課程名稱
下ㄧ課
#下一課課程名稱
課程目錄