第二章 预备知识
本章将对全书使用的量子力学和量子计算的基本概念与符号进行介绍。
当然，量子编程理论是基于量子力学构建的。所以，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><i|。例子 2.1.5 就是这种类型的测量。
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 章中找到相关内容。
让我们看看量子线路 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 令 
= p1, · · · , pm 和 
= 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] 对这类研究进行了一些有趣的讨论。
