從比特到量子比特，量子計算爲什麼快？｜量子計算羣英會（四）

圖1：貝尼奧夫

在MIT1981年的第一屆“計算與物理”的大會上，除了費曼給出一個關於模擬量子計算的演講之外，另一位科學家，保羅·貝尼奧夫（Paul Benioff，1930-2022）也作了一個重要的演講。貝尼奧夫報告的主要內容是基於他在1980年發表的文章，其中主要討論了圖靈量子計算機，及其實現的可能性等等。

貝尼奧夫在 20 世紀 80 年代初發表了四篇論文，爲量子計算的基礎做出了開創性貢獻。他首次證明量子計算機在理論上是可行的，可以構建量子系統來傳遞信息或執行極其複雜的計算。

貝尼奧夫的工作，討論了關於計算機模型的形式。大部分的經典計算機模型都是開放耗散系統，量子計算機模型是否能通過封閉且能量守恆的系統構造呢？貝尼奧夫在他的論文中，構造了這樣幾乎無能量耗散的計算模型。

1

經典圖靈機

首先簡要介紹圖靈機，這是計算機的一個常用的理論模型，由英國人圖靈提出並以他命名。

阿蘭·圖靈（Alan Turing，1912-1954）如今被譽爲計算機之父和人工智能之父，是一位數學天才，傳奇的人物。

著名的數學家希爾伯特在1930年發表他的退職感言中有一句名言：“我們必須知道，我們必將知道”，闡明瞭他的科學哲學觀：認爲數學中沒有不可知之物，任何一個問題都有解。他對數學系統的具體要求，包括滿足“形式化、完備性、一致性、確定性”這幾個要點。也就是說，在形式化的基礎上，必須滿足剩下的三條。

不過，就在第二年，另一位數學家哥德爾便提出不完備性定理，嚴格證明了“完備”和“一致”不可能同時滿足，粉碎了希爾伯特計劃的美夢。

天才的圖靈對此很感興趣，努力鑽研後，用一個巧妙的方法得出了結論：判定性問題無解！

圖靈那年才二十出頭，他花全力構建了一個完美的通用計算機，這個機器可以滿足希爾伯特將“計算”形式化的要求，然後，圖靈用此機器證明了，即使計算機有無限的內存空間，能夠永遠持續計算，對某些問題，也無法在有窮的步驟內給出“是”或者“否”的答案。可以舉“停機問題”爲例說明這點。

什麼叫停機問題呢？對一臺計算機而言，輸入程序w後，計算機開始運轉，可能有兩種結果：1，計算機在有限的時間內結束運算而停機（好結果）；2，計算機進入死循環，永遠停不了（壞結果）。我們當然不希望我們寫出來的程序w產生死循環，最好是在機器運行它之前，就使用某種方法判定一下這個程序w是好是壞。於是我們就想：是不是能有一個另外的程序P，對於任意給定的輸入程序w，能夠判斷w是會停機的好程序，還是會死循環的壞程序？這就叫做停機問題。根據圖靈論文中的證明，不存在判定w“好”或“壞”的程序P，即不存在解決停機問題的通用算法。

計算機的程序可寫成一個函數，例如，上面所說的停機程序P，可以寫成P(w)。P(w) 是一個二值函數：如果結果是停機，P(w)=0；如果結果是死循環，P(w)=1。然後，我們可以用反證法來簡單地證明停機問題無解，證明過程如下。

如果存在一個判斷停機問題的程序P(w)，那麼我們再構造一個新的程序Q(P(w))，這個程序與P的輸出正好相反：如果w經P判斷爲停機，則Q作死循環；如果P判斷w爲死循環，則Q立刻停機。

這時，如果我們把w=Q輸入P，新程序會得到什麼結果呢？結果應該是Q(P(w))= Q(P(Q))。意思是說：P判定Q是死循環，但Q停機了，所以又不是死循環。也就是說，判定的結果是自相矛盾的：說是死循環又能停機，說能停機又變成死循環。因此，出現了計算機判定不了的情況，所以，最初的假設是不正確的，即判定程序P(w)不存在，不能解決停機問題。

圖靈的論文是對希爾伯特計劃的又一個致命打擊，證明了不可能建立一套形式化的數學系統來保證確定性。圖靈的研究結果同時也說明，不可能建立一臺計算機在有窮步內確定任何公式是否可被證明，即人類思維永遠無法被機器取代。

圖2：通用圖靈機

圖靈對計算機和程序給出了嚴格的數學定義，這個模型後來被稱爲通用圖靈機【1】

通用圖靈機的主要結構有三個部分（圖2）：狀態控制器、讀寫頭、一條無限長的紙帶。紙帶想象成由表示0或1的小格子組成，代表無限的內存，其中存儲內容包括初始數據、運算規則、結果等。讀寫頭是可以從帶子上讀、寫、且能左右移動的“頭”，也就是個“掃描器”，掃描器能沿着紙帶來回移動，讀取紙帶上的內容，然後在紙帶上進一步打印出更多的內容。狀態控制器則指揮讀寫頭，控制整個計算過程，就是根據當前機器所處的狀態和當前讀寫頭所指的格子上的符號，通過控制規則，更改狀態寄存器的數值。一個能按照規則的“控制器”。計算過程便是重複讀寫及控制，直到狀態變爲某個特殊狀態，觸發圖靈機停止運算爲止。

改變紙帶上的不同程序，便可以讓機器執行任何“人類計算機”可以執行的過程。需要強調的是：圖靈機並不是某個具體的計算機，而是圖靈爲了定義“算法”提出的抽象模型。

當時對圖靈來說，研究希爾伯特計劃很重要，但那只有數學上的意義。今天看起來，他發明的通用計算機對全人類文明社會意義非凡。

當然，正如前面說過的，即使抽象的通用圖靈機可以模擬所有數學問題，也不能解決所有數學問題，比如“停機問題”。

圖靈在42歲時，因爲他的同性戀傾向遭受迫害而自殺身亡。圖靈死後，人們在他的桌子上，發現一個被咬了一口的含有氰化物的蘋果，頗似現在蘋果公司的符號，不過這只是巧合。

2

貝尼奧夫

保羅·貝尼奧夫1930年出生於美國加州。在加州大學伯克利分校獲得了植物學本科及核化學的博士學位。1960年，貝尼奧夫進入了以色列的魏茨曼科學研究院做博士後。此後他在玻爾研究所從事了六個月的科研工作。從1961年之後，他在美國阿貢國家實驗室工作直到1995年退休。貝尼奧夫於2022年91歲在美國伊利諾伊州去世。

貝尼奧夫在阿貢國家實驗室從事的是化學和環境科學工作，與量子計算技術沒有直接的關係。因此，可以想象，貝尼奧夫的量子計算工作是靠他的“業餘愛好”完成的。也許早年與玻爾共事的一段經歷啓發他思考物理學中的基本問題。他的工作涵蓋量子計算機、量子機器人以及邏輯、數學和物理基礎之間的關係。

貝尼奧夫除了從事量子信息外，還進行傳感研究，探索用於進行實驗的‘量子機器人’的概念。這在當年並不流行，是冷門領域，但他因爲這些研究成爲相關領域的先驅。總之，貝尼奧夫是一位非常有創意的思想家，他並不一定熱衷於探索當時的‘熱門事物。這是值得我們所有人學習的優秀的科學素質。

通用圖靈機的理論是計算學科最核心的理論，那麼，圖靈機的量子版本應該是個什麼樣子，如何實現呢？貝尼奧夫在論文中【2】，將圖靈機中的每個組成部分和操作，與他量子系統中的物理量對應起來。例如，他用自旋爲1/2的粒子串起來的的一維晶格，對應於圖靈機的無限長紙帶。在晶格中的每一個固定位置的自旋粒子，均可作爲寄存器。用一個沿着晶格移動的無自旋粒子，可以構成量子圖靈機的讀寫頭。量子圖靈機的所有可能狀態則由粒子1/2自旋的不同投影組成。量子圖靈機進行的每一步計算，對應於每一個粒子自旋狀態的變化。

圖3：量子圖靈機

貝尼奧夫通過圖靈機的薛定諤方程描述，證明計算機可以在量子力學定律下運行。貝尼奧夫的工作爲量子計算領域鋪平了道路，被公認爲是量子計算機的第一個理論框架。

實際上，將圖3與圖2比較可見，量子圖靈機和經典圖靈機的本質區別說起來很簡單，就是在於用自旋爲1/2的量子疊加態來替代了（0、1）的二進制邏輯。用現在計算機科學的術語來說，就是用量子比特來代替比特。

3

Qubit-來源

量子比特從英語Qubit翻譯而來，這個術語1992 年才被髮明出來並開始使用，它起源於兩位美國理論物理學家伍特斯和舒馬赫之間的一次有趣的對話。

圖4：發明Qubit術語的科學家

威廉·伍特斯（William Wootters，1951-）是一位美國理論物理學家，也是量子信息理論領域的創始人之一，他在 1982 年與Wojciech H. Zurek的聯合論文中，證明了量子不可克隆定理。

本傑明·舒馬赫（Benjamin Schumacher，）也是美國理論物理學家，主要研究領域爲量子信息論。他發現了一種將量子態解釋爲信息的方法，將信息壓縮在一個狀態中，這現在被稱爲舒馬赫壓縮，是香農無噪聲編碼定理的量子模擬。

伍特斯和舒馬赫都曾經是著名物理學家惠勒在奧斯丁德州大學的學生，惠勒以善於用短語來概括深奧的物理概念而聞名，黑洞、蟲洞都是他的發明。伍特斯和舒馬赫也許繼承了這個傳統，有次他們開車前往機場，在討論量子信息的過程中，發現語言中缺少了點什麼，造成了似乎不能簡潔地描述量子信息問題。於是，他們有了一個想法：“可能有必要爲量子信息創建一個新的測量單位！”，接着，便冒出了“Qubit“這個詞彙。

一開始他們覺得這很搞笑，因爲Qubit的發音使他們想起了一種古老的長度單位“Cubit”（肘），是基於人體從肘部到中指尖的距離。古代有幾個民族，都使用過這個單位，例如，肘是聖經中的諾亞方舟的計量單位。

但之後他們認爲這是一個好主意，應該將這個術語引入學術界。因此，在1992年達拉斯舉行的一次量子計算會議上，舒馬赫在作演講時便強調了一個重點：計算機如何編碼信息？衆所周知，普通計算機以bit的形式存儲和處理信息，位（bit）是二進制數字的縮寫，即二進制算術中的 1 和 0。但如果要談論量子計算，使用比特並不是正確的方式。您需要一個描述“量子信息量”的單位，這就是 Qubit！因此，舒馬赫在達拉斯會議上的演講成爲了第一次使用和定義該術語Qubit的科學演講【3】。

4

量子比特vs比特

綜上所述，量子計算與經典計算的主要區別是運算單元：經典計算機的基本運算單位是比特，而量子計算機的基本單元是量子比特。量子比特也叫量子位或量子元，實質上也就是等同於量子物理中的疊加態，或者是圖3的量子圖靈機中畫的“自旋1/2”的粒子，或者也就是通常比喻的“薛定諤的貓”，又死又活！表達的都是同一個意思：Qubit。

理解疊加態，理解量子比特，是理解量子計算技術的關鍵。

雖然量子比特與比特，只區區相差“Qu”兩個字母，但其物理內容卻完全不同，具體實現更是天壤之別。比特的（0、1）兩個數值，用電壓的“高和低”很容易實現，而要實現量子比特，儘管有多種方法，但都非常困難。

比特只有兩個可能的狀態，即0和1。一個寄存器在任何時刻，只能處於兩個狀態之一：或是0，或是1。而量子比特是一種疊加態，它有兩個本徵態，即|0>和|1>，也可以將它們形式地對應於經典的0和1。但是，一個量子寄存器在任何時刻的狀態|y>，不是“之一”，而是兩種本徵態的疊加：

此外，可以忽略沒有物理意義的整體相位，這樣一來，4個實參數便只剩下兩個。被兩個參數描述的所有疊加態，在4維實數空間中構成一個超曲面。更進一步，該超曲面對應於3維歐氏空間的一個球面，這就是我們常見到的表示量子比特的布洛赫球面，見圖5右。

圖5：比特和量子比特

圖5中，兩個孤立點（0，1）描述的比特，及描述量子比特的布洛赫球，十分形象地顯示了比特和量子比特的異同。不同的是：比特只有兩個狀態，而量子比特可能的狀態有無窮多，因爲布洛赫球面【4】上有無窮多個點，每個點都是一個疊加態。但比特和量子比特也有相同之處，那就是：任何時刻所處的狀態只是一個：比特或是0或是1；量子比特任何時刻的狀態對應於球面上一個固定點，但這個點不只是|0> 或|1>，一般來說是它們的疊加，即既是|0> 又是|1>。

布洛赫球面以瑞士裔美國物理學家費利克斯·布洛赫（Felix Bloch，1905年- 1983）命名，布洛赫是一位諾貝爾物理學獎獲得者，他對理解晶格中的鐵磁性和電子行爲做出了基礎理論貢獻，榮獲1952年諾貝爾物理學獎。他也被認爲是核磁共振的開發者之一。布洛赫球面，是他一個小作品。

圖6：布洛赫球面的來龍去脈

我們在圖6中簡要總結了一下用布洛赫球面來表示量子比特的邏輯思路。如圖6所示，量子比特（疊加態）|y>可以表示爲球面上的一個點，因此，之前的公式（1）可以寫成：

公式（3）是用球座標中的極角q和方位角j兩個參數，來表示布洛赫球面，也就是量子比特。此外，量子比特作爲一種疊加態，有兩個關鍵點必須強調。

1. 量子世界的本質是隨機的，這個意思可以從本徵態疊加態之關係理解。本徵態和疊加態是相對的，依賴於物理量，也取決於（量子比特）基底的選擇。例如對薛定諤的貓，一般我們說 “死貓”與“活貓”是基底，又死又活、半死不活是疊加態。然而這不是絕對的，也可以將又死又活 半死不活當作基底態，而“死貓” “活貓”便成爲了疊加態，見圖7。因此，原以爲是固定態的基態，實質也是疊加態，所以本質上都是疊加態。

圖7：疊加態和本徵態是相對的

2. 疊加態疊加什麼？疊加的是概率幅不是概率。概率幅和概率是不一樣的，它們的區別很重要。如果兩個本徵態互不正交，概率幅疊加會產生干涉項，見圖8。概率幅疊加後，模的平方中，除了兩個基態係數模之外，還有兩個基態的相干項，包含了兩個波函數相對相位的信息，即兩個波函數是相干的。

而經典的概率疊加，僅是概率混合的統計現象。量子物理中概率幅的疊加，反映了波動的本質。量子疊加能產生干涉，多種狀態同時存在，使得量子計算機能同時對多種狀態進行計算，即可以對特定算法進行平行計算，這是量子計算快於經典計算的奧秘所在！

圖8：概率幅疊加產生干涉項

機器的“計算”是什麼意思呢？經典計算中有許多邏輯門：例如AND（與門），OR（或門），以及NOT（非門）、與非門、或非門等等。這些邏輯門的各種組合，將各個“比特”的0、1狀態變來變去，便能夠完成各種複雜的計算。量子比特也需要類似的概念：“量子門”！這將在下一篇介紹。

參考文獻

【1】通用圖靈機-維基百科：https://zh.wikipedia.org/wiki/%E9%80%9A%E7%94%A8%E5%9C%96%E9%9D%88%E6%A9%9F

【2】"The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines", Paul Benioff, Journal of Statistical Physics, 22, 563, 1980.

【3】Quantum coding，Benjamin Schumacher，Phys. Rev. A 51, 2738 – Published 1 April 1995.

【4】布洛赫球面-維基百科：https://zh.wikipedia.org/wiki/%E5%B8%83%E6%B4%9B%E8%B5%AB%E7%90%83%E9%9D%A2

由於微信公衆號亂序推送，您可能不再能準時收到墨子沙龍的推送。爲了不與小墨失散， 請將“墨子沙龍”設爲星標賬號，以及常點文末右下角的“在看”。

轉載微信原創文章，請在文章後留言；“轉載說明”在後臺回覆“轉載”可查看。爲了提供更好的服務，“墨子沙龍”有工作人員就各種事宜進行專門答覆：各新媒體平臺的相關事宜，請聯繫微信號“mozi-meiti”；線下活動、線上直播相關事宜，請聯繫微信號“mozi-huodong”。

墨子是我國古代著名的思想家、科學家，其思想和成就是我國早期科學萌芽的體現。墨子沙龍的建立，旨在傳承、發揚科學傳統，倡導、弘揚科學精神，提升公民科學素養，建設崇尚科學的社會氛圍。

墨子沙龍面向熱愛科學、有探索精神和好奇心的普通公衆，通過面對面的公衆活動和多樣化的新媒體平臺，希望讓大家瞭解到當下全球最尖端的科學進展、最先進的科學思想，探尋科學之秘，感受科學之美。

墨子沙龍由中國科學技術大學上海研究院及浦東新區南七量子科技交流中心主辦，受到中國科大新創校友基金會、中國科學技術大學教育基金會、浦東新區科學技術協會、中國科學技術協會及浦東新區科技和經濟委員會等支持。

關於“墨子沙龍