05 - Deutsch 演算法 (Deutsch Algorithm)

先說了,這是個沒什麼用的演算法 XD"

那為什麼要介紹 Deutsch Algorithm?

因為他是第一個證明了如何使用量子做計算?量子計算如何比普通電腦還快?

也因此開啟了量子演算法的研究。

現在就 … 開始解釋演算法在做什麼囉:

假設有兩種函式(function),任意選一個給你,請你幫忙檢驗這個函式是否為常數:

  1. 常數函式:

    • f(x)=0f(x) = 0
    • f(x)=1f(x) = 1

  2. 一般函式:

    • f(x)=xf(x) = x
    • f(x)= !xf(x) =\ !x

如果是一般的電腦,必須要測驗兩次:

  1. f(0)=0{f(x)=x,f(x)=0,f(0) = 0 \Rightarrow \begin{cases} f(x)= x,\\ f(x)= 0, \end{cases}

  2. f(1)=1f(x)=xf(1) = 1 \Rightarrow f(x)= x

Deutsch’s Algorithm 是一個量子演算法,可以用不同於普通電腦的方法,以一次的計算,決定到底是哪一個函式。

假設有一個轉換 (如下圖)

還記得 H0=0+12H|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}H1=012H|1\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}

電路中 x=0+12x=\frac{|0\rangle+|1\rangle}{\sqrt{2}}y=012y = \frac{|0\rangle-|1\rangle}{\sqrt{2}} 傳入 UfU_f

傳進去會發生什麼事?

Uf(xy)=Uf(x012)=12Uf(x(01))U_f(|x\rangle|y\rangle) = U_f(|x\rangle\frac{|0\rangle-|1\rangle}{\sqrt{2}}) = \frac{1}{\sqrt{2}}U_f(|x\rangle(|0\rangle-|1\rangle))

=12(Uf(x0)(Uf(x1)))= \frac{1}{\sqrt{2}}( U_f(|x\rangle|0\rangle )-( U_f(|x\rangle|1\rangle)))

=12(Uf(x0f(x))(Uf(x1f(x))))= \frac{1}{\sqrt{2}}( U_f(|x\rangle|0\oplus f(x)\rangle ) - ( U_f(|x\rangle |1\oplus f(x)\rangle ))) ----- 結果

那麼如果 f(x)=0f(x)=0,那麼 00=0,11=10\oplus 0 = 0, 1\oplus 1=1,結果是x12(01)|x\rangle \frac{1}{\sqrt{2}} (|0\rangle-|1\rangle)

反之 f(x)=1f(x)=1,那麼 01=1,11=00\oplus 1 = 1, 1\oplus 1=0,結果會是x12(10)|x\rangle \frac{1}{\sqrt{2}} (|1\rangle-|0\rangle)

因此,此函式可以寫成如下

(1)f(x)x12(10)(-1)^{f(x)}|x\rangle \frac{1}{\sqrt{2}} (|1\rangle-|0\rangle)


現在我們把 x 放進去,x=0+12x=\frac{|0\rangle+|1\rangle}{\sqrt{2}}

Uf(xy)=(1)f(x)x12(10)=(1)f(0+12)(0+12)12(10)....U_f(|x\rangle|y\rangle)=(-1)^{f(x)}|x\rangle \frac{1}{\sqrt{2}} (|1\rangle-|0\rangle)=(-1)^{f(\frac{|0\rangle+|1\rangle}{\sqrt{2}})}(\frac{|0\rangle+|1\rangle}{\sqrt{2}})\frac{1}{\sqrt{2}} (|1\rangle-|0\rangle) ....


等等!!別關掉 …

=(1)f(0)0212(10)+(1)f(1)1212(10)=(-1)^{f(0)}\frac{|0\rangle}{\sqrt{2}}\frac{1}{\sqrt{2}} (|1\rangle-|0\rangle) + (-1)^{f(1)}\frac{|1\rangle}{\sqrt{2}}\frac{1}{\sqrt{2}} (|1\rangle-|0\rangle)


$$= \frac{(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle}{\sqrt{2}} \frac{1}{\sqrt{2}} (|1\rangle-|0\rangle) $$

所以,如果 f(0)=f(1)f(0)=f(1)

  • f(0)=f(1)=0f(0)=f(1)=0Uf=[0+12][012]U_f = [\frac{|0\rangle+|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}]

  • f(0)=f(1)=1f(0)=f(1)=1Uf=[0+12][012]U_f = -[\frac{|0\rangle+|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}]

這時對第一個 qubits 做 Hadamard Gate (H-gate) 後測量(measure) 都會得到是 0 。

反之 f(0)f(1)f(0) \neq f(1)

  • f(0)=0f(0)=0f(1)=1f(1)=1Uf=[012][012]U_f = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}]

  • f(0)=1f(0)=1f(1)=0f(1)=0Uf=[012][012]U_f = -[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}]

這時對第一個 qubits 做 Hadamard Gate (H-gate) 後測量 (measure) 都會得到是 1 。

因此,經過一次的測量,就可以知道到底這者個函數,是否為常數函數。

實作電路:

Code :
等我 XDDD

=================================

問題是這個黑箱是什麼? 其實就是需要你去設計的電路。

現階段還只能,針對一個 function,透過觀察其輸入與輸出,實作 Gate 來組出相對的電路。

當時這個演算法所需要的黑箱,現在已經有設計好的了。

但是這只是個簡易的問題,判斷輸出是否一樣,所以… 說實話真的沒什麼用,就當作一個展示吧。