1.1　量子計算機是什么

量子計算機是一種不同于以往任何計算機的新型計算機。本書將從量子計算機的特點和定位講起。

1.1.1　何為計算

大家可以回憶一下在小學一年級學習算術時的情景。我們先學習了0到9這 10個數字，然后學習了加減乘除四則運算。在日常生活中，我們可以利用這些知識來清點物品的數量、規劃時間或者算賬。

后來我們又學會了更加復雜的計算方法，知道了計算還可以運用到產品制造、建筑設計和地球環境測量等工作中。不過，上了高中后我們開始意識到，人類的計算能力并沒有那么強：對于大數運算，用筆計算 5 位數的乘法已經比較吃力了；圖形計算的話，頂多算算圓形或三角形等簡單圖形的周長和面積；至于位數更多的數或更加復雜的圖形，恐怕腦袋里就會一團糟，更是無從下手了。

好在我們可以使用計算器。計算器的種類繁多，這里姑且將所有用于計算的機器統稱為計算器。我們最熟悉的計算器當屬電子計算器。在電子計算器發明之前，人們使用算盤進行計算。計算器出現后，多位數的運算速度實現了大幅提升。

更復雜的計算還可以使用計算機來完成。學習帶有和等未知數的方程式后，我們可以在不使用具體數字的情況下列出計算公式，然后根據這些公式來編寫程序。這樣一來，很難通過筆算完成的復雜計算就可以交由計算機來處理了。無論是計算幾千位的大數，還是計算復雜的三維圖形，只要知道基本的方程式，就能借助計算機求出答案。

計算機是利用電能執行計算的機器，于 1960年前后開始實際投入使用。它擁有超越人類的計算能力，如今已融入我們的日常生活中。圖1.1 展示了計算器的發展歷程。

圖1.1　計算器的發展歷程

1.1.2　計算機的極限

即使是利用電能的計算機，能力也是有限的。在過去的 60年間，計算機不斷發展，不但實現了高速計算，使用方法也變得越來越簡單。然而，人類想要解決的問題也在以同樣的速度變得更復雜、更煩瑣。對于復雜的三維物體或具有量子力學行為的物質，就算使用當今最先進的計算機也無法輕松執行仿真計算。不可否認，有時候在計算方面，計算機仍力有未逮。近期備受關注的區塊鏈技術正是基于這一事實產生的系統。另一門受到廣泛關注的機器學習技術，同樣致力于減少求解問題所花費的時間。

因此，突破當今計算機的極限就變得至關重要，人們認為世界將因此變得更加美好（圖1.2）。那么，如何才能突破計算機的極限呢？量子計算機無疑是答案之一。

圖1.2　借助量子計算機突破極限

1.1.3　量子計算機是什么

目前，研究人員正在積極研發作為下一代高速計算機的量子計算機。對于現代計算機所面臨的重重難題，哪怕量子計算機只能解決其中的一小部分，也會給社會帶來巨大沖擊。

首先，筆者來簡單介紹一下什么是量子計算機。本書將量子計算機定義為一種通過積極利用量子力學特有的物理狀態來實現高速計算的計算機。量子計算機中的“量子”（quantum）正是量子力學中的“量子”。量子力學是在大學階段開設的一門課程。作為物理學的分支之一，它是為了解釋原子和電子等極小物質的運動而發展起來的理論。量子力學告訴我們，在原子、電子和光子（光的粒子）等極小的物質，以及超導物質等冷卻至極低溫度的物質上會發生不同尋常的神秘現象，而這些現象是可以通過實驗證實的。例如，研究人員已經實現了疊加態和量子糾纏態等量子力學所特有的物理狀態（相關內容會在后面的章節講解）。那么，為什么不積極利用這些特有的物理狀態來制造計算機呢？正是基于這一想法，量子計算機誕生了。量子計算機能夠執行遠超傳統計算機計算能力的量子計算。隨著研究的深入，與傳統計算之間存在本質差別的量子計算的潛力漸漸顯露出來。量子計算機的研發，即研發出一種能夠通過精確控制量子來突破傳統計算機極限的量子計算機，成了物理學和工程學上的一大挑戰（圖1.3）。

圖1.3　什么是量子計算機

1.1.4　量子計算機與經典計算機

下面，我們總結一下量子計算機和普通計算機之間的區別。首先，計算可以大致分為兩類：一類是基于同為物理學分支之一的經典物理學的經典計算，另一類就是基于量子力學（這里也可以說是量子物理學，本書后文將統一使用“量子力學”一詞）的量子計算。

我們在初中和高中的物理課上學過物體的運動、力的作用和電磁場的特性等知識，這些都屬于經典物理學的研究范疇。量子力學的研究內容則包括原子和電子的性質等，這些要在大學的某些專業課上才會學到。我們可以認為，經典計算和量子計算分別對應于這兩種物理學。筆者會從第 3 章開始介紹二者的區別。本書中，我們把執行量子計算的設備稱為量子計算機，把執行經典計算的設備，也就是那些常見的普通計算機稱為經典計算機。

量子計算向下兼容經典計算，這就意味著任何可以用經典計算機求解的問題都可以用量子計算機求解。對應到物理學上，這就等同于任何可以由經典力學處理的現象（原則上）都可以由量子力學處理（即經典物理學是量子力學的近似）。

此外，人們已經發現，有時借助量子計算機可以快速求解經典計算機難以求解的問題。這一現象對應到物理學上就是量子力學甚至可以處理經典物理學無法處理的現象（圖1.4）。

圖1.4　物理學與計算之間的對應關系

量子計算機目前還沒有公認的定義。本書對量子計算機的定義如上一頁的圖1.3所示。需要注意的是，雖然普通計算機的運轉同樣離不開利用了量子力學現象的半導體設備（如晶體管和閃存等），但在其上執行的計算其實還是對應于經典物理學的經典計算。我們需要明確“用于實現的物理現象”與“能夠實際執行的計算”之間的區別，僅僅使用了可由量子力學解釋的現象并不意味著可以執行量子計算。但是，要想執行量子計算，則需要精確控制可由量子力學解釋的現象，并實現所謂的“量子力學特有的物理狀態”這一特殊狀態。

1.1.5　量子計算機的類型

本書將量子計算機分為以下三種類型（圖1.5）。

• 通用量子計算機

  通用量子計算機可以執行任意的量子計算。解釋得更詳細一點，就是通用量子計算機能夠以足夠高的精度將一種任意的量子態轉換為另一種任意的量子態。所謂任意的量子態，是指任意多個量子比特（也稱為量子位）的狀態。若一種量子計算機能以足夠高的精度——之所以這么說，是因為 100% 轉化很困難——將任意的量子態轉換為期望的狀態，我們就可以把這種量子計算機稱為通用量子計算機。另外，量子比特的數量增加后，所要執行的轉換也會變得越來越復雜，噪聲的影響也會變大，因此量子計算機必須能夠糾正計算過程中出現的錯誤（具備容錯能力）。能夠容錯的量子計算機稱為“具備容錯能力的量子計算機”。

   

• 非通用量子計算機

  非通用量子計算機無法執行任意的量子計算，即只能執行部分量子計算，但它也表現出了優于經典計算機的一面。

  名為 NISQ（Noisy Intermediate-Scale Quantum，嘈雜中型量子）的量子計算機就屬于此類。這類量子計算機目前正處于研發階段，尚不具備容錯能力（或容錯能力較弱）。具體內容會在 1.2.6節介紹。

   

• 非經典計算機

  非經典計算機使用（或旨在使用）量子力學特有的物理狀態執行計算，但尚未表現出優于經典計算機的一面。目前正在研發的量子退火計算機就屬于此類。

  

  圖1.5　量子計算機的類型

  表1.1 總結了上述三種量子計算機的特點。本書將這三種計算機統稱為廣義量子計算機，并就此展開詳細講解。

  從表中可以看出，廣義量子計算機與經典計算機的不同之處，在于計算時是否使用了量子力學特有的物理狀態；而對于同屬廣義量子計算機的非通用量子計算機和非經典計算機，二者之間的區別體現在計算性能方面，即是否存在超越經典計算的量子優勢；最后，非通用量子計算機與通用量子計算機之間的區別，在于量子計算是否具有通用性。

  表1.1　量子計算機的類型和特點

  

1.1.6　量子計算模型的類型

上一小節從硬件角度介紹了量子計算機的分類。此外，計算也有類型之分——本書將量子計算模型分為通用型和專用型兩類。這里所說的計算模型是指描述計算執行方式的模型。

• 通用型

  通用型模型可以描述所有量子計算。量子電路模型就是一種典型的通用型模型。除此以外，還有多種在計算量上等效的模型尚處于研究階段，比如基于測量的量子計算、絕熱量子計算和拓撲量子計算等（請參考 6.5節專欄）。筆者會在后面的章節中就量子電路模型展開詳細講解。

  • 量子電路模型

    該模型在執行計算時使用的是量子電路和量子門，二者取代了經典計算機中使用的電路和邏輯門（logic gate）。1

    該模型自量子計算機研究之初沿用至今，是能夠描述通用量子計算的最標準的模型（圖1.6）。

    

    圖1.6　量子電路模型

     

• 專用型

  專用型模型可以描述特定的計算。本書將會講解一種名為量子退火的計算模型，它是專門用于計算伊辛模型基態（第 7 章）的計算模型，解決問題的方式是將問題映射到伊辛模型（圖1.7）。

  

  圖1.7　伊辛模型

  • 量子退火

    2011年，一家名為 D-Wave Systems 的加拿大風險投資公司將量子退火商業化。Google 和 NASA（National Aeronautics and Space Administration，美國國家航空航天局）也參與了相關研究，使得量子退火聲名鵲起。東京工業大學的西森秀稔教授團隊和麻省理工學院的愛德華·法爾希（Edward Farhi）團隊先后提出了量子退火（門脅和西森，1998）和量子絕熱計算（法爾希等，2001），這兩種理論上的計算模型形成了量子退火的基礎。基于這兩種計算模型，人們就可以使用專為量子退火設計的機器——量子退火計算機來執行計算。

1因此該模型也常被稱為量子門方式。