3. 量子圖靈機 --- 量子計算機有多快

04-27

丘奇-圖靈-德意奇論題(Church-Turing-Deutsch Thesis)

1936年，太平洋西岸還在一片戰火紛飛中，美洲大陸的普林斯頓寧靜的校園裡卻也在悄悄的改變世界。教授阿隆佐丘奇和他的博士生圖靈分別利用自己發明的 $lambda$ 演算和圖靈機模型，提交了論文來探討計算的極限是什麼。他們的結論（猜想）之後被稱為「丘奇-圖靈」論題：

「所有可以有效計算的函數都可以被通用圖靈機計算。」

這句（意義稍顯含混不清的也沒有被證明過的）話直接奠定了之後計算機科學蓬勃發展的基礎。方向已經被指得很明顯：造出圖靈機吧，之後(幾乎)就沒有我們不能做的了（當然不包括不可判定問題們，圖靈他們的本意其實就是向希爾伯特證明存在不可判定問題）。

之所以叫做論題而不是猜想是因為：1.「可以有效計算的函數」本身就沒有過準確定義，於是不可能被證明。2. 幾乎沒有人在乎證明，圖靈機明顯已經無比強大了。

於是人類最偉大的信息革命就在這句模糊而又目標遠大的話中開始爆發。

時間飛轉至49年後的1985年，另外一場革命也開始孕育。英國物理學家德意奇(David Deutsch)發表了關於「量子圖靈機」的論文。德意奇肯定看了3年前費曼的論文，「simulating physics with computers"，其中費曼第一次提出了利用量子力學來實現計算。之後一些物理學家，包括來自阿貢國家實驗室的Paul Benioff，從物理上也設計出了一些模型，表示從能量等角度，費曼的設想沒有問題，物理上是可以實現的。德意奇開始想如果這些物理學家所說的量子計算機可以實現的話，那麼一定也要限定可計算的範圍，也一定有一個量子版本的「丘奇-圖靈論題」。而他論文中提出的這個版本（丘奇-圖靈-德意奇論題），比原版要好太多：

「所有（有限的可以實現的）物理系統都可以被一台通用計算機器來模擬。」

其中所有的名詞都可以被準確定義。而它的哲學意義和現實意義更是深遠。在現實上看，現在的我們發現模擬各種物理系統已經是所有理工科的日常之一，從飛機機翼周圍氣流的流體力學到宇宙的演化到分子動力學，無一不有計算機模擬參與。從哲學意義上看，我們的世界可不可能就是運行在一台機器上的模擬程序？如果這個論題為真，是不是意味著世界就是完全可以被理解的了（只要能理解這台機器就能理解世界）？不過隨著弦論等高深的物理理論的出現，現在所有的物理理論和科學家們越來越明顯的傾向於這個論題為假。

量子圖靈機

所幸的是在限定為量子力學系統後，德意奇證明了他論文後面所定義的量子圖靈機可以模擬所有物理系統---這便奠定了現在所有設想利用量子計算機模擬量子系統的想法的理論基礎。基於量子物理，德意奇的量子圖靈機(Quantum Turing Machine, QTM)和圖靈的概率圖靈機(Probabilistic TM，PTM)定義非常類似，幾乎可以沿用紙帶模型(在此假設讀者熟悉概率圖靈機)。QTM由：

字符集 $Sigma={B, b_1,b_2...}$ 。其中 $B$ 是代表空字元。和圖靈機一樣，只要可數，字符集的元素個數完全不影響。於是我們和經典計算機一樣，一般都取0， 1，空字元的集合。
探針狀態 $Q={q_0,q_1,...,q_f}$ 。其中 $q_0$ 為初始探針狀態， $q_f$ 為末態探針狀態。
內存(紙帶)空間 $M={m|m={s_i}, s_iin Sigma, iin mathbb{Z}}$ 。意思為紙帶空間是具體的紙帶配置(configuration)的集合。一個紙帶配置是一個把紙帶用字元塗滿的方式（可以用空字元）。我們還用字母 $d$ 來表示當時QTM的探頭(probe)位置。探頭位置表示內存紙帶上被探頭指向並且將改寫的格子位置。
狀態轉移函數 $sigma=Q imes M imes Q imes M imes [-1,1]_{mathbb{Z}} ightarrow mathbb{C}$ 。這個可以理解為給定圖靈機狀態 $(q_1, m_1 ) in Q imes M$ 和任意另一狀態 $(q_2,m_2) in Q imes M$ , $sigma$ 可以給出一個複數，而這個複數的共扼平方(模平方)就是從 $(q_1,m_1)$ 轉移到 $(q_2,m_2)$ 的概率。然後探頭位置可以左移或者右移一位（因為量子計算是可逆計算，所以探頭必須也可以向左移動）。

組成。

到此為止QTM的結構和經典（概率）圖靈機幾乎無區別，除開概率是模平方。於是現在要把它量子化，變成一個希爾伯特空間。因為TM本身就是離散的，形式上這一步很簡單：只要把QTM裡面探針的任意狀態從 $(q,m,d)$ 改作 $|q;m;d>$ 便是，然後把所有的 $|q;m;d>$ 想作一個無限維希爾伯特空間的一組正交基便可。量子系統的演化(evolution)必須由酉矩陣(Unitary Matrix)完成，於是狀態轉移函數必須也保證模平方之和為1。QTM的運行就是從初始狀態開始不斷執行狀態轉移，直到到達終止狀態。

QTM和PTM的最大區別就在於：1. PTM執行每一步後都會進行觀測，從而它永遠在一個確定的狀態上，之前的其他信息都損失掉了，而QTM只在最後一步進行觀測，中間的無數可能性和無數的信息都被包含在了最後的狀態(這一點和NTM更類似)。2. 恰好就是因為概率是模平方之和為1而不是直接相加為1, 量子概率可以把一些可能性抵消，於是放大一些我們需要的結果。比如一個經典的例子就是進行兩次Hadamard操作：如果QTM有兩個狀態，和|1>，我們可以寫成向量的形式 $|0>=[matrix{1\0}]$ ， $|1>=[matrix{0\1}]$ ,再假設有一個叫Hadamard的(概率)狀態轉移函數定義如下： $frac{1}{sqrt{2}}[matrix{1&1\1&-1}]$ 。假如我們之前在狀態|0>上，那麼執行這個(概率)狀態轉移函數兩次我們得到一個確定的結果：

$frac{1}{sqrt{2}}[matrix{1&1\1&-1}] imesfrac{1}{sqrt{2}}[matrix{1&1\1&-1}] imes[matrix{1\0}]=frac{1}{sqrt{2}}[matrix{1&1\1&-1}] imesfrac{1}{sqrt{2}}[matrix{1\1}]=[matrix{1\0}]$

先轉移到一個不確定的狀態，再轉移到一個確定的狀態。這是使用PTM時難以想像的。

而QTM和非確定圖靈機(Nondeterministic TM,NTM)的區別在於：在最後的狀態中，QTM只能以一定概率取出所有可能性中的一種，而NTM假設我們知道最後狀態的所有信息。

量子計算機有多快

現在我們都知道，圖靈機是現代計算機的原型(Prototype)。而原型的作用在於，在避開8核，256Gb SSD, DDR4等這些參數和名詞之後，我們能準確的知道一台計算機能做什麼，不能做什麼，能有多塊。更精確的說，它用來定義複雜度類(Complexity class)。複雜度類以各種原型能解決與否，來把問題分類。

以下是一些複雜度類(詳細請參見Introduction to the Theory of Computation by Michael Sisper)：

在多項式時間內能被圖靈機(TM)決定的問題屬於P。
在多項式時間內能被非確定圖靈機(Non-deterministic TM)決定的問題屬於NP。
在多項式時間內能被概率圖靈機(Probabilistic TM)以大於2/3的概率(或者任意確定的大於1/2)決定的問題屬於BPP。BPP被普遍認為是可以被計算機有效計算的。
在多項式時間內能被概率圖靈機(Probabilistic TM)以大於1/2的概率(這個概率可以取決於輸入長度 $n$ , 比如 $(50+ frac{1}{n})$ %)決定的問題屬於PP。這個類幾乎是只存在在理論上，因為離1/2太近的概率我們不運行很多次(指數級別)是分辨不出來的。
能只用多項式空間就決定的問題屬於Pspace。
能在指數時間內決定的問題屬於Exp。
在多項式時間內能被量子圖靈機(Probabilistic TM)以大於2/3的概率(或者任意確定的大於1/2)決定的問題屬於BQP。

多項式時間/空間意思是演算法的操作步數(number of steps)在O(n^k)的範圍內，n是輸入圖靈機的字元串的長度，k是任意常數。

P和NP還有函數版本，把1和2中的「決定」換成「計算出」即可，有些地方叫他們作FP, FNP, 很多地方也就放在P和NP裡面了。還有很多別的有意思的複雜度類，比如芝加哥大學的教授Laszlo Babai提出的MA(Merlin Arthur), 亞瑟梅林協議。MA基於以歐洲中古傳說的兩個人物命名的互動式證明系統。基本想法是：想像一個無所不能的魔法師梅林（一個假設能力很強的TM）是證明者，而勇武有力的亞瑟王（一個Probabilistic TM）是個驗證者，亞瑟不能完全相信神秘莫測的梅林，從而需要在自己能力範圍內測試梅林是否誠實，如果一個問題他們倆在有限輪交互內能驗證就屬於MA。當然MA也有量子版本，把驗證者換成QTM則成了QMA。更一般的互動式證明系統是IP, 其中驗證者可以是任何TM。互動式證明系統非常重要也非常有趣，以後如有機會我們可以細談。

到現在為止，複雜度類已經有513個，他們都被收錄在理論計算機學家Scott Aaronson創立的Complexity Zoo里。

大家都非常關心哪些問題屬於哪個複雜度類，一些有名的例子有，

SAT問題。給定一個布爾表達式，比如(a and b) or (a and not b)，能否找到a, b屬於{true, false}使得這個表達式為真。雖然看上去很簡單，但是非常出人意料的它屬於NP。而且所有NP問題都可以歸化於它(1982圖靈獎，Stephen Cook)。
質因數分解。還不知道屬於P還是NP。
圖同構。給定兩幅圖，確定他們是否是可以一一對應的。還不知道屬於P還是NP。

大家也關心複雜度類之間的關係，然而這非常複雜：P是否等於NP, P是否等於BPP等都是著名的懸而未決的問題。

現在的問題是：BQP在複雜度類的哪個位置？

首先，BPP肯定屬於BQP。對於每一台PTM，我們可以構造一台QTM使得狀態轉移函數里的(模平方)概率等於PTM裡面的概率即可。這可以讓人稍微心安：量子計算機至少和經典計算機一樣快。

但是人們最關心的問題是：BQP和NP是什麼關係？BQP和P是什麼關係？從上面QTM和NTM的分析來看，因為最後一步可以儲存機器中所有的信息，NTM貌似要更強大，所以NP似乎包含BQP，。但是直覺往往是不準的，我們連P是否是等於NP都不知道。

到現在我們也不知道以上問題的答案。這也使得九十年代初期人們對量子計算機開始心灰意冷--- 我們為什麼要花大價錢造一台不知道有多快的機器？直到94年彼得秀爾(Peter Shor)提出質數分解演算法才拯救了量子世界---至少有一個我們還不知道怎麼有效解決的問題可以被量子計算機以指數級別的加速解決了。

陸陸續續一直有新的量子演算法提出，也有些複雜度理論的結論出現（比如2009年證明的QIP=Pspace）但是BQP在複雜度這個動物園裡到底在哪我們還一直找不到。但是因為秀爾演算法和格羅夫演算法，人們還是以極大的熱情在建造量子計算機。

所以，問題的答案是：我們也不知道量子計算機有多快，但是有些特定問題它比經典計算機要快很多。

其實從某種意義上來說，量子圖靈機已經是一個有點「過時」的概念了，很少有人使用：首先，量子圖靈機模型只是告訴我們了量子計算機的下限（至少和經典計算機一樣快），卻並沒有真正告訴我們它真正能有多快。其次，經典圖靈機的令人振奮之處在於圖靈構造了通用圖靈機，一台「無所不能」的圖靈機，而Umesh Vazirani的通用量子圖靈機也是用的一台經典圖靈機構造的，而使得使用這個過於抽象的概念讓人有點興趣索然，不過這也奠定了現在「經典控制，量子數據」(Classical control, quantum data)的思路。第三點，也是最重要的一點，1993年姚期智教授證明了方便直觀很多的量子線路模型可以在多項式時間內模擬任何量子圖靈機，這個模型一直沿用至今。但是從歷史角度講，它還是非常重要，有一個非常重要的結論就是用量子圖靈機模型證明的：做T步的量子計算，我們對概率幅的精度只需要O(log T)。這保證了量子計算機是「數位」(digital)的，而不是「模擬"(analog)的, 所以我們能造出來。XD

德意奇的Twitter: https://twitter.com/DavidDeutschOxf

Paul Benioff的主頁：Argonne Physics Division

Umesh Vazirani的主頁：Home Page For Umesh Vazirani

複雜性動物園： Complexity Zoo