【科普】量子計(jì)算通識(shí)-6-Deutsch多伊奇算法

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

以下內(nèi)容參照微軟研究院主題演講《Quantum Computing for Computer Scientists（計(jì)算機(jī)科學(xué)家量子計(jì)算導(dǎo)讀）》的結(jié)構(gòu)進(jìn)行整理和擴(kuò)充的。
本篇是第六部分。上一篇【科普】量子計(jì)算通識(shí)-5

多伊奇問題Deutsch Problem

量子計(jì)算能做什么？有什么優(yōu)勢(shì)？
我們從最簡(jiǎn)單的多伊奇問題開始。

首先，我們知道，對(duì)于一個(gè)比特進(jìn)行操作，有四種方法：不變，翻轉(zhuǎn)，等0，等1，它們都可以表示成用一個(gè)矩陣相乘的模式。

  • f(x)=x
    \begin{pmatrix}1,0\\0,1\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0 \qquad \begin{pmatrix}1,0\\0,1\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}0\\1\end{pmatrix}=1
  • f(x)=﹁x
    \begin{pmatrix}0,1\\1,0\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}0\\1\end{pmatrix}=1 \qquad \begin{pmatrix}0,1\\1,0\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0
  • f(x)=0
    \begin{pmatrix}1,1\\0,0\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0 \qquad \begin{pmatrix}1,1\\0,0\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0
  • f(x)=1

這四種操作又可以根據(jù)輸入輸出的對(duì)比分為兩種情況：

  • 情況A：變量結(jié)果variable，不變和翻轉(zhuǎn)都屬于這種，它們的輸出結(jié)果可能是0也可能是1。這種變量結(jié)果也可以叫做平衡結(jié)果Balanced，因?yàn)榻Y(jié)果有一半情況下是輸出0，另一半情況下輸出1。另外注意，這兩種操作都是可逆的，就是說(shuō)如果你知道是翻轉(zhuǎn)操作并且結(jié)果輸出1，那么就可以推算輸入是0。

  • 情況B：常量結(jié)果constant，等0和等1都屬于這種，他們的輸出結(jié)果是固定的，永遠(yuǎn)等于0或者等于1，不會(huì)因?yàn)檩斎氩煌煌＿@兩種操作是不可逆的，也就是說(shuō)即使你知道是等0操作并且知道操作結(jié)果輸出0，也不能推理出輸入的數(shù)值是0還是1。

現(xiàn)在問題是，假設(shè)有一個(gè)函數(shù)操作f'，我們只知道它是四種操作里的一種，但我們可以用輸入輸出進(jìn)行測(cè)試，那么，要確定f'屬于情況A（變量可逆）還是情況B（常數(shù)不可逆），我們最少做幾次測(cè)試？

David Deutsc大衛(wèi)·多伊奇

這個(gè)問題最早是英國(guó)物理學(xué)家David Deutsch提出來(lái)的，當(dāng)然他也提出了量子算法的解決方案。

經(jīng)典計(jì)算機(jī)解決方案

用經(jīng)典計(jì)算機(jī)來(lái)判斷f'到底是情況A（變量結(jié)果操作）還是情況B（常量結(jié)果操作），必須要經(jīng)過(guò)兩次嘗試，第一次輸入0觀看結(jié)果，第二次輸入1觀看結(jié)果。

  • 第一次輸入0輸出是0，那么f'可能是不變，也可能是等0。
  • 第一次輸入0輸出是1，那么f'可能是翻轉(zhuǎn)，也可能是等1。
  • 第一次輸入1輸出是0，那么f'可能是翻轉(zhuǎn)，也可能是等0。
  • 第一次輸入1輸出是1，那么f'可能是不變，也可能是等1。

所以，必須至少嘗試兩次，第一次輸入0，第二次輸入1或者相反：

  • 0\to0,1\to1\quad\Rightarrow f(x)=x，不變，情況A變量
  • 0\to0,1\to0\quad\Rightarrow f(x)=0，等0，情況B常量
  • 0\to1,1\to1\quad\Rightarrow f(x)=1，等1，情況B常量
  • 0\to1,1\to0\quad\Rightarrow f(x)=﹁x，翻轉(zhuǎn)，情況A變量

我們經(jīng)過(guò)兩次經(jīng)典計(jì)算可以確定f'屬于變量操作或者常量操作。

雖然我們也可以確定到它屬于四種操作中的哪一種，但其實(shí)這個(gè)信息是不必要的，又是不得已而為之的，因?yàn)槲覀冎恍枰袛嘧兞炕蛘叱Ａ考纯伞?/p>

重新組裝

在量子計(jì)算中我們要求所有操作都是可逆的，那么我們先對(duì)四種位操作進(jìn)行重新布線，也就是說(shuō)設(shè)計(jì)四種可逆的量子位操作線路，或者說(shuō)四種算法。當(dāng)然，這四種算法也必須滿足實(shí)現(xiàn)四種操作：

在這里我們輸入兩個(gè)量子位InputA和InputB，其中InputA是固定的|0>，你可以把它視為冗余的輔助輸入；同樣輸出的OutputA是真正的操作結(jié)果，而OutputB也可以視為冗余的副產(chǎn)品。

為什么設(shè)計(jì)成這樣的線路？先不急，我們先看在這個(gè)結(jié)構(gòu)下如何實(shí)現(xiàn)四種可逆的量子位操作。

  • 等0操作線路，直接把InputA(|0>)輸出到OuputA，這就確保了OutputA固定為|0>；而至于冗余的OutputB也直接連接到InputB即可。如下圖：

  • 等1操作線路，和等0線路差不多，把InputA線路上面添加一個(gè)非門就可以確保OutputA固定為|1>了。如下圖：

  • 不變操作線路，這個(gè)就有點(diǎn)復(fù)雜了，注意這里是個(gè)CNOT可控非門，InputB是控制位，InputA是目標(biāo)被控位。所以，如果InputB是|0>，那么InputA
    穿過(guò)連線不變輸出OutputA的就還是|0>，而正好和控制位InputB相同；如果InputB是|0>是|1>，那么InputA的|0>穿過(guò)連線被翻轉(zhuǎn)輸出OutputA就是|1>，也正好和控制位InputB相同。
  • 翻轉(zhuǎn)操作線路，只要在不變操作的基礎(chǔ)上增加一個(gè)翻轉(zhuǎn)操作就可以了。

注意上面四個(gè)圖的OutputA，分別是|0>、|1>、|x>、|﹁x>，這正對(duì)應(yīng)了量子比特的四種操作。

Deutsch多伊奇算法

有了上面四種操作全新的可逆線路算法，我們用一次測(cè)試就可以確定F'是變量操作還是常量操作了。

首先我們把F'(x)當(dāng)做一個(gè)未知的黑盒子，并向兩端增加一些翻轉(zhuǎn)操作（X）、Hadamard門操作（H）和一些測(cè)量Measure操作（M），組成下面的測(cè)試電路：

從圖中可知，我們的兩個(gè)輸入InputA和InputB都是|0>，那么我們來(lái)看一下在等0、等1、不變、翻轉(zhuǎn)四種不同的操作情況下輸出的結(jié)果都是什么。

在此之前，我們先把左側(cè)的翻轉(zhuǎn)（X）和Hadamard（H）處理出來(lái)：

InputA和InputB，都是|0>，經(jīng)過(guò)-X-H-后得到\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}：

我們把這個(gè)點(diǎn)作為進(jìn)入未知黑盒F'的起點(diǎn)，下面用藍(lán)色圓點(diǎn)表示。

  • 假設(shè)F'是等0操作，那么經(jīng)過(guò)F'(x)沒變化，然后經(jīng)過(guò)右邊的Hadamard門結(jié)果是\begin{pmatrix}0\\ 1\end{pmatrix}，測(cè)量結(jié)果是1，聯(lián)合OutputA和OutputB得到|11>：

  • 假設(shè)F'是等1操作，那么如下圖，OutputA多經(jīng)歷一次翻轉(zhuǎn)（X），再經(jīng)過(guò)Hadamard門（H）之后到達(dá)了 \begin{pmatrix}0 \\-1\end{pmatrix}，但測(cè)量結(jié)果還是1，聯(lián)合OutputA和OutputB仍然得到|11>

  • 假設(shè)F'是不變操作，那么情況會(huì)復(fù)雜一些，我們有下圖：

但OutputA是怎么回事？首先我們知道這是個(gè)CNOT可控非門操作，而CNOT就是乘以一個(gè)特別的矩陣，我們有如下公式：

\begin{align} &C\begin{pmatrix} \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix} \end{pmatrix}=C\begin{pmatrix} \frac{1}{2}\\\frac{-1}{2}\\\frac{-1}{2}\\\frac{1}{2}\\ \end{pmatrix}\\ &=\frac{1}{2}\begin{pmatrix}1,0,0,0\\0,1,0,0\\0,0,0,1\\0,0,1,0\end{pmatrix} \begin{pmatrix}1\\-1\\-1\\1\end{pmatrix}\\ &=\frac{1}{2} \begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}= \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix} \end{align}
注意這里最后一步的巧妙之處在于開頭的CNOT操作相當(dāng)于把兩個(gè)\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}的張量積轉(zhuǎn)換為\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{pmatrix}和\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}的張量積，簡(jiǎn)化后就是：

C\begin{pmatrix} \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix} \end{pmatrix}=\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}

所以有上圖，OutputA是\begin{pmatrix}1\\ 0\end{pmatrix}測(cè)量后是|0>，聯(lián)合OutputA和OutputB仍然得到|01>

  • 假設(shè)F'是翻轉(zhuǎn)操作，那么相當(dāng)于比不變操作多了一個(gè)翻轉(zhuǎn)，如下圖所示，注意這里OutputA的翻轉(zhuǎn)（X）操作仍然在原地，所以最終聯(lián)合OutputA和OutputB仍然得到|01>

綜合上面四種情況，我們得到：

  • 等0操作結(jié)果是|11>
  • 等1操作結(jié)果是|11>
  • 不變操作結(jié)果是|01>
  • 翻轉(zhuǎn)操作結(jié)果是|01>

所以，輸入InputA和InputB兩個(gè)都是|0>，如果結(jié)果是|11>，那么F'就是個(gè)常量操作，如果結(jié)果是|01>，那么F'就是個(gè)變量操作。

只要一次操作就完成了！速度快了一倍！

下一篇：【科普】量子計(jì)算通識(shí)-7-Deutsch算法解析

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

每個(gè)人的智能新時(shí)代

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

END

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

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