帶你讀《量子程式設計基礎》之二：預備知識

點選檢視第一章 點選檢視第三章

第二章 預備知識

本章将對全書使用的量子力學和量子計算的基本概念與符号進行介紹。

• 當然，量子程式設計理論是基于量子力學建構的。是以，2.1節介紹了量子力學的希爾伯特空間表示，這是本書的數學基礎。
• 2.2節介紹了量子線路。縱觀曆史，幾個主要的量子算法被設計出來的時候還沒有任 何量子程式設計語言存在。是以通常使用量子線路作為計算模型來對這些量子算法進行描述。
• 2.3節介紹了一些基本的量子算法。這一節主要是為了給量子程式設計提供例子，而非系統地闡述量子算法。是以本節并不會介紹太多複雜的量子算法。

為了使讀者能夠盡快進入本書的核心内容——量子程式設計，我會盡力縮短本章的篇幅。是以，本章列舉的材料都非常簡潔。初學者可以從本章開始學習，但同時建議閱讀［174］一書的第2、4、5、6和8章，這樣可以更好地了解本章所介紹的概念。另一方面，如果讀者已經從标準教科書（例如［174］）學習過這些材料，那麼建議直接跳過本章，僅将本章用于符号檢索。

2.1量子力學

量子力學是一門基礎性的實體學科，主要研究原子以及亞原子尺度上的實體現象。量子 力學的一般形式是基于四個基本假設來進行闡述的。我們将更多地通過數學的方式來對這些基本假設進行介紹，而并不會在實體學上對它們進行過多解釋。希望這樣做可以為讀者掌 握量子程式設計提供捷徑。

2.1.1希爾伯特空間

我們通常将希爾伯特空間作為量子系統的狀态空間。它是基于向量空間的概念進行定義的。我們将 C 記為複數的集合。對于任意一個複數 λ = a + b> ∈ C，它的共轭複數為λ∗ = a − b>。在量子力學中，我們采用狄拉克符号代表向量，如 |ϕ> 和 |ψ> 等。

定義 2.1.1 （複）向量空間是一個非空的集合 H ，且具有如下兩種操作:

• 向量加法+：H + H → H 。
• 标量乘法·：C · H → H 。

它還滿足如下條件：

(1) + 滿足交換律：對于任意的 |ϕ>, |ψ> ∈ H , |ψ> + |ϕ> = |ϕ> + |ψ>。

(2) + 滿足結合律：對于任意的 |ϕ>, |ψ>, |χ> ∈ H , |ϕ> + (|ψ> + |χ>) = (|ϕ> + |ψ>) + |χ>。

(3) + 具有零元素 0，稱為零向量，它滿足：對于任意的 |ϕ> ∈ H , 0 + |ϕ> = |ϕ>。

(4) 任意的 |ϕ> ∈ H 都有逆向量 −|ϕ>，滿足：|ϕ> + (−|ψ>) = 0。

(5) 對于任意的 |ϕ> ∈ H ，有 1|ϕ> = |ϕ>。

(6) 對于任意的 |ϕ> ∈ H , λ, µ ∈ C, λ(µ|ϕ>) = λµ|ϕ>。

(7) 對于任意的 |ϕ> ∈ H , λ, µ ∈ C,(λ + µ)|ϕ> = λ|ϕ> + µ|ϕ>。

(8) 對于任意的 |ϕ>, |ψ> ∈ H , λ ∈ C, λ(|ϕ> + |ψ>) = λ|ϕ> + λ|ψ>。

還需要如下知識來幫助我們更好地了解希爾伯特空間的概念：

定義 2.1.2 内積空間是指具有内積的向量空間 H ；即存在一種映射關系

<·|·> : H × H → C

滿足如下條件: 對于任意的 |ϕ>, |ψ>, |ψ1>, |ψ2> ∈ H ，λ1, λ2 ∈ C，都有

(1) <ϕ|ϕ> > 0，等号成立當且僅當 |ϕ> = 0。

(2) <ϕ|ψ> = <ψ|ϕ>∗。

(3) <ϕ|λ1ψ1 + λ2ψ2> = λ1<ϕ|ψ1> + λ2<ϕ|ψ2>。

對于任意的向量 |ϕ>, |ψ> ∈ H ，我們稱複數 <ϕ|ψ> 為 |ϕ> 和 |ψ> 的内積。有時候也将

<ϕ|ψ> 記為 (|ϕ>, |ψ>)。如果 <ϕ|ψ> = 0，那麼稱 |ϕ> 和 |ψ> 是正交的，并記為 |ϕ> ⊥ |ψ>。向量

|ψ> 的長度為：

如果 ||ψ|| = 1，那麼稱它為機關向量。

極限的概念可以從向量長度的角度來定義。

定義 2.1.3 令 {|ψn>} 是一列屬于 H 的向量且 |ψ> ∈ H 。

(1) 如果對于任意的 ε > 0，都存在一個正整數 N 使得對于所有的 m, n > N 都滿足||ψm − ψn|| < ε，那麼稱 {|ψn>} 為柯西序列。

(2) 如果對于任意的 ε > 0，都存在一個正整數 N 使得對于所有的 n > N 都滿足||ψn − ψ|| < ε，那麼稱 |ψ> 為 {|ψn>} 的極限，并記為 |ψ> = l>mn→∞ |ψn>。

現在我們給出希爾伯特空間的定義。

定義2.1.4 希爾伯特空間是一個完備的内積空間，即在這個内積空間内任何一個柯西序列的向量序列都有極限。

希爾伯特空間的基可以幫助我們更好地了解希爾伯特空間的結構。本書中，我們僅考慮有限維的或者可數無限。維(獨立)的希爾伯特空間。

定義2.1.5 一個有限或者可數無限的機關向量簇{|ψi>}如果滿足如下條件，就可以稱為H的一組标準正交基：

(1) {|ψi>} 是兩兩正交的：對于任意的 >, j 且 > = j, 都有 |ψi> ⊥ |ψj >。

(2) {|ψi>} 可以擴充成整個 H 空間：任意的 |ψ> ∈ H ，都可以通過線性組合 |ψ> = P> λ>|ψi> 進行表示，其中 λ> ∈ C 且 |ψi> 的數量是有限的。

任意兩組标準正交基中向量的數量是相同的。我們将它稱作空間 H 的次元，并記為d>mH 。特别地，如果一組标準正交基中包含無數個向量，那麼稱 H 的次元是無限的，并記為 d>mH = ∞。

在量子程式設計中，隻有當資料類型是無限(比如整數)的時候才會用到無限次元的希爾伯特空間。如果讀者覺得無限次元的希爾伯特空間以及相關概念(比如定義2.1.3中的極限，定義2.1.6中的閉子空間)很難了解的話，那麼隻需要了解有限維希爾伯特空間并掌握 一些初等線性代數的知識，就能夠了解本書的重點。

當 H 的次元有限時，例如 d>mH = n，假設有一組固定的标準正交基 {|ψ1>, |ψ2>, · · · , |ψn>}，那麼所有屬于 H 的向量 |ψ> = Pn>=1 λ>|ψi> 都可以通過 Cn 中的向量來表示：

子空間的概念對于了解希爾伯特空間也非常重要。

定義2.1.6 令H是一個希爾伯特空間。

(1) 如果 X ⊆ H ，并且對于任意的 |ϕ>, |ψ> ∈ X, λ ∈ C，都滿足:

(a) |ϕ> + |ψ> ∈ X

(b) λ|ϕ> ∈ X

那麼就稱 X 為 H 的子空間。

(2) 對于每一個 X ⊆ H ，它的閉包 X 是 X 中序列 {|ψn>} 的極限 l>mn→∞ |ψn> 的

集合。

(3) 如果 X = X，則 X 是 H 的閉子空間。

對于任意的子集 X ⊆ H ，由 X 擴充的空間:

是包含 X 的 H 的最小子空間。換言之，spanX 是 X 生成的 H 的子空間。此外，

是由 X 産生的閉子空間。

我們在前面已經對兩個向量的正交進行了定義。對其進行擴充，可以得到對兩個向量集合之間正交關系的定義。

定義2.1.7 令H是希爾伯特空間。

(1) 對于任意的 X, Y ⊆ H ，如果對所有的 |ϕ> ∈ X, |ψ> ∈ Y 均有 |ϕ> ⊥ |ψ>，那麼稱X 與 Y 是正交的，并記為 X ⊥ Y 。特别地，如果 X 隻有一個元素 {|ϕ>}，那麼簡單地記作|ϕ> ⊥ Y 。

(2) 令 X 是 H 的閉子空間，那麼它的正交補為：

正交補 X⊥ 也是 H 的閉子空間，且對于 H 的任一閉子空間都有 (X⊥)⊥ = X。

定義 2.1.8 令 H 是一個希爾伯特空間，X 和 Y 是它的兩個子空間，那麼

稱為 X 與 Y 的和。

可以将上述定義直接擴充到多個 H 的子空間 X> 的和

。特别地，如果 X>(1 6 > 6 n) 與其他子空間互相正交，那麼可以将

。特别地，如果 X>(1 6 > 6 n) 稱為正交和。

通過上述準備工作，我們可以對量子力學第一基本假設進行介紹:

• 量子力學第一基本假設: 可以用希爾伯特空間來表示一個封閉（即孤立）的量子系統的狀态空間，且這個系統中的純态 可以通過狀态空間中的機關向量來描述。

通常将态 |ψ1>, · · · , |ψn> 的線性組合 |ψ> = Pn>=1 λ>|ψi> 稱為這些态的疊加态，複系數 λ>

稱為機率幅。

例子 2.1.1 将比特的概念進行量子化擴充，可以得到量子比特的概念。量子比特的狀

态空間是一個二維的希爾伯特空間：

H2 的内積可以這樣定義:

對于所有的 α, α‘, β, β’ ∈ C 都成立。{|0>, |1>} 是 H2 的一組标準正交基，通常稱為可計算基

矢。可以将向量 |0>, |1> 表示為：

量子比特的狀态可以通過機關向量 |ψ> = α|0> + β|1> 來描述，其中 |α|^2 + |β|^2 = 1。下面兩個

向量：

是另一組标準正交基。它們都是 |0> 和 |1> 的疊加态。二維希爾伯特空間 H2 也可以被視作經典的布爾資料類型的量子化對應物。

例子 2.1.2 本書中另一類常用的希爾伯特空間是平方可求和序列空間：

其中 Z 是整數集合。H∞ 的内積被定義為：

對于所有的 αn, α'n ∈ C(−∞ < n < ∞) 都成立。{|n> : n ∈ Z} 是一組标準正交基，且 H∞ 是

一個無限維空間。可以将這個希爾伯特空間了解為經典的整數型變量的量子化對應物。

練習 2.1.1 驗證上述兩個例子中的内積滿足定義 2.1.2 中的三條性質。

2.1.2 線性算子

在上一節中我們研究了量子系統的靜态描述，并将其狀态空間命名為希爾伯特空間。現在我們繼續研究如何對動态的量子系統進行描述。量子系統的演化及其上的所有操作都可以通過希爾伯特空間上的線性算子來描述。是以本節将對線性算子及其矩陣表示進行研究。

定義 2.1.9 令 H 和 K 是希爾伯特空間，映射:

如果對于任意的 |ϕ>, |ψ> ∈ H 和 λ ∈ C 都滿足如下條件：

(1) A(|ϕ> + |ψ>) = A|ϕ> + A|ψ>

(2) A(λ|ψ>) = Aλ|ψ>

就稱它為線性算子。

如果一個算子是 H 到它自身的映射，那麼稱該算子為 H 中的算子。如果 H 中的一個算子把每個向量都映射成這個向量本身，那麼就将這個算子稱為 H 中的機關算子，并記作 IH ；如果 H 中的一個算子把每個向量都映射成 H 中的零向量，那麼就将這個算子稱為 H 中的零算子，并記作 0H 。對于任意的向量 |ϕ>, |ψ> ∈ H ，可以将它們的外積定義為算子 |ϕ><ψ|：

對于所有的 |χ> ∈ H 都成立。投影算子是一類簡單且實用的算子。令 X 是 H 的一個閉子空間且 |ψ> ∈ H ，那麼存在唯一的 |ψ0> ∈ X 和 |ψ1> ∈ X^⊥ 滿足：

将向量 |ψ0> 稱為 |ψ> 在 X 上的投影，并記作 |ψ0> = PX|ψ>。

定義 2.1.10 對于 H 的任意閉子空間 X, 可以将算子

稱為在 X 上進行的投影變換。

練習 2.1.2 證明：如果 {|ψi>} 是 X 的一組标準正交基，那麼 PX = P> |ψi><ψ>|。

本書隻考慮有界算子。有界算子的定義為：

定義 2.1.11 對于 H 上的算子 A，如果存在常數 C > 0 滿足：

對于所有的 |ψ> ∈ H 都成立，那麼稱該算子是有界的。可以将算子 A 的範數定義為一個非

負數 ：

将 H 中有界算子的集合記為 L (H )。

有限維希爾伯特空間内的所有算子都是有界的。

在通過将現有算子進行組合來産生新算子時，算子的運算法則很有用。我們可以自然而然地将算子的加法、标量乘法群組合定義為：對于任意的 A, B ∈ L (H ), λ ∈ C, |ψ> ∈ H ，都有

練習 2.1.3 證明滿足加法和标量乘法的集合 L (H ) 是一個向量空間。

我們也可以對算子的正定性以及多個算子之間的序和距離進行定義。

定義 2.1.12 對于一個算子 A ∈ L (H )，如果滿足對于所有的态 |ψ> ∈ H ，<ψ|A|ψ> 都

是一個非負實數，即 <ψ|A|ψ> > 0，那麼就稱這個算子是正定的。

定義 2.1.13 将 L¨owner 序

定義為：對于任意的 A, B ∈ L (H ), A

B 當且僅當

B − A = B + (−1)A 是正定的。

定義 2.1.14 令 A, B ∈ L (H )，則它們之間的距離為 :

其中 |ψ> 代表了 H 中所有的純态（即機關向量）。

算子的矩陣表示

有限維希爾伯特空間中的算子可以通過矩陣的形式表示，這在應用中非常友善。讀者在

讀完這部分内容後，通過類比之前學過的初等線性代數知識，可以更好地了解前面定義的那

些抽象概念。

如果 {|ψi>} 是 H 的一組标準正交基，那麼算子 A 就由 A 作用在這組基向量 |ψi> 上的

像 A|ψi> 唯一确定。特别地，當 H 的次元 n 是有限的情況時，假設有一組固定的标準正交

基 {|ψ1>, · · · , |ψn>}，那麼可以将 A 通過一個 n × n 的複矩陣來表示：

其中:

對于所有的 >, j = 1, · · · , n 都成立。此外，算子 A 作用在向量

上的

像可以通過矩陣 A = (a>j )n×n 與向量 |ψ> 之積來表示:

其中

對于所有的 > = 1, · · · , n 都成立。舉例來說，IH 是一個機關矩陣，0H

是一個零矩陣，如果有:

它們的外積是矩陣

，其中對于所有的 >, j = 1, · · · , n 都有

。本書對有限維希爾伯特空間的算子及其矩陣表示不做區分。

練習 2.1.4 證明在有限維希爾伯特空間中，算子的加法、标量乘法群組合分别與該算子矩陣表示的加法、标量乘法和矩陣乘法是等價的。

2.1.3 幺正變換

2.1.1 節介紹了量子力學第一基本假設，該假設對量子系統進行了靜态描述。本節中，我們将用上一節給出的數學工具對量子系統的演化進行描述。

量子系統的連續時間演化是通過所謂的薛定谔偏微分方程描述的。但在量子計算中，我們通常隻對系統的離散時間演化進行研究，即幺正變換。對于任意的算子 A ∈ L (H )，在空間 H 中都存在唯一的線性算子 A†，滿足：

對于所有的 |ϕ>, |ψ> ∈ H 都成立。我們将算子 A† 稱為 A 的伴随算子。特别地，如果 n 維希

爾伯特空間中的一個算子是通過矩陣

來表示的，那麼它的伴随算子可以通過

A 的轉置共轭矩陣來表示:

其中對于任意的 >, j = 1, · · · , n，都有

。

定義 2.1.15 U ∈ L (H ) 是一個有界算子。如果 U 的伴随算子與它的逆相同，即

那麼稱 U 為幺正變換。

所有的幺正變換都是保内積的，即

對于所有的 |ϕ>, |ψ> ∈ H 都成立。當 H 的空間次元有限時，U†U = IH 與 UU† = IH 是等價的。如果 d>mH = n，那麼 H 中的幺正變換可以通過一個 n × n 的幺正矩陣 U 來表示，即矩陣 U 滿足 U†U = In，其中 In 是一個 n 維機關矩陣。

下面這條引理給出一種定義幺正算子的有用的技術：

引理 2.1.1 假設 H 是一個有限維希爾伯特空間且 K 是它的一個閉子空間。如果線性算子 U : K → H 是保内積的，即

對于任意的 |ϕ>, |ψ> ∈ K 都成立，那麼空間 H 中存在一個幺正算子 V，它是對算子 U 在 H 下的擴充，即 V |ψ> = U|ψ> 對于任意的 |ψ> ∈ K 都成立。

練習 2.1.5 證明引理 2.1.1。

現在我們準備介紹量子力學第二基本假設：

• 量子力學第二基本假設：假設一個封閉的量子系統（即該系統和外部環境沒有互動）在時間 t0 和 t 的狀态分别為 |ψ0> 和 |ψ>，那麼它們之間通過幺正算子 U 互相關聯，且該算子隻取決于時間 t0 和 t，

  

下面兩個簡單的例子可以幫助讀者更好地了解這個基本假設。

例子 2.1.3 Hadamard 變換是二維希爾伯特空間 H2 中一種常見的作用于量子比特的幺正算子：

它可以将處在可計算基矢 |0> 和 |1> 的量子比特轉換為疊加态:

例子 2.1.4 令 k 是一個整數，那麼可以在無限維希爾伯特空間 H∞ 上定義 k-平移算子 Tk：

對于所有的 n ∈ Z 都成立。很容易驗證 Tk 是一個幺正算子。特别地，我們記

且 TR = T1，它們可以将一個粒子從目前所處位置分别向左或者右移動一個位置。

讀者可以在 2.2 節看到更多關于幺正變換的例子，在那裡幺正變換用于制備量子線路中的量子邏輯門。

2.1.4 量子測量

通過前面兩個小節，我們已經掌握了如何對量子系統進行靜态和動态的描述。對量子系統的觀測是通過量子測量來完成的。量子測量的定義為：

• 量子力學第三基本假設：對狀态空間為 H 的量子系統進行的測量可以通過一系列算子 {Mm} ⊆ L (H ) 來刻畫，且這些算子滿足歸一化條件：

  

其中 Mm 稱為測量算子，索引 m 代表測量時可能得到的結果。如果在測量之前的一瞬間，這個量子系統的狀态是 |ψ>，那麼對于任意的 m，測量得到 m 的機率為:

該系統在獲得測量結果 m 之後的狀态為：

很容易發現，歸一化條件 (2.3) 意味着所有測量結果的機率之和

接下來這個例子可以幫助讀者更好地了解上述假設。

例子 2.1.5 在可計算基矢上對一個量子比特進行測量會得到兩種測量結果，可以将這類測量定義為測量算子：

如果這個量子比特在測量之前處于 |ψ> = α|0> + β|1>, 那麼獲得測試結果為 0 的機率為:

并且在此情況下，測量之後的狀态為:

與之類似，測量結果為 1 的機率為 p(1) = |β|^2，并且在此情況下，測量之後的狀态為 |1>。

投影測量

可以根據厄米算子及其譜分解來定義一類非常有用的測量。

定義 2.1.16 如果一個算子 M ∈ L (H ) 滿足:

M† = M

那麼稱它是厄米共轭的。實體學上也将厄米算子稱為可觀測量。

從上述定義可以看出一個算子 P 成為投影算子要滿足這樣的條件：對于 H 的某一閉子空間 X 有 P = PX 成立，當且僅當 P 是厄米共轭的且 P^2 = P。

可以用基于厄米算子的譜分解這一數學概念的可觀測量來構造量子測量。由于本書篇幅有限，我們僅考慮有限維希爾伯特空間 H 下的譜分解 （無限維的情況需要更複雜的數學原理；參考 [182] 一書的 3.5 節。本書隻在 3.6 節将其作為數學工具來證明一個技巧性的引理）。

定義 2.1.17

(1) 算子 A ∈ L (H ) 的特征向量是一個非零向量 |ψ> ∈ H , 且滿足存在 λ ∈ C 使得A|ψ> = λ|ψ> 成立，其中 λ 是特征向量 |ψ> 所對應的特征值。

(2) A 的特征值的集合稱為 A 的 (點) 譜，記為 spec(A)。

(3) 對于任意的特征值 λ ∈ spec(A)，集合

是 H 的一個閉子空間，将該空間稱為特征值 λ 對應的特征空間。

不同的特征值 λ1 ≠ λ2 所對應的特征空間是正交的。可觀測量（即厄米算子）M 的特征值都是實數。此外還可以将 M 的譜分解表示為：

其中 Pλ 是在 λ 對應的特征空間上的投影算子。因為 {Pλ : λ ∈ spec(M)} 中所有測量算子Pλ 都是投影算子，是以可以将它稱為投影測量。通過前面介紹的量子力學第三基本假設可以得到：對一個處于狀态 |ψ> 的系統進行測量，得到 λ 的機率為:

并且在這種情況下，測量之後系統的狀态為:

因為所有可能的測量結果 λ ∈ spec(M) 都是實數，是以可以對 M 在狀态 |ψ> 下的期望（平均值）進行計算：

可以看出，對于給定的狀态 |ψ>，機率 (2.4) 和測量之後的狀态 (2.5) 由投影 {Pλ} 唯一确定（而不是 M 本身）。是以可以很容易地得到，{Pλ} 是正交投影算子的一個完備集，即滿足如下條件的算子的集合：

簡單起見，有時将正交投影算子的完備集稱為投影測量。一種特例是：在希爾伯特空間的一組标準正交基 {|i>} 上進行測量，其中對于所有的 > 都有 P> = |i>

2.1.5 希爾伯特空間的張量積

目前，我們隻對單一量子系統進行了研究。本節将對由兩個或兩個以上子系統構成的複

合系統進行研究。對複合系統的描述是基于張量積的概念進行的。我們主要對有限維希爾伯

特空間的張量積進行研究。

定義 2.1.18 令 Hi 是希爾伯特空間，

是它的一組标準正交基，其中 i = 1, · · · , n。我們将具有如下形式元素的集合記為 B:

的張量積是一個以 B 作為标準正交基的希爾伯特空間：

從式 (2.1) 可以得出，可以将任意屬于

的元素寫為這樣的形式：

其中，

對于任意的 j1, · · · , jn 都成立。此外可

以通過線性性來證明，上述定義中每一個因子空間 Hi 與基

的選擇是無關的，舉例來說，如果

，那麼

由于 B 是一組标準正交基，是以

空間中的向量加法、标量乘法和内積就可以很自然地定義出來。

本書中我們有時需要考慮可數無限維希爾伯特空間的張量積。令 {Hi} 是可數無限希爾伯特空間簇，對于任意的 i，

都是 Hi 的一組标準正交基。記所有 Hi 中基向量的張量積的集合為：

那麼 B 是一個有限集合或可數無限集合，還可以将它用線性向量的形式進行表示：B =

。可以将 {Hi} 的張量積定義為以 B 作為标準正交基的希爾伯特空間：

現在我們可以對量子力學第四基本假設進行介紹:

• 量子力學第四基本假設：複合量子系統的狀态空間是其組成部分的狀态空間的張量積。

假設 S 是由 S1, · · · , Sn 構成的複合量子系統，這些子系統的狀态希爾伯特空間分别為H1, · · · , Hn。對于任意的 1 ≤ i ≤ n，Si 的态為 |ψi> ∈ Hi，那麼 S 的态為直積态 |ψ1, · · · , ψn>。此外，S 也可能是幾個直積态的疊加 (線性組合)。糾纏是量子力學中最有趣也最令人費解的實體現象，它出現于複合系統中：如果複合量子系統的狀态不能通過其子系統狀态的直積進行表示，那麼就稱它為糾纏。糾纏現象是經典世界和量子世界最大的不同之一。

例子 2.1.6 具有 n 個量子比特系統的狀态空間為:

特别地，兩個量子比特的量子系統的态既可以是直積态（比如 |00>, |1>|+>），也可以是糾纏态（比如貝爾态或者 EPR 糾纏對）：

因為希爾伯特空間的張量積也是希爾伯特空間，是以可以對張量積中的線性算子、幺正變換和測量進行讨論。希爾伯特空間的張量積中有一類特殊的算子：

定義 2.1.19 對于 i = 1, · · · , n，令 Ai ∈ L (Hi)，那麼這些算子的張量積是算子

，該算子可以通過

及其線性組合來進行定義，其中對于任意的 i = 1, · · · , n 都有 |ϕi> ∈ Hi。

然而其他非張量積的算子在量子計算中也同樣重要，因為它們可以産生量子糾纏。

例子 2.1.7 雙量子比特系統的希爾伯特空間

中的受控非門（即 CNOT）算子 C 是這樣定義的:

或者可以通過如下 4 × 4 的矩陣進行等價描述：

它可以将直積态轉化為糾纏态：

通過投影測量實作一般性測量

2.1.4 節介紹的投影測量是一類特殊的量子測量。通過張量積的概念可以證明：如果允許引入一個附屬系統，那麼任意的量子測量都可以通過投影測量加上一個幺正變換來實作。令 M = {Mm} 是希爾伯特空間 H 中的量子測量。

• 引入一個新的希爾伯特空間 HM = span{|m>}，并用它來記錄 M 所有可能的測量結果。
• 任意選取一個确定的态 |0> ∈ HM，并定義算子：

  

對于任意的 |ψ> ∈ H 都成立。很容易驗證 UM 是保内積的，并且通過引理 2.1.1 可以将它擴充為屬于 HM ⊗ H 的幺正算子，将該幺正算子也記為 UM。

• 定義在 HM ⊗ H 中的投影測量

  

  滿足

  

  對于所有的 m 都成立。

那麼，測量 M 可以通過下面的投影測量 M 和幺正算子 UM 來實作：

命題 2.1.1 令 |ψ> ∈ H 是一個純态。

• 對狀态 |ψ> 執行測量 M 時，測量結果為 m 的機率為 pM(m)，測量後對應的系統的狀态為 |ψm>。
• 對狀态

  

  = UM(|0>|ψ>) 執行測量 M 時，測量結果為 m 的機率為

  

  ，測量後對應的系統的狀态為

  

那麼對于任意的 m，都可以得到

。在下一小節中，對 H 中的混态進行研究時也會得到類似的結論。

練習 2.1.6 證明命題 2.1.1。

2.1.6 密度算子

我們已經對量子力學的四個基本假設進行了學習，但它們都隻讨論了純态的情況。本節将對這些基本假設進行擴充，使它們在混态的情況下依然适用。

有些時候我們并不清楚量子系統所處的态，但知道它是由若幹純态 |ψi> 及其相應機率p> 構成的，其中對于任意的 i，都有

。這種情況下可以使用密度算子對其進行描述。我們稱 {(|ψi>, pi)} 為純态或者混态的一個系綜，可以将該系綜的密度算子定義為：

特别地，可以将純态 |ψ> 視作一個特殊的混态 {(|ψ>, 1)}，它的密度算子為 ρ = |ψ><ψ|。

也可以用另一種方法對密度算子進行描述。雖然描述的方式不同，但本質上卻是等價的。

定義 2.1.20 算子 A ∈ L (H ) 的迹 tr(A) 的定義為：

其中 {|ψi>} 是 H 的一組标準正交基。

可以證明 tr(A) 與基 {|ψi>} 的選擇是無關的。

定義 2.1.21 希爾伯特空間 H 中的密度算子 ρ 是一個正定算子 (見定義 2.1.12)，且tr(ρ) = 1。

該定義說明對于任意的混态 {(|ψi>, p>)}，由式 (2.6) 定義的算子 ρ 是密度算子。反過來，對于任意密度算子 ρ，都存在一個（但不一定唯一）混态 {(|ψi>, p>)} 滿足式 (2.6)。

處于混态的量子系統的演化和測量可以通過密度算子進行優美的描述：

• 假設一個封閉的量子系統從時間 t0 到 t 的演變過程可以通過 t0 時間的幺正算子 U 來描述：|ψ> = U|ψ0>, 其中 |ψ0> 和 |ψ> 分别為這個系統在時間 t0 和 t 的狀态。如果這個系統在時間 t0 和 t 處于混态 ρ0 和 ρ，那麼：

• 如果一個量子系統的狀态在測量 {Mm} 之前是 ρ，那麼測量得到 m 的機率為:

  

在此情況下，該系統測量之後的狀态為：

練習 2.1.7 從式 (2.6)、量子力學基本假設一和二，推導出式 (2.7)、(2.8) 和 (2.9)。

練習 2.1.8 令 M 是一個可觀測量 (厄米算子) 且 {Pλ : λ ∈ spec(M)} 是根據 M 定義的投影測量。證明在混态 ρ 下的 M 的期望為：

約化密度算子

通過上一節介紹的量子力學第四基本假設，可以建構複合量子系統。當然，因為複合系統的狀态空間是其子系統狀态空間的張量積，也是希爾伯特空間，是以可以對複合系統的混态及其密度算子進行讨論。反過來，我們經常需要對複合量子系統的子系統的狀态進行描述。但有可能複合系統處于純态，它的一些子系統卻處于混态。這個現象是量子世界和經典世界的另一明顯不同之處。是以，如果想對複合量子系統的子系統的狀态進行恰當的描述，必須先對密度算子的概念進行介紹。

定義 2.1.22 令 S 和 T 是兩個量子系統，它們的狀态空間分别為 HS 和 HT。系統 T的偏迹

可以通過

及其線性組合進行定義，其中 |ϕ>, |ψ> ∈ HS 且 |θ>, |ζ> ∈ HT。

定義 2.1.23 令 ρ 是屬于 HS ⊗ HT 的密度算子。系統 S 的約化密度算子為：

從直覺上來講，當複合系統 ST 的狀态為 ρ 時，約化密度算子 ρS 可以對子空間 S 的狀态進行描述。讀者可以從 [174] 一書的 2.4.3 節中找到更詳細的說明。

練習 2.1.9

• 什麼情況下空間 HA ⊗ HB 中純态 |ψ> 的約化密度算子 ρA = trB(|ψ><ψ|) 不是純态？
• 令 ρ 是 HA ⊗ HB ⊗ HC 中的一個密度算子，它是否滿足 trC (trB(ρ)) = trBC (ρ)?

2.1.7 量子操作

2.1.3 節中定義的幺正變換可以對封閉型量子系統的演變進行合理的描述。但對于和外界有互動的開放式的量子系統，比如測量，就需要用更一般性的量子操作去對它的态的變化進行描述。

通常将向量空間 L (H )（即希爾伯特空間 H 中有界算子的空間）中的線性算子稱為 H 中的超算子。為了定義量子操作，首先需要對超算子的張量積進行介紹。

定義 2.1.24 令 H 和 K 是希爾伯特空間。對于任意屬于 H 的超算子 E 和屬于 K 的超算子 F，它們的張量積 E ⊗ F 是在空間 H ⊗ K 中的超算子，可以将該超算子定義為：對于任意 C ∈ L (H ⊗ K )，記

其中對于所有的 k，都有 Ak ∈ L (H ), Bk ∈ L (K )，那麼定義:

E 和 F 的線性關系保證了 E ⊗ F 是定義明确的：(E ⊗ F)(C) 與式 (2.10) 中 Ak 和 Bk的選擇無關。

現在我們開始對開放型量子系統的演化過程進行研究。将量子力學第二基本假設進行一般性推廣，假設一個系統在時間 t0 和 t 的狀态分别為 ρ 和 ρ0，那麼它們之間一定通過超算子 E 互相關聯，該超算子僅依賴于時間 t0 和 t,

可以将時間 t0 和 t 之間的動态變化視為一個實體過程：ρ 是這個過程開始之前的狀态，ρ0 是這個過程結束之後的狀态。接下來這個定義表明超算子是刻畫這一過程的恰當的模型。

定義 2.1.25 如果希爾伯特空間 H 中的量子操作滿足如下的條件，那麼該量子操作就是一個超算子：

(1) 對于任意屬于 H 的密度算子 ρ 都滿足

(2) （完備正定性）對于任意一個額外的希爾伯特空間 HR，假設 A 是 HR ⊗ H 中的一個正定算子，那麼 (IR ⊗ E )(A) 滿足正定性，其中 IR 是 L (HR) 中的機關算子，即對于任意的算子 A ∈ L (HR) 都有 IR(A) = A 成立。

對于那些将量子操作作為一款描述開放型量子系統中狀态轉換的數學模型的讨論，讀者可以參閱文獻 [174]。接下來的兩個例子告訴我們如何将幺正變換和量子測量視作特殊的量子操作。

例子 2.1.8 令 U 是希爾伯特空間 H 中的一個幺正變換。定義：

其中 ρ 是密度算子。那麼 E 是 H 中的量子操作。

例子 2.1.9 令 M = {Mm} 是 H 中的一個量子測量。

(1) 對于任意的 m，以及任意一個在測量之前狀态為 ρ 的系統，定義：

其中 pm 是測量結果為 m 的機率，ρm 是測量後對應系統的狀态，那麼 Em 是一個量子操作。

(2) 對于任意在測量之前狀态為 ρ 的系統，隻要忽略測量結果，則測量後系統的狀态為：

那麼 E 是一個量子操作。

量子資訊論中通常将量子操作作為通信信道的數學模型。為了讀取中間或最終計算結果，量子程式中通常既包含幺正變換也包含量子測量，是以最好将其視作開放式量子系統。是以本書采用量子操作作為定義量子程式語義的主要數學工具。

這裡給出的量子操作的抽象定義很難應用于實際。幸運的是，通過下面這個定理可以将量子操作視為系統與環境之間的互動，并且可以使用系統本身的算子而非超算子來對它進行表示，進而友善對該量子操作進行計算。

定理 2.1.1 下列叙述是等價的:

(1) E 是希爾伯特空間 H 中的量子操作。

(2)（系統環境模型）存在一個環境系統 E，其希爾伯特空間為 HE，U 是 HE ⊗ H 中的幺正變換，P 是向 HE ⊗ H 的閉子空間做投影變換的投影算子，那麼有：

對于所有在 H 中的密度算子 ρ 都成立，其中 |e0> 是 HE 中的一個确定的态。

(3) （Kraus 算子和表示）在 H 中存在一個有限或者可數無限的算子集合 {Ei} 滿足

并且

對于所有在 H 中的密度算子 ρ 都成立。這種情況下，通常記為:

這個定理的證明非常複雜，有興趣的讀者可以在 [174] 一書的第 8 章中找到相關内容。

2.2 量子線路

前一節介紹了量子力學的基本架構。從本節起，我們将考慮如何利用量子系統進行計算。我們會從低層次的量子計算機模型 —— 量子線路開始介紹。

2.2.1 基本定義

經典計算機的數字電路是通過依賴布爾變量的邏輯門實作的。量子線路是數字電路的量子對應物。粗略地說，它由量子邏輯門構成，其中量子邏輯門可以通過 2.1.3 節定義的幺正變換進行模組化。

我們将量子比特變量記為 p, q, q1, q2, · · ·，可以将它們想象成量子線路中的線譜。不同量子比特變量的序列 q 稱為量子寄存器。有時變量在寄存器中的順序并不重要，那麼該寄存器與其量子比特變量的集合是等價的。是以可以将集合論的概念應用于在寄存器上：

對于任意的量子比特變量 q，我們将它的希爾伯特空間記為 Hq，這與二維的希爾伯特空間H2 同構（參考例子 2.1.1）。此外，對于量子比特變量的集合 V = {q1, · · · , qn}，或者量子寄存器 q = q1, · · · , qn，将由量子比特 q1, · · · , qn 構成的複合系統的狀态空間記為:

顯然，HV 是 2^n 次元的空間。我們知道，一個 0 ≤ x ≤ 2^n 的整數可以由 n 個比特的二進制串 x1, · · · , xn ∈ {0, 1}^n 表示:

沒必要對整數 x 及二進制表示進行區分。是以，可以将任意 HV 中的純态寫作：

其中 {|x>} 稱為

的可計算基矢 。

定義 2.2.1 對于任意的正整數 n，如果 U 是一個 2^n×2^n 的幺正矩陣，且 q = q1, · · · , qn

是一個量子寄存器，那麼

G ≡ U[q] 或 G ≡ U[q1, · · · , qn]

稱為 n- 量子比特門，并且我們将 G 中的（量子）變量的集合記為 qvar(G) = {q1, · · · , qn}。

門 G ≡ U[q] 是 q 的狀态空間 Hq 中的幺正變換。我們在将幺正矩陣 U 作為量子門時，通常不會再專門提到量子寄存器 q。

定義 2.2.2 量子線路實際上是由多個量子門構成的序列：

C ≡ G1 · · · Gm

其中 m > 1，且 G1, · · · , Gm 是量子門。C 中變量的集合為：

在前兩個定義中，關于量子門和量子線路的描述與經典電路的布爾表達式非常相似，并且對其進行代數操作很友善。但是這兩個定義的展示性不強。實際上，也可以通過與描述經典電路相類似的方法對量子線路進行描述，有興趣的讀者可以在 [174] 一書的第 4 章中找到相關内容，此外還可以從

http://physics.unm.edu/CQuIC//Qcircuit/

找到繪制量子線路圖的宏包。

讓我們看看量子線路 C ≡ G1 · · · G2 是如何進行計算的。假設 qvar(C) = {q1, · · · , qn}，

并且對于任意的門都滿足

，其中寄存器

= q1, · · · , qn 的子序列且 Ui 是空間

中的幺正變換。

• 如果線路 C 的輸入狀态為 |ψ> ∈ Hqvar(C)，那麼輸出結果為:

  

其中對于任意的 i，

是 Ui 在空間 HC 中的柱面擴張，且 Ii 是空間

中的機關算子。注意在式 (2.11) 中對幺正操作 U1, · · · , Um 的使用順序與電路 C 中 G1, · · · , Gm 的順序相反。

• 更一般地，如果

  

  是一個量子比特變量的集合，那麼可以将任意的态

  |ψ> ∈ HV 寫為如下形式：

。隻要線路 C 中輸入為 |ψ>，其輸出結果一定

是：

C 的線性關系保證其輸出的定義是明确的。

如果兩個量子線路在輸入相同的情況下，輸出一定相同，那麼稱這兩個量子線路是等價的。

定義 2.2.3 令 C1 和 C2 是兩個量子線路，且

。如果對于任意的 |ψ> ∈ HV , 有：

那麼 C1 和 C2 是等價的并記為 C1 = C2。

一個具有 n 個輸入和 m 個輸出的經典線路，實際上是一個布爾函數:

與之相似，一個滿足 qvar(C) = {q1, · · · , qn} 的量子線路 C 總是等價于一個 Hqvar(C) 中的幺

正變換或者一個 2^n × 2^n 的幺正矩陣。可以從式 (2.11) 中得出這個結論。

最後，為了建構大型的量子線路，我們需要對量子線路的合成進行介紹。

定義 2.2.4 令 C1 ≡ G1 · · · Gm 且 C2 ≡ H1 · · · Hn 是量子線路，其中 G1, · · · , Gm 和 H1, · · · , Hn 都是量子門，那麼它們的合成是如下串聯結構：

C1C2 ≡ G1 · · · GmH1 · · · Hn

練習 2.2.1

(1) 證明：如果 C1 = C2，那麼對于任意的 |ψ> ∈ HV 和任意的 V ⊇ qvar(C1)∪qvar(C2)， 式 (2.12) 都成立。

(2) 證明：如果 C1 = C2，那麼 CC1 = CC2 且 C1C = C2C。

2.2.2 單量子比特門

在介紹了量子門和量子線路的一般性定義之後，本節将介紹一些例子。

最簡單的量子門是單量子比特門。它可以通過一個 2 × 2 的幺正矩陣來表示。在例子 2.1.3 中的 Hadamard 門就是一類單量子比特門。下面是其他一些在量子計算中常用的單量子比特門。

例子 2.2.1

(1) 全局相移:

其中 α 是實數，且：

是一個 2 × 2 的機關矩陣。

(2)（相對）相移：

其中 α 是實數。特别地，有：

(a) 相位門：

(b) π/8 門：

例子 2.2.2 泡利矩陣：

顯然，我們有 X|0> = |1>, X|1> = |0>。是以泡利矩陣 X 實際上是一個非門。

例子 2.2.3 布洛赫球體關于 xˆ、yˆ、zˆ 軸的旋轉分别為:

其中 θ 是實數。

例子 2.2.3 給出的量子門有一個很好的幾何解釋：單量子比特的态可以通過布洛赫球體中的向量進行表示。在該态上執行 Rx(θ)、Ry(θ)、Rz(θ) 相當于将它分别以 x 軸、y 軸、z 軸為軸旋轉 θ 角。讀者可以在 [174] 一書的 1.3.1 節和 4.2 節找到更詳細的資料。可以證明任何單量子比特門都可以通過旋轉和全局相移組成的線路來表示。

練習 2.2.2 證明前三個例子中的矩陣都具有幺正性。

2.2.3 受控門

對于量子計算而言，僅有單量子比特門還不夠。本節中，我們将介紹一種重要的多量子比特門 —— 受控門。

在這些受控門中，最常用的是 CNOT 算子 C（參考例子 2.1.7）。本節将用另一種方式對其進行描述。令 q1 和 q2 是量子比特變量。那麼 C[q1, q2] 是兩量子比特門，其中 q1 是控制量子比特，q2 是目标量子比特。它的執行方式如下：

其中 i1, i2 ∈ {0, 1}，⊕ 是模二加法 。即如果 q1 為 |1>，那麼将 q2 反轉；否則 q2 不做任何

改變。通過對 CNOT 門進行簡單的推廣，我們有：

例子 2.2.4 令 U 是一個 2 × 2 的幺正矩陣，那麼受控 U 門是一類兩量子比特門，其定義如下：

其中 i1, i2 ∈ {0, 1}。它的矩陣表示為：

其中 I 是一個 2 × 2 的機關矩陣，顯然 C = C(X)，即 CNOT 是一個受控 X 門，其中 X 是泡利矩陣。

練習 2.2.3 SWAP 是另一類兩量子比特門，其定義為：

其中 i1, i2 ∈ {0, 1}。從本質上而言，它将兩個量子比特的狀态進行交換。SWAP 門可以通過三個 CNOT 門來實作：

練習 2.2.4 證明受控門具有如下屬性：

(1) C[p, q] = H[q]C(Z)[p, q]H[q]

(2) C(Z)[p, q] = C(Z)[q, p]

(3) H[p]H[q]C[p, q]H[p]H[q] = C[q, p]

(4) C(M(α))[p, q] = P(α)[p]

(5) C[p, q]X[p]C[p, q] = X[p]X[q]

(6) C[p, q]Y [p]C[p, q] = Y [p]X[q]

(7) C[p, q]Z[p]C[p, q] = Z[p]

(8) C[p, q]X[q]C[p, q] = X[q]

(9) C[p, q]Y [q]C[p, q] = Z[p]Y [q]

(10) C[p, q]Z[q]C[p, q] = Z[p]Z[q]

(11) C[p, q]T[p] = T[p]C[p, q]

上述所有的控制門都是兩量子比特門。實際上，我們可以對受控門進行更一般性的

定義：

定義 2.2.5 令

= p1, · · · , pm 和

是寄存器，且

∩

= ∅。如果 G = U[

] 是一個量子門，那麼以

作為控制量子比特并以

作為目标量子比特的受控線路

是希爾伯特空間

中的幺正變換。可以将其定義為：

對于任意的

都成立。

接下來這個例子介紹了一類三量子比特受控門。

例子 2.2.5 令 U 是一個 2 × 2 的幺正矩陣，p1, p2, q 為量子比特變量。雙重受控 U 門

是空間 Hp1 ⊗ Hp2 ⊗ Hq 中的幺正變換。對于所有的 t1, t2 ∈ {0, 1} 且 |ψi ∈ Hq 都有：

特别地，我們将雙重受控 NOT 門也稱為 Toffoli 門。

Toffoli 門是經典可逆計算 中的通用門。隻需稍作擴充（按照 2.2.5 節所定義的方式）就能使它成為量子計算中的通用門。此外，在量子糾錯中也會經常用到 Toffoli 門。

練習 2.2.5 通過如下等式将多個受控門組成一個新的控制門，請對這些等式進行證明：

(1) C(p)(C(q)(U)) = C(p,q)(U)

(2) C(p)(U1)C(p)(U2) = C(p)(U1U2)

2.2.4 量子多路複用器

可以将受控門的概念進一步擴充為多路複用器 。本節中，我們将介紹量子多路複用器的概念及其矩陣表示。

對于經典計算而言，最簡單的多路複用器是條件語句“if· · · then· · · else· · ·”：當“if”為真時，執行“then”後面的語句；當“if”為假時，執行“else”後面的語句。條件語句可以通過并行處理“then”和“else”子句，再多路複用輸出結果的方式來實作。

量子條件語句是對經典條件語句的量子模拟：“if”之後的條件（布爾表達式）替換為一個量子比特，即通過量子比特的基态 |1> 和 |0> 來替換真值 true 和 false。

例子 2.2.6 令 p 是一個量子變量，

= q1, · · · , qn 是一個量子寄存器，且令 C0 = U0[

] 和 C1 = U1[

] 是量子門。那麼量子條件語句 C0 ⊕ C1 是一個 1 + n 量子比特邏輯門，其中第一個量子比特 p 是選擇量子比特，剩下的 n 個量子比特 q 則是資料量子比特，其定義為：

對于任意的 |ψ> ∈ Hq 都成立，其中 i ∈ {0, 1}。也可以将它等價地定義為矩陣：

在例子 2.2.4 中定義的受控門是一類特殊的量子條件語句：C(U) = I ⊕ U, 其中 I 是機關矩陣。

量子條件語句和經典條件語句的本質差別在于選擇量子比特不僅可以處于基态 |0> 和 |1>，也可以處于疊加态：

對于任意的 |ψ0>, |ψ1> ∈ Hq 都成立，并且對于任意的複數 α0 和 α1 都滿足 |α0|^2 +|α1|^2 = 1。

多路複用器是對條件語句的多層擴充。粗略來講，多路複用器就是一個開關，它将其中一個輸入資料傳遞到輸出中，就像一個標明了一組輸入的函數。與之類似，量子多路複用器(簡稱 QMUX) 是對量子條件語句的多路擴充。

定義 2.2.6 令

= q1, · · · , qn 為量子寄存器。令 Cx = Ux[

] 是一個量子門，其中 x ∈ {0, 1}^m。那麼 QMUX

是一個 m + n 量子比特門，其中前 m 個量子比特

是選擇量子比特，其餘的 n 個量子比特

是資料量子比特。它将保持選擇量子比特的态，并根據選擇量子比特的态對相應的資料量子比特進行幺正變換：

對于任意的 t ∈ {0, 1}^m 和 |ψ> ∈ Hq 都成立。

QMUX 可以通過對角矩陣來表示：

這裡，我們将整數 0 ≤ x ≤ 2^m 用二進制表示法 x ∈ {0, 1}^m 進行表示。經典多路複用器和QMUX 還有一個不同之處在于選擇量子比特 p 可以處于基态 |x> 的疊加态：

對于任意的态 |ψx> ∈ Hq(0 ≤ x ≤ 2^m) 都成立，且式中任意的複數 αx 都滿足

顯然，在定義 2.2.5 中介紹的受控門是一種特殊的 QMUX：

其中前 2^m − 1 個被加項是和 U 具有相同次元的機關矩陣。

練習 2.2.6 證明多路複用器滿足如下屬性：

下一節我們将會看到 QMUX 在量子遊走中一個簡單的應用。第 6 章會對 QMUX 和量子程式結構（量子 case 語句）之間的内在關聯進行介紹。QMUX 已經成功地應用于量子線路的合成（參見文獻 [201]），是以它在編譯量子程式的時候也會很有用。

2.2.5 量子門的通用性

在前三個小節中，我們已經介紹了幾類重要的量子門。人們自然會問：對于量子計算而言僅有這些門足夠嗎？本節就來回答這個問題。

為了更好地了解這個問題，讓我們先對經典計算中類似的問題進行思考。對于任意的n > 0，存在 22n 個 n 進制的布爾函數 。整體上而言，我們有無數個布爾函數。但是存在一些小型的邏輯門的集合，它們具有通用性：通過它們可以産生所有的布爾函數。例如，{NOT，AND}，{NOT，OR}。我們可以将這種通用性的概念推廣到量子門當中：

定義 2.2.7 如果所有幺正矩陣都可以通過一個幺正矩陣的集合 Ω 産生，那麼就稱這個集合具有通用性；即對于任意的正整數 n 和任意的 2^n × 2^n 幺正矩陣 U，都存在一個滿足qvar(C) = {q1, · · · , qn} 的線路 C，且該線路是通過屬于 Ω 中的幺正矩陣定義的門所構造的，使得：

U[q1, · · · , qn] = C

（這與定義 2.2.3 中介紹的線路等價。）

下面的定理将介紹一種最簡單的通用量子門集合。

定理 2.2.1 由 CNOT 門和所有的單量子比特門構成的集合具有通用性。

上述讨論的經典邏輯門的通用集合總是一個有限集。但是定理 2.2.1 中給出的通用量子門集合中的元素卻是無限的。事實上，幺正算子的集合構成一個連續統，該連續統是不可數無限的。是以不可能通過量子門的有限集合去實作任意一個幺正算子。這就迫使我們去研究量子門的近似通用性，而非定義 2.2.7 中所介紹的完全通用性。

定義 2.2.8 如果對于任意的幺正算子 U 和任意的 ε > 0，都存在一個滿足 qvar(C) ={q1, · · · , qn} 的線路 C，且該線路是通過屬于 Ω 中的幺正矩陣定義的門所構造的：

其中距離 d 是通過式 (2.2) 定義的，那麼稱該集合 Ω 具有近似通用性。

下面的定理介紹了兩種常見的近似通用門的集合。

定理 2.2.2 下列兩個門的集合具有近似通用性：

(1) Hadamard 門 H、π/8 門 T 和 CNOT 門 C。

(2) Hadamard 門 H、相位門 S、CONT 門 C 和 Toffoli 門（參考例子 2.2.5）。

此處省略了定理 2.2.1 和定理 2.2.2 的證明，有興趣的讀者可以在 [174] 一書的 4.5 節找到關于這兩個定理的證明。

2.2.6 量子線路的測量

上一節介紹的通用性理論表明任何量子計算都可以通過由 2.2.2 節和 2.2.3 節所述的基本量子門構成的量子線路來實作。但是量子線路的輸出通常是一個量子态，外界是不能直接觀測的。為了讀取計算結果，需要線上路運作結束時執行量子測量。是以我們需要對一般性量子線路的概念進行研究，即包含量子測量的線路。

正如 2.1.4 節所述，如果允許引入附屬量子比特，那麼僅需要使用投影測量。此外，如果線路中包含 n 個量子比特變量，那麼因為這些量子比特的其他标準正交基都可以通過對可計算基矢進行幺正變換得到，是以僅在可計算基矢 {|xi : x ∈ {0, 1}n} 上執行測量就足夠了。

實際上，量子測量并不隻是在計算結束後使用。我們還經常将它作為計算的中間步驟，并以測量結果作為控制後續計算步驟的條件。但是 Nielsen 和 Chuang [174] 明确指出：

• 延遲測量原理: 測量總是可以從一個量子線路的中間階段移動到線路的最後階段；如果線路的任何階段都需要使用測量結果，那麼可以用條件量子操作替換經典受控操作。

練習 2.2.7 詳細闡述延遲測量原理，并對它進行證明。該證明可以通過如下步驟完成：

(1) 我們可以通過歸納法對包含測量的量子線路（簡稱 mQC）進行形式化定義：

(a) 每個量子門都是一個 mQC。

(b) 如果 q 是量子寄存器，M = {Mm} = {Mm1, Mm2 , · · · , Mmn } 是屬于 Hq 的量子測量，且對于任意的 m，Cm 都是一個 mQC 且滿足 q ∩ qvar(Cm) = ∅，那麼：

也是 mQC。

(c) 如果 C1 和 C2 都是 mQC，那麼 C1C2 也是。

式 (2.13) 表明，我們在 q 上執行測量 M，那麼後續的計算步驟是根據測量結果進行選擇的：如果測量結果為 m，那麼接下來會執行相應的線路 Cm。

(2) 将量子線路之間的等價性關系 (定義 2.2.3) 擴充到 mQC 的情況。

(3) 證明對于任意的 mQC C，都存在量子電路 C0 (不包含測量) 和量子測量 M[

] 滿足 C = C0M

如果将 (2) 中的條件

∩ qvar(Cm) = ∅ 去掉，那麼被測量的量子比特在測量後的态可以在接下來的計算過程中使用。這種情況下延遲測量原理是否依然适用？

2.3 量子算法

上一節介紹的包含測量的量子線路是一個完整（卻底層）的量子計算模型。自 20 世 紀 90 年代初以來，已經發現了許多比對應的經典算法計算速度更快的量子算法。由于曆史原因，再加上當時缺少成熟的量子程式設計語言，導緻這些算法都是通過量子線路模型進行描述的。

在本節中，我們将介紹幾個有趣的量子算法。我們的目的是為接下來介紹的量子程式設計結構提供例子，而不是對量子算法本身進行較長的描述。如果讀者想盡快進入本書的核心，可以跳過這一節，直接看第 3 章。接下來的章節中将會程式設計實作這一節介紹的算法，是以如果讀者想了解這些内容就需要閱讀本節。

2.3.1 量子并行性與量子幹涉

我們将從設計量子算法的兩種基本技術開始 —— 量子并行性與量子幹涉。這是量子計算機能夠勝過經典計算機的兩個關鍵因素。

量子并行性

我們可以通過一個簡單的例子對量子并行性進行清晰的闡述。考慮一類 n 進制的布爾函數：

它的任務是對不同的輸入 x ∈ {0, 1}n 同時計算 f(x)。粗略地講，經典情況下想要并行完成這項任務需要建立多個計算相同函數 f 的電路，它們同時對不同的輸入 x 進行計算。相比之下，我們僅需要建立一個單量子線路并執行幺正變換：

這樣就可以完成任務，其中任意的 x ∈ {0, 1}^n, y ∈ {0, 1}^n。顯然，幺正操作 Uf 是依照布爾函數 f 設計的。該線路由 n + 1 個量子比特組成，前 n 個量子比特為“資料”寄存器，最後一個量子比特是“目标”寄存器。可以證明對于任意一個計算 f 的經典電路，都可以建構一個具有相似複雜度的量子線路去實作 Uf。

練習 2.3.1 證明 Uf 是一個多路複用器 (參考定義 2.2.6)：

其中前 n 個量子比特為選擇量子比特，對于任意的 x ∈ {0, 1}^n，Uf,x 是在最後一個量子比特上執行的幺正操作：

其中 y ∈ {0, 1}；即如果 f(x) = 0，那麼 Uf,x 是一個機關算子 I；如果 f(x) = 1，那麼它是非

門。

接下來的流程說明了如何通過量子并行性同時計算所有可能的輸入 x ∈ {0, 1}n 所對應的 f(x) 的值：

• 通過 n 個 Hadamard 門就可以非常有效地産生資料寄存器中 2^n 個基态的等權疊加态 ：

（n 個 |0> 的張量積），且 H⊗n = H ⊗ · · · ⊗ H（n 個 H 的張量積）。

• 對處于态 |ψ> 的資料寄存器執行幺正變換 Uf，将目标寄存器的态設定為 |0>：

應當注意到，該等式僅執行了一次幺正操作 Uf，但是方程右側的不同項包含了關于所有x ∈ {0, 1}^n 的 f(x) 的值。從某種意義上而言，該式同時對 f(x) 的 2^n 個輸入進行了計算。

但是僅有量子并行性，量子計算機還不足以勝過經典計算機。實際上，為了從式 (2.15)等号右邊的狀态中提取資訊，我們必須做一次測量；舉例而言，如果我們在資料寄存器的可計算基矢 {|xi : x ∈ 0, 1^n} 上執行測量，那麼我們隻能得到單個 x (機率為 1/2n) 對應的 f(x)的值，并不能同時得到所有 x ∈ {0, 1}n 對應的 f(x) 的值。是以，如果我們使用這種方法提取資訊，那麼量子計算機相對于經典計算機将毫無優勢可言。

量子幹涉

為了使上述方法真正發揮作用，必須将量子并行性與量子系統的另一特性相結合，這種特性就是量子幹涉。舉例而言，讓我們思考疊加态

顯然式 (2.15) 的等号右邊是該疊加态的一種特殊情況。正如之前所言，如果我們直接在可計

算基矢上測量資料寄存器，隻能得到單個 x 對應的 f(x) 的局部資訊。但是如果我們先在數

據寄存器上執行一個幺正操作 U，将該疊加态轉化為：

。此時再在可計算基矢上對其進行測量，就能得到所有 x ∈ {0, 1}^n 對應的 f(x) 的全局資訊。這個全局資訊寄存于

的某單一的值 x' 中。從某種意義上來說，幺正操作 U 可以将不同 x 的取值所對應的 f(x)的資訊進行合并。值得注意的是，幺正變換之後執行測量的基與幺正變換之前執行測量的基是不同的。是以在測量時選取合适的基對于提取全局資訊至關重要。

2.3.2 Deutsch-Jozsa 算法

上一小節中關于量子并行性和量子幹涉的讨論仍然不能說明它們是否真的可以幫助我們解決一些實際的計算問題。但在 Deutsch-Jozsa 算法 中，我們可以清楚地看到量子并行性和量子幹涉相結合的力量。該算法解決了如下問題：

• Deutsch 問題：給定一個布爾函數 f : {0, 1}^n → {0, 1}，該函數可能是常數或平衡函數（即對于所有可能的 x，f(x) 有一半的機率為 0，一半的機率為 1）。判斷該函數是常數還是平衡函數。

該算法如圖 2.1 所示。需要注意的是，在這個算法中我們将由式 (2.14) 定義的函數 f 所決定的幺正操作 Uf 稱為量子黑盒。

為了更好地了解該量子算法，我們需要仔細研究設計過程中的幾個關鍵思想：

• 在第 2 步中，目标寄存器（最後一個量子比特）被巧妙地初始化為态 |−> = H|1i 而不是如式 (2.15) 所述的态 |0>。因為

  

是以通常将這類特殊的初始化方式稱為相位反沖技巧。這裡隻有将目标寄存器的相位從 1 變為

，才能将該相位移動到資料寄存器之前。

• 在第 3 步使用量子黑盒 Uf 的時候展現了量子并行性。
• 量子幹涉在第 4 步中使用：将 n 個 Hadamard 門作用在資料寄存器上（前 n 個量子比特）可以得到：

• 在第 5 步中，我們在可計算基矢

  

  上對資料寄存器進行測量。得到測量結果為 z = 0 (即 |z> = |0>^⊗n) 的機率是：

  

有趣的是，當 f 是平衡函數時，|0>^⊗n 的機率幅的正負貢獻值會互相抵消。

練習 2.3.2 證明式 (2.16) 中的等式：

對于任意的 x ∈ {0, 1}^n 都成立，其中如果滿足 x = x1, · · · , xn, z = z1, · · · , zn，則

最後，讓我們簡要對比一下通過經典計算和 Deutsch-Jozsa 算法來解決 Deutsch 問題的查詢複雜度。經典算法需要重複地在 x ∈ {0, 1}^n 中取值并計算 f(x)，直到能夠确定 f 是常數還是平衡函數。是以，經典算法需要對 f 進行

次計算。相比之下，Deutsch-Jozsa算法僅需要在第 3 步執行一次 Uf 操作即可。

2.3.3 Grover 搜尋算法

Deutsch-Jozsa 算法恰當地闡述了設計量子算法中的幾個關鍵點，但通過該算法解決的通常是某種人為構造的問題。本節我們将介紹一種在實際應用中非常有用的量子算法 ——Grover 算法。該算法可以解決如下問題：

• 搜尋問題：目的是對一個具有 N 個元素的資料庫進行搜尋，且該資料庫中元素的索引為 0, 1, · · · , N − 1。為了友善起見，我們假設 N = 2^n，這樣就可以通過 n 個比特對資料庫中的索引進行存儲。此外，假設該問題恰好有 M 個解且 1 ≤ M ≤ N/2。 與 Deutsch-Jozsa 算法相似，Grover 算法中也有一個量子黑盒，該黑盒可以識别搜尋問題的解。我們可以對其進行形式化描述：定義函數 f : {0, 1, · · · , N − 1} → {0, 1} 為：

  

我們記

其中 H2 是單量子比特的态空間。那麼可以将該黑盒視作 HN⊗H2 中的幺正算子 O = Uf：

對于任意的 x ∈ {0, 1, · · · , N − 1}, q ∈ {0, 1} 都成立，其中 |x> 是索引寄存器，|q> 是黑盒量子比特，即當 x 是解的時候會反轉，否則保持不變。特别地，這個黑盒具有相位反沖屬性：

是以，如果黑盒量子比特的初始态為 |−>，那麼它會在整個算法執行過程中保持 |−> 不變，是以可以在公式中将其省略：

Grover 旋轉

Grover 旋轉是 Grover 算法的一個重要子程式。如圖 2.2 所示，它由四個步驟組成，讓我們看看 Grover 旋轉究竟做了什麼。我們将圖 2.2 所定義的幺正變換記為 G，即 G 由步驟1∼4 中的算子所構成。需要指出第 1 步中使用的黑盒 O 是在空間 HN 中的幺正算子 (而非空間 HN ⊗ H2)。在第 3 步中的條件相位變換是在空間 HN 的基 {|0>, |1>, · · · , |N − 1>} 上定義的。接下來的引理表明這個量子線路中的幺正算子實作了 Grover 旋轉。

引理 2.3.1 G = (2|ψ><ψ| − I)O，其中

是 HN 中的等權疊加。

練習 2.3.3 證明引理 2.3.1。 很難從上面的描述中想象出算子 G 實際上代表了旋轉操作。通過幾何可視化能夠幫助我們更好地了解 Grover 旋轉。讓我們引入空間 HN 中的兩個向量：

顯然，兩個向量是正交的。如果我們将夾角 θ 定義為：

那麼可以将引理 2.3.1 中所述的等權疊加态表示為：

此外，我們有:

引理 2.3.2

直覺而言，Grover 算子 G 是由 |α> 和 |β> 擴充成的二維空間中的一個角度為 θ 的旋轉。對于任意的實數 δ，向量 cos δ|α> + sin δ|β> 都可以通過點 (cos δ,sin δ) 來表示。是以，引理 2.3.2 表明 G 可以通過如下映射關系表示：

練習 2.3.4 證明引理 2.3.2。

Grover 算法

Grover 算法以 Grover 旋轉作為子程式，該算法如圖 2.3 所示。

應當注意到在圖 2.3 中，k 是一個整型常量；在下一段中将對如何選取 k 值進行說明。

性能分析

可以證明經典計算機解決搜尋問題大緻需要 N/M 次操作。讓我們看看 Grover 算法的第 3 步中需要疊代多少次 G。注意在第 2 步中，索引寄存器（也就是前 n 個量子比特）的初始狀态為：

是以旋轉弧度

可以使索引寄存器從 |ψ> 态變化為 |β> 态。引理 2.3.2 表明 Grover算子 G 是一個 θ 角度的旋轉。令 k 是一個最接近實數 Q 的整數：

因為

，是以有：

是以，k 是一個屬于區間

的正整數。根據假設

，我們可以得到：

且

，即 k = O(√N)。另一方面，通過 k 的定義我們可以得到：

由此可得：

，是以有

是以，因為

，是以算法執行成功的機率為：

也就是說 Pr(success) = Θ(1)。特别地，如果 M << N，那麼成功的機率将會非常高。

可以将前面的描述總結為：Grover 算法可以以 O(1) 的成功率在 k = O(√N) 步之内找到解 x。

2.3.4 量子遊走

在設計 Deutsch-Jozsa 算法和 Grover 算法的過程中，我們已經感受到了量子并行性和量子幹涉的力量。本節我們将對另一類量子算法進行研究，這類算法的設計思路與前兩個算法完全不同，它是基于量子遊走（即經典随機遊走的量子對應物）的概念進行設計的。

一維空間的量子遊走

最簡單的随機遊走是一維空間遊走：一個粒子在一條離散的直線上移動，我們可以将這個直線上的節點記為 Z = {· · · , −2, −1, 0, 1, 2, · · · }。在每一次的遊走過程中，該粒子都會根據“擲硬币”的結果向左或者向右移動一位。對一維空間随機遊走進行量子化擴充，就可以得到 Hadamard 遊走。Hadamard 遊走的定義如下：

例子 2.3.1 Hadamard 遊走的希爾伯特态空間為 Hd ⊗ Hp，其中：

• Hd = span{|L>, |R>} 是二維希爾伯特空間，稱為方向空間。|L> 和 |R> 分别表示方向Left 和 Right。
• Hp = span{|n> : n ∈ Z} 是無限維希爾伯特空間，且 |n> 代表整數 n 所标記的位置。

且 spanX 是一個非空的集合 X，它是根據式 (2.1) 定義的。Hadamard 遊走中的每一步都可

以通過幺正算子

來表示，其中平移變換 T 是空間 Hd ⊗ Hp 中的一個幺正算子，我們可以将其定義為：

對于任意的 n ∈ Z 都成立，其中 H 是方向空間 Hd 中的 Hadamard 變換，IHp 是位置空間Hp 中的機關算子。對算子 W 進行疊代就構成了 Hadamard 遊走。

練習 2.3.5 将位置空間 Hp 中的左移算子 TL 和右移算子 TR 定義為：

對于任意的 n ∈ Z 都成立。那麼平移變換算子 T 實際上就是以方向變量作為選擇量子比特的量子條件語句 TL ⊕ TR（參考例子 2.2.6）。

雖然 Hadamard 遊走是仿照一維随機遊走進行設計的，但是它們的一些行為卻完全不同：

• 可以将平移變換算子 T 描述為：如果方向系統處于 |L> 态，那麼遊走粒子将會從位置 n 移動到 n − 1，如果方向系統處于 |R> 态，那麼遊走粒子将會從位置 n 移動到n + 1。這看起來和随機遊走非常相似，但在量子遊走中方向可以處于 |L> 和 |R> 的疊加态，這樣遊走粒子就可以同時向左和向右進行移動。
• 在随機遊走中，我們隻需要精确地統計“擲硬币”的結果；舉例而言，投擲一枚公平“硬币”得到正面朝上和反面朝上的機率均為 1/2。但在量子随機遊走當中，我們不得不明确地定義隐藏于“硬币”的統計行為之下的動力學；舉例而言，可以将 Hadamard變換 H 視作公平“硬币”的量子實作，而如下 2 × 2 的幺正矩陣（類似的矩陣還有很多）也是如此：

• 量子遊走中可能會有量子幹涉發生；例如，令 Hadamard 遊走的初始狀态為 |L>|0>。那麼我們有：

其中 −|R>|0> 和 |R>|0> 是異相的，是以它們可以互相抵消。

圖上的量子遊走

圖上的随機遊走是一類在設計和分析算法時常用到的随機遊走。令 G = (V, E) 是一個n-途徑正則有向圖，即圖中每個頂點都有 n 個鄰接頂點。那麼我們可以對每個頂點的每條鄰邊用一個從 1 到 n 之間的整數 i 進行标記，對于任意的 1 ≤ i ≤ n，标号為 i 的有向邊都可以構成一個排列。通過這種方法可以将任意頂點 v 的第 i 個鄰接頂點 vi 定義為與 v 通過标号為 i 的邊相連接配接的頂點。在圖 G 上的随機遊走的定義為：G 上的頂點 v 代表遊走粒子的态且對于任意一個态 v，遊走粒子從 v 移動到它的每個鄰接頂點的機率都是确定的。可以将這類随機遊走進行量子化擴充：

例子 2.3.2 在 n-途徑正則圖 G = (V, E) 上的量子遊走的希爾伯特空間為 Hd ⊗ Hp，其中：

• 

  是一個 n 維的希爾伯特空間。我們引入一個被稱為方向“硬币”的輔助量子系統，該系統的态空間為 Hd。對于任意的 1 ≤ i ≤ n，态 |i> 代表第 i 個方向。空間 Hd 稱為“硬币空間”。

• 

  是位置希爾伯特空間。對于圖中的每個頂點 v，Hp 中都存在一個相對應的基态 |v>。

移位 S 是 Hd ⊗ Hp 中的一個算子，其定義為：

對于任意的 1 ≤ i ≤ n, v ∈ V 都成立，其中 vi 是 v 的第 i 個鄰接頂點。直覺上而言，對于任意的 i，如果“硬币”處于态 |i>，那麼遊走粒子會朝第 i 個方向進行移動。當然，“硬币”也可以處于态 |i>(1 ≤ i ≤ n) 的疊加态，這種情況下遊走粒子會同時朝所有方向移動。

如果我們進一步在“硬币”空間 Hd 中標明一個被稱為“擲硬币算子”的幺正算子 C，那麼可以通過如下幺正算子對圖 G 上的單步量子遊走進行模組化：

其中 IHp 是位置空間 Hp 中的機關算子。例如，可以選擇離散傅裡葉變換 (FT) 來實作公平

“硬币”，其中：

為“擲硬币”算子，ω = exp (2πi/d)。FT 算子将每個方向都映射為方向的疊加态，且對該疊加态進行測量之後得到任一方向的機率均為 1/d。對單步遊走算子 W 進行疊代就構成了圖上的量子遊走。

練習 2.3.6 對于任意的 1 ≤ i ≤ n，我們可以在位置空間 HV 中定義一個移位算子 Si：

對于任意的 v ∈ V 都成立，其中 vi 代表 v 的第 i 個鄰接頂點。如果我們允許量子多路複用器 (QMUX) 中的選擇變量為任意量子變量，而并非僅僅是量子比特，那麼例子 2.3.3 中的移位算子 S 就是以方向 d 作為選擇變量的 QMUX ⊕i Si。

可以發現，有時量子遊走中的量子效應（比如幹涉）可以為遊走提供明顯的加速；例如，相較于經典的随機遊走，它能夠使得量子遊走從一個頂點更快地到達另一個頂點。

2.3.5 量子遊走搜尋算法

我們能利用上一小節最後提出的量子加速思想設計出勝過經典算法的量子算法嗎？在本節中，我們将介紹這樣一種能夠解決 2.3.3 節中搜尋問題的算法。

假設資料庫由 N = 2n 個元素構成，該資料庫中所有元素都通過 n 個比特的二進制串x = x1 · · · xn ∈ {0, 1}^n 進行編碼。在 2.3.3 節中，我們假設恰好存在 M 個解。此處我們僅考慮 M = 1 的特殊情況。是以，算法的目的是找到單一目标解 x∗。本小節中的搜尋算法是基于 n 維超立方體上的量子遊走設計的。n 維超立方體有 2n 個頂點，且每個頂點都對應于資料庫中的一個元素 x。如果兩個頂點 x 和 y 僅有一個比特不同，那麼就稱這兩個頂點是相連的：

也就是說，x 和 y 的二進制編碼中僅有一位比特不同。是以，n 維超立方體中的 2n 個頂點的度數都是 n（即每個頂點都與其他 n 個頂點相連接配接）。

作為例子 2.3.2 的一個特殊情況，我們可以将在 n 維超立方體上的量子遊走描述為：

• 希爾伯特态空間是 Hd ⊗ Hp，其中 Hd = span{|1>, · · · , |n>}，

  

且 H2 是單量子比特的态空間。

• 移位算子 S 将 |d, x> 映射為 |d, x ⊕ ed>（将 x 的第 d 個比特進行反轉），其中 ed = 0 · · · 010 · · · 0（第 d 個比特是 1，其餘為 0）是 n 維超立方體的第 d 個基向量。也可以将它形式化地描述為：

  

其中 ⊕ 是分量方式的模二加法。

• 将“擲硬币”算子 C 作為不帶黑盒的 Grover 旋轉（參考引理 2.3.1）：

  

其中 I 是空間 Hd 的機關算子，|ψd> 是所有 n 個方向的等權疊加态：

|d> 與 Grover 算法相似，我們有一個可以對目标元素 x∗ 進行标記的黑盒。假設這個黑盒是通過 C 的擾動進行實作的：

其中 C' 是 Hd 中的幺正算子。直覺上而言，每當目前位置對應的是非目标元素時，該黑盒就會對方向系統使用原來的“擲硬币”算子 C，而需要對目标元素 x∗ 進行标記時使用的卻是一類特殊的“硬币”C'。

搜尋算法的基本流程為：

• 将量子計算機初始化為所有的方向和所有的位置的等權疊加态：|ψ0> = |ψd> ⊗ |ψp>，其中，

• 使用 t 次受擾亂的單步遊走算子：

，W 是通過式 (2.20) 定義的單步遊走算子。

• 在基 |d, x> 上對量子計算機的态進行測量。

在本算法中使用的“擲硬币”算子 D 和例子 2.3.2 中的原始“擲硬币”算子 C（更确切地說，是 C ⊗ I）有明顯的不同：算子 C 隻在方向空間上起作用，是以它和位置空間是互相獨立的。但 D 是通過使用标記目标元素 x' 的 C' 對 C ⊗ I 進行修改得到的，從式 (2.22) 中顯然可以發現 D 是位置相關的。

對于 C' = −I 的情況，已經證明該算法找到目标元素的機率為

，是以通過重複執行該算法，可以以任意小的誤差機率找到目标元素。這裡不對該算法的性能進行分析，有興趣的讀者可以從文獻 [203] 中找到相關内容。

我們鼓勵讀者将這類基于量子遊走的搜尋算法和 2.3.3 節介紹的 Grover 搜尋算法進行仔細比較。

2.3.6 量子傅裡葉變換

另一類重要的量子算法是基于量子傅裡葉變換設計的。回想一下離散傅裡葉變換，它以複向量 x0, · · · , xN−1 作為輸入，輸出複向量 y0, · · · , yN−1：

對于任意的 0 ≤ j ≤ N 都成立。将離散傅裡葉變換進行量子化擴充，就可以得到量子傅裡葉變換。

定義 2.3.1 在标準正交基 |0>, · · · , |N − 1> 上的量子傅裡葉變換為：

更一般地，在 N 維希爾伯特空間中一般态上的量子傅裡葉變換為：

其中，機率幅 y0, · · · , yN−1 是通過對機率幅 x0, · · · , xN−1 執行離散傅裡葉變換得到的。式 (2.21) 給出了量子傅裡葉變換的矩陣表示。

命題 2.3.1 量子傅裡葉變換 FT 是幺正的。

練習 2.3.7 證明命題 2.3.1。

量子傅裡葉變換線路

接下來的命題及其證明給出了量子傅裡葉變換通過單比特邏輯門和兩比特邏輯門進行實作的一種方案。

命題 2.3.2 令 N = 2n。那麼量子傅裡葉變換可以通過由 n 個 Hadamard 門和

個受控門組成的量子線路實作。

證明：可以通過構造一個滿足上述條件的量子線路來證明該命題。我們使用二進制來表

示：

• j1j2 · · · jn 表示

  

• 0.jkjk+1 · · · jn 表示

  

對于任意的 k ≥ 1 成立。

可以通過如下三步來對該命題進行證明：

(1) 使用 2.2 節介紹的概念，我們設計如下線路：

其中 Rk 代表相移（參考例子 2.2.1）：

對于任意的 k = 2, · · · , n 都成立。如果我們将 |j> = |j1 · · · jn> 輸入到線路 (2.24) 中，那麼通過計算得到輸出為：

(2) 可以發現當 N = 2^n 時，量子傅裡葉變換可以改寫為如下形式：

(3) 最後，通過比較公式 (2.26) 和 (2.25)，我們發現線上路 (2.24) 的最後添加

個SWAP 門就可以将量子比特的順序進行反轉，是以可以導出量子傅裡葉變換。其中 SWAP門可以通過 3 個 CNOT 門實作（參考例子 2.2.3）。

2.3.7 相位估計

現在讓我們看看上一節定義的量子傅裡葉變換如何在相位估計算法中使用。這個量子算法解決了如下的問題：

• 相位估計：一個幺正算子 U 有一個特征向量 |ui，且該特征向量對應的特征值為

  

  ,其中 ϕ 的值是未知的。該算法的目标是對相位 ϕ 進行估算。

相位估計算法如圖 2.4 所述。它使用兩個寄存器：

• 第一個寄存器由 t 個初始化為 |0> 的量子比特 q1, · · · , qt 構成。
• 第二個寄存器是經 U 作用的系統 p，該系統的初始态為 |u>。

使用 2.2 節介紹的相關概念，可以将該線路的算法寫成如下形式：

其中：

C(·) 是受控門（參考定義 2.2.5），FT† 是量子傅裡葉變換（FT）的逆變換，它可以通過對命

題 2.3.2 的證明中給出的 FT 線路進行反轉得到。

顯然，線路 (2.27) 由 O(t^2) 個 Hadamard 門和受控門以及對黑盒 U2j 的一次調用構成，其中 j = 0, 1, · · · , t − 1。進一步觀察可得：

一類特殊的情況

為了了解該算法是如何工作的，接下來我們将對一類特殊的情況進行思考。在這種情況下可以将 ϕ 通過 t 個比特進行表示：

ϕ = 0.ϕ1ϕ2ϕ3 · · · ϕt

那麼可以将式 (2.28) 改寫為：

此外，通過式 (2.27) 和 (2.26) 可以得到：

通過上述關于特殊情況的讨論，讀者應該明白為什麼該算法是正确的。現在我們對一般

情況進行研究。令 0 ≤ b ≤ 2t 滿足 b/2t = 0.b1 · · · bt 是與 ϕ 最接近的 t 個比特且小于 ϕ，即：

我們将兩者之間的誤差記為 δ = ϕ − b/2^t。顯然 0 ≤ δ < 1/2^t。因為對于所有的 θ 都有|1 − e^iθ| ≤ 2，是以

。因為：

(1)

(2)

是以：

假設測量的最終結果為 m，那麼對于任意的正整數 d，我們有：

如果我們想逼近 ϕ 的值，使其精确度達到 2^−n 并使成功的機率至少為 1 − ε，那麼隻需要選取

且要求

即可。由此可得：

且我們在相位估計算法中可以使用 t = T 個量子比特。

将上述推導與式 (2.27) 和命題 2.3.2 相結合，我們可以得出如下結論：圖 2.4 描述的算法可以使用

個量子比特，以 1 − ε 的成功機率在 O(t2) 步之内計算出 ϕ 的 n 比特近似值。

相位估計算法是許多量子算法的重要組成部分，比如著名的 Shor 算法 [204] 和求解線性方程組的 Harrow-Hassidim-Lloyd 算法 [112]。這兩種算法的詳細讨論超出了本書的範圍。

2.4 文獻注解

• 量子力學：2.1 節介紹的量子力學的相關材料都是标準内容，這些内容在任何量子力學教材中都可以找到。
• 量子線路：2.2 節的部分内容是基于文獻 [34] 和 [174] 一書的第 4 章編寫的。2.2.4 節介紹的量子多路複用器的概念是由 Shende 等人 [201] 提出的。量子門和量子線路的符号以及練習 2.2.7 中包含測量的量子線路的概念源于文獻 [226]。2.2 節僅僅是對量子線路基礎知識的簡介。自從文獻 [34] 發表以來，量子線路已經發展為更廣闊的研究領域。特别地，近幾年關于量子線路的研究，包括合成（大型幺正矩陣的分解）和優化量子線路，以及在量子程式設計語言的編譯中的應用，都變得炙手可熱；8.2 節關于未來研究方向的讨論中也提到了這一點。需要注意，對量子線路的合成和優化比經典電路中的類似問題要複雜得多。
• 量子算法：2.3.1∼2.3.3 節、2.3.6 節和 2.3.7 節介紹的内容很大程度上是基于 [174] 一書的第 4 章的内容設計的。文獻 [9] 和 [19] 分别對一維量子遊走和圖上的量子遊走進行了定義。2.3.5 節介紹的算法是由 Shenvi 等人 [203] 提出的。自從 Shor 算法和 Grover 算法被設計出來之後，量子算法已經成為量子計算領域中最火熱的研究領域之一。[174] 一書是對早期最主要的三種量子算法（Shor 算法、Grover算法和量子模拟 [154]）以及它們的各種變形介紹最詳細的資料之一。Shor [205] 針對“為什麼設計出來的量子算法這麼少”這一問題提出了兩種解釋，并指出可能發現新型量子算法的幾種研究思路。過去十年中，有大量關于量子遊走和基于量子遊走的量子算法的論文被發表，參見文獻 [18,192,214]。量子算法方面最近取得的突破性進展是設計出了可以求解線性方程組的 Harrow-Hassidim-Lloyd 算法 [112]。這導緻了在過去幾年中，關于量子機器學習算法 [156-157,184] 的研究變得非常火熱；文獻 [2] 對這類研究進行了一些有趣的讨論。