oracle and query

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

Oracle

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

Query Model

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

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

$$\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)=\left\{0,1\right\}^n\rightarrow\left\{0,1\right\}$ 將第二個register設定為 $|-\rangle$，並query

$$\begin{aligned} |x,-\rangle\rightarrow|x,-\oplus f(x)\rangle \end{aligned}$$

開始展開化簡，因 $|-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{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)=0$ ，化簡後與原來並無區別

$$\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)=1$ ，卻會相差一個負號

$$\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,-\oplus f(x)\rangle = (-1)^{f(x)}|x\rangle|-\rangle$$