量子計算的hello world——Deutsch演算法程序演示（僅需線性代數基礎）

來自專欄希爾伯特空間魁比特郡4 人贊了文章

1. 引子

量子計算好神秘哦！學IT的人該如何理解？為啥量子計算這麼牛？能否寫個量子計算版的hello world程序來耍耍感受一下？這些問題是身邊的同事經常問我的問題。雖然知乎上或者其他網站都有好些量子計算的科普，可惜對外行仍是有很多理解上的障礙，也往往沒有法子從程序運行來直觀感受。

現在這個帖子不是去過多地重複量子計算原理，只是從一個hello world程序來牽引我們對量子計算的理解。所幸的是，目前有好幾家單位都提供了量子計算的雲服務，比如IBM、清華大學、微軟、阿里等，方便大家試用，在上面做實驗，比如接下來的hello world程序。

首先定義我們這個hello world要做啥。僅僅列印一句「hello world」應該不能滿足大家的胃口，至少我們得找個例子來演示量子計算相對經典計算的優越性吧。當然，這個例子越簡單越好哈。早在1985年，也就是Feynman同學提出「量子計算」概念的第二年，Deutsch同學就設想了這麼個例子，我們直接借鑒就好。下面的介紹只需具備線性代數的基礎即可（flag先立在這裡，我儘力哈）

2. 問題定義：最簡單的量子計算——Deutsch問題

這個問題具體是這樣的：考慮自變數和因變數取值均為0或1的函數 ，比如 , 。可以看出，前兩個函數 屬於「常量函數」（在原文里稱為constant函數），即 ；而後兩個函數 屬於「平衡函數」（在原文里稱為balanced函數），即如果 的取0或1的幾率相等的話，函數值 和 的幾率也是相等的。問題是，把某個函數 看成黑盒子，你只能通過輸入一系列的值來測試，那麼需要輸入多少次，能夠確認這個函數是屬於「常量函數」還是「平衡函數」？

我們先看看經典計算機的解法。很明顯，我們只需要分別輸入0和1，運行 兩次，就可以確認答案。比如先輸入 ，假設我們運行黑盒子發現 ，那麼 可能是 或者是 。接著輸入 就可以確定具體是哪個。

而利用量子計算機，我們只需要運行 一次，就能確認答案，具體做法稍後詳解。也許你會說這並不是很明顯的優勢，但是當把輸入變成多元函數，就不一樣了。對於經典計算機，演算法複雜度是指數級的。而量子演算法可以始終保持只需運行一次即可。換言之，在這個問題上，量子計算帶來了指數級的收益。

是不是很神奇？在具體解釋原理之前，我們先看看演算法的量子線路和運行結果是啥樣子的。

3. Deutsch演算法的量子線路和運行結果示例

我們這裡考慮3元函數， （ 為異或運算，即兩個邏輯變數相異，輸出才為1），很明顯它是一個「平衡函數」，因為不管 取值如何，只要 取值改變，函數 的取值也跟著改變。

在阿里量子計算雲（網址：http://quantumcomputer.ac.cn，也可以嘗試其他平台哈），我們搭建量子線路如下：

我知道這可能看上去不明所以然，容我稍後分解，這裡只指出，第2列的Z門和CZ門（即那個太陽鏡哈）就實現了上面說的 （不妨作為一個練習）。先看運行結果：

這個結果應該這樣解讀，對於第一個變數 ，它由量子比特 承載，輸入為0（量子線路上所有量子比特 均初始化為0），輸出為1（通過幾率分布來體現），因此它是「平衡函數」（反之，輸出若為0，則它是「常量函數」）。這和我們一開始對函數的定義 是一致的。至於為什麼需要這樣解讀，就是演算法設計的緣故了。

4. Deutsch演算法原理

為了理解Deutsch演算法，我們先看看干涉實驗。它體現的概率相加相減，後續會結合我們要考察的函數，最終匯總起來，得到函數的分類。在量子力學裡（或者你們喜歡的薛定諤貓身上），粒子（貓）具有波動性，在通過雙縫後，在探測器上會出現明暗條：

稍微把上述實驗推廣一下。設想有 個探測器，從源到每個探測器有 條可能的路徑。

（未完待更新哈）

推薦閱讀：