oracle and query

本小節介紹先備知識，兩種oracle 和 query，以及時間複雜度所關心的核心議題。

Oracle

我們視oracle為一個黑盒，並不在意裡面如何運作，通常oracle會有一個輸入函式，而我們能做的就是詢問這個oracle，而oracle會告訴我們答案。

Query Model

我們在說的時間複雜度，基本上都是基於query的次數，oracle內的複雜度我們並不需要去討論，因為他是個黑盒。

給定一個輸入函數 f(x)f(x) ，而根據query後的結果，oracle一般來說又可分為兩種：

∣x,w⟩→∣x,w⊕f(x)⟩∣x⟩→(−1)f(x)∣x⟩\begin{aligned} &|x,w\rangle\rightarrow|x,w\oplus f(x)\rangle\\ &|x\rangle\rightarrow(-1)^{f(x)}|x\rangle \end{aligned}

我們常稱第二種為phase oracle，因為他改變了量子態的機率幅的正負號，而事實上，兩者是等價的，以下給個小小的證明：

給定一個 f(x)={0,1}n→{0,1}f(x)=\left\{0,1\right\}^n\rightarrow\left\{0,1\right\} 將第二個register設定為 ∣−⟩|-\rangle，並query

∣x,−⟩→∣x,−⊕f(x)⟩\begin{aligned} |x,-\rangle\rightarrow|x,-\oplus f(x)\rangle \end{aligned}

開始展開化簡，因 ∣−⟩=∣0⟩−∣1⟩2|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}} ，得到以下結果

∣x,−⊕f(x)⟩=∣x⟩∣0⊕f(x)⟩−∣x⟩∣1⊕f(x)⟩2|x,-\oplus f(x)\rangle = \frac{|x\rangle|0\oplus f(x)\rangle-|x\rangle|1\oplus f(x)\rangle}{\sqrt{2}}

仔細觀察可以發現，當 f(x)=0f(x)=0 ，化簡後與原來並無區別

∣x,−⊕0⟩=∣x⟩∣0⊕0⟩−∣x⟩∣1⊕0⟩2=∣x⟩∣0⟩−∣x⟩∣1⟩2=∣x,−⟩\begin{aligned} |x,-\oplus 0\rangle &= \frac{|x\rangle|0\oplus 0\rangle-|x\rangle|1\oplus 0\rangle}{\sqrt{2}}\\ &=\frac{|x\rangle|0\rangle-|x\rangle|1\rangle}{\sqrt{2}}\\ &=|x,-\rangle \end{aligned}

但是當 f(x)=1f(x)=1 ，卻會相差一個負號

∣x,−⊕1⟩=∣x⟩∣0⊕1⟩−∣x⟩∣1⊕1⟩2=∣x⟩∣1⟩−∣x⟩∣0⟩2=−∣x,−⟩\begin{aligned} |x,-\oplus 1\rangle &= \frac{|x\rangle|0\oplus 1\rangle-|x\rangle|1\oplus 1\rangle}{\sqrt{2}}\\ &=\frac{|x\rangle|1\rangle-|x\rangle|0\rangle}{\sqrt{2}}\\ &=-|x,-\rangle \end{aligned}

透過這個證明，我們可以了解到兩種oracle的等價，也就是：

∣x,−⊕f(x)⟩=(−1)f(x)∣x⟩∣−⟩|x,-\oplus f(x)\rangle = (-1)^{f(x)}|x\rangle|-\rangle
PreviousDeutsch-JozsaNext經典 vs Deutsh-Jozsa

Last updated