日韩avav国产,久久久少妇

歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識】
更多相關(guān)文章請點擊【量子計算通識】
上一篇：【科普】量子計算通識-6

這一篇我們來看一下多伊奇算法是怎么推導(dǎo)出來的。

多伊奇問題

我們用 $x\in \{0,1\}^n$ 表示 $x$ 是由0或1組成的任意 $n$ 位二進制數(shù)，比如 $n=3$ 位的011、 $n=7$ 位的1010011。

我們又知道對于單比特的四種操作可以分為兩類：

常量操作constant：等0，等1；
平衡操作balanced：不變，翻轉(zhuǎn)。

更多參考這里：【科普】量子計算通識-2-四種操作與乘積態(tài)

綜合上面兩個情況，我們就可以描述為， $\forall x \in \{0,1\}^n$ ，對于0和1組成的任意 $n$ 位長度二進制數(shù)的兩種操作：

Constant：
$f(x)=0\quad或\quad f(x)=0$
Balanced：
$50\%情況 $f(x)=0\quad 另外50\%情況 f(x)=1$

多伊奇的問題就是，如果有一個符合以上條件的未知函數(shù)，那么如何嘗試最少且足夠的次數(shù)，來確定它是Constant操作還是Balanced操作。

經(jīng)典計算機解法

$n$ 位2進制最多表示 $2^n$ 個數(shù)字，比如2位的00、01、10、11共有 $2^2=4$ 種，可以表示十進制的0 ~ 3；同樣3位的000、001、010、011、100、101、110、111共可以表示0 ~ 7，即 $2^3=8$ 種；同樣8位可以表示 $2^8=256$ 。

所以，對于經(jīng)典計算機來說，需要嘗試 $2^n*\frac{1}{2}+1$ 次（也就是一半多一次），才能確保足夠可以判斷未知函數(shù)屬于哪一種，因為前提已經(jīng)承諾，如果是Balanced類型，那么一半多一次恰好剛剛超過50%，如果這么多情況的結(jié)果都是相同的，那么它就是Constant類型操作（因為Constant類型操作所有結(jié)果都一樣），否則就是Balanced類型操作。

這就好比一共8張卡片，要么都一樣顏色，要么黑白各一半。這時我們只要最多翻開5張，就能知道屬于那種情況了。

量子計算解法

如前面文章所述，在量子計算機中，只需要一次嘗試就可以做出準(zhǔn)確判斷。當(dāng)然我們要進行一些特殊處理。

圖中的符號 $\Psi$ 讀作|p’sai|

首先我們需要設(shè)計一個電路 $U$ ，它包含我們需要進行判斷的函數(shù) $f(x)$ ，可以說是我們在 $f(x)$ 的基礎(chǔ)上又增加了一些處理使其成為函數(shù) $U$ 。

$U$ 的作用就是可以傳入一些量子比特，然后輸出另外一些比特量子比特，并且可以讓我們從輸出的量子比特中一眼就可以看出其中 $f(x)$ 是Constant操作還是Balanced操作。

聽上去這個 $U$ 電路一定很難設(shè)計，實際卻是不難，它只要滿足能夠把 $|x>|y$ 映射成為 $|x>|y\oplus f(x)>$ 即可：

$U:|x>|y>\Rightarrow|x>|y\oplus f(x)>$

這里的圓圈加號 $\oplus$ 的意思是異或，即：

$0\oplus 0=0$

$1\oplus 1=0$

$1\oplus 0=1$

$0\oplus 1=1$

異或即相同得0，相異得1。這里有些有趣的規(guī)律：

異或看起來和CNOT門很像，第一位是0的結(jié)果和第二位相同，第一位是1的結(jié)果和第二位相反。
兩位順序顛倒也能成立，第二位是0的時候，結(jié)果和第一位相同，第二位是1的時候，結(jié)果和第一位相反。

關(guān)于CNOT門，參照【科普】量子計算通識-3-CNOT可控非門

總之我們先記住 $U$ 操作就是把輸入的兩個量子位變成輸出的另外兩個量子位，輸出中的后一位是第二個輸入位和 $f$ 函數(shù)輸入第一位的異或結(jié)果：

$U:|x>|y>\Rightarrow|x>|y\oplus f(x)>$

實際上我們只要根據(jù)輸出的 $|x>$ 就可以判斷出 $f(x)$ 屬于Constant還是Balanced操作，下面我們進行推理演算 $n=1$ 即2個比特位的情況。

計算Hadamard之后的 $\Psi_1$

如圖，我們輸入兩個量子比特，一個0一個1，所以
$\Psi_0=|0>|1>$

下面來計算兩個比特分別經(jīng)過Hadamard門之后的 $\Psi_1$ 。

關(guān)于哈達瑪門，相當(dāng)于乘以一個特殊矩陣，即 $H=\frac{1}{\sqrt{2}}\begin{pmatrix}1,1\\1,-1\end{pmatrix}$ ，即 $|0>$ 變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cfrac%7B%7C0%3E%2B%7C1%3E%7D%7B%5Csqrt%7B2%7D%7D" alt="\frac{|0>+|1>}{\sqrt{2}}" mathimg="1">，即 $|1>$ 變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cfrac%7B%7C0%3E-%7C1%3E%7D%7B%5Csqrt%7B2%7D%7D" alt="\frac{|0>-|1>}{\sqrt{2}}" mathimg="1">，更多請參照【科普】量子計算通識-5-哈達瑪門與單位圓狀態(tài)機

$\begin{align} \Psi_1&=H|0>\otimes H|1>=(\frac{|0>+|1>}{\sqrt{2}})\otimes (\frac{|0>-|1>}{\sqrt{2}})\\ &=\frac{1}{2}(|0>+|1>)(|0>- |1>) \end{align}$

計算U之后的 $\Psi_2$

針對函數(shù) $U$ ，由于我們有：

$U:|x>|y>\Rightarrow|x>|y\oplus f(x)>$

所以經(jīng)過 $U$ 把 $|x>|y>$ 替換為 $|x>|y\oplus f(x)>$ 之后的 $\Psi_1$ 就變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5CPsi_2" alt="\Psi_2" mathimg="1">：

$\begin{align} \Psi_1&=\frac{1}{2}(|0>+|1>)(|0>-|1>)\\ &=\frac{1}{2}(|0>|0>-|0>|1>+|1>|0>-|1>|1>)\\ \end{align}$

$\begin{align} \Psi_2&=U:\Psi_1\\ &=\frac{1}{2}(|0>|0\oplus f(0)>-|0>|1\oplus f(0)>+|1>|0\oplus f(1)>-|1>|1\oplus f(1)>)\\ &=\frac{1}{2}(|0>(|0\oplus f(0)>-|1\oplus f(0)>)+|1>(|0\oplus f(1)>-|1\oplus f(1)>)) \end{align}$

我們注意到按照約定， $f(0)$ 只能取0或1，那么

當(dāng) $f(0)=0$ 時， $(-1)^{f(0)}=1$ ，并且有：
$|0\oplus f(0)>-|1\oplus f(0)>=|0\oplus 0>-|1\oplus 0>=|0>-|1>=(-1)^{f(0)}(|0>-|1>)$

當(dāng) $f(0)=1$ 時， $(-1)^{f(0)}=-1$ ，并且有：
$|0\oplus f(0)>-|1\oplus f(0)>=|0\oplus 1>-|1\oplus 1>=|1>-|0>=(-1)^{f(0)}(|0>-|1>)$

結(jié)合這兩種情況，一定有：
$|0\oplus f(0)>-|1\oplus f(0)>=(-1)^{f(0)}(|0>-|1>)$

同樣的道理， $f(1)$ 也可以等于0或1，所以也會有：
$|0\oplus f(1)>-|1\oplus f(1)>=(-1)^{f(1)}(|0>-|1>)$

把這兩個式子帶入 $\Psi_2$ 得到：

$\begin{align} \Psi_2&=\frac{1}{2}(|0>(|0\oplus f(0)>-|1\oplus f(0)>)+|1>(|0\oplus f(1)>-|1\oplus f(1)>))\\ &=\frac{1}{2}((-1)^{f(0)}|0>(|0>-|1>)+(-1)^{f(1)}|1>(|0>-|1>))\\ &=\frac{1}{2}((-1)^{f(0)}|0>+(-1)^{f(1)}|1>)(|0>-|1>)\\ \end{align}$

計算U之后的 $\Psi_3$

對 $\Psi_2$ 乘以Hadamard矩陣，即 $|0>$ 變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cfrac%7B%7C0%3E%2B%7C1%3E%7D%7B%5Csqrt%7B2%7D%7D" alt="\frac{|0>+|1>}{\sqrt{2}}" mathimg="1">，即 $|1>$ 變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cfrac%7B%7C0%3E-%7C1%3E%7D%7B%5Csqrt%7B2%7D%7D" alt="\frac{|0>-|1>}{\sqrt{2}}" mathimg="1">，這就得到 $\Psi_3$ 。注意如圖所示，是整體進行操作而不是每一位分別Hadamard操作：

$\begin{align} \Psi_3&=\frac{1}{2}((-1)^{f(0)}|0>+(-1)^{f(1)}|1>)(|0>-|1>)\\ &=\frac{1}{2}((-1)^{f(0)}\frac{|0>+|1>}{\sqrt{2}}+(-1)^{f(1)}\frac{|0>-|1>}{\sqrt{2}})(|0>-|1>)\\ &=((-1)^{f(0)}\frac{|0>+|1>}{2}+(-1)^{f(1)}\frac{|0>-|1>}{2})(\frac{|0>-|1>}{\sqrt{2}})\\ &=(\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>)(\frac{|0>-|1>}{\sqrt{2}})\\ \end{align}$

測量結(jié)果

$\Psi_3$ 式子有點長，但我們只關(guān)注前面括號內(nèi)的部分，也就是 $\Psi_3$ 要被 $M$ 測量的部分：

$\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>$

注意 $|0>$ 和 $|1>$ 對應(yīng)系數(shù)的兩個分母實際是A+B和A-B的格式，那么假設(shè) $f(x)$ 是Constant即 $f(0)=f(1)=0$ 那么這個結(jié)果就是：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f( 0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{(-1)^0+(-1)^0}{2}|0>+\frac{(-1)^0-(-1)^0}{2}|1>\\ &=\frac{2}{2}|0>+\frac{0}{2}|1>\\ &=|0>\\ \end{align}$

如果 $f(0)=f(1)=1$ ，那么結(jié)果也類似的：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{(-1)^1+(-1)^1}{2}|0>+\frac{(-1)^1-(-1)^1}{2}|1>\\ &=\frac{-2}{2}|0>+\frac{0}{2}|1>\\ &=-|0>\\ \end{align}$

對于 $M$ 測量操作求平方計算結(jié)果來說， $|0>$ 和 $-|0>$ 結(jié)果都是0。

關(guān)于測量請參照這里【科普】量子計算通識-4-量子位

但是，如果 $f(x)$ 是個Balanced操作，即 $f(0)=1-f(1)$ 結(jié)果會怎樣？

如果 $f(0)=1$ ， $f(1)=0$ ，那么：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{-1+1}{2}|0>+\frac{-1-1}{2}|1>\\ &=-|1>\\ \end{align}$

如果 $f(0)=0$ ， $f(1)=1$ ，那么：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{1-1}{2}|0>+\frac{1-(-1)}{2}|1>\\ &=|1>\\ \end{align}$

綜上，如果我們最后 $M$ 測量的結(jié)果是0，那么 $f(x)$ 一定是Constant操作，如果我們最后 $M$ 測量的結(jié)果是1，那么 $f(x)$ 一定是Balanced操作。

這里只針對 $n=1$ ，也就是兩個量子位的計算，后面我們來推導(dǎo)多個量子位的情況。

下一篇：【科普】量子計算通識-8-Deutsch-Jozsa算法解析

歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識】
更多相關(guān)文章請點擊【量子計算通識】

每個人的智能新時代

如果您發(fā)現(xiàn)文章錯誤，請不吝留言指正；
如果您覺得有用，請點喜歡；
如果您覺得很有用，歡迎轉(zhuǎn)載~

END

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【科普】量子計算通識-7-Deutsch算法解析

【科普】量子計算通識-7-Deutsch算法解析

多伊奇問題

經(jīng)典計算機解法

量子計算解法

計算Hadamard之后的 $\Psi_1$

計算U之后的 $\Psi_2$

計算U之后的 $\Psi_3$

測量結(jié)果

每個人的智能新時代

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【科普】量子計算通識-7-Deutsch算法解析

多伊奇問題

經(jīng)典計算機解法

量子計算解法

計算Hadamard之后的

計算U之后的

計算U之后的

測量結(jié)果

每個人的智能新時代

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

計算Hadamard之后的 $\Psi_1$

計算U之后的 $\Psi_2$

計算U之后的 $\Psi_3$