量子计算的研究始于 20 世纪 80 年代。1982 年，Benio. 和 Feynman 
最早提出了量子计算的概念。Feynman 指出，用经典计算机模拟量子力 
学系统存在本质的困难，当量子系统规模较大时，所需的计算代价将会呈 
指数级上升，即对 n 个量子粒子（例如二能级原子）系统的经典模拟需要 
存储 2n 个复振幅。因此，需要以指数大小存储这些信息。进一步地，他 
提出构造基于量子力学原理的计算机以克服这些困难，利用量子计算机 
使用 n 量子比特就可以自然地表示这些振幅。 
1985 年，Deutsch 给出了第一个量子计算模型，一个在一台经典计 
算机上需要两次查询才能解决的黑盒问题，在量子计算机上仅用一次 
量子查询就可以解决。一系列相关的结果（Deutsch-Jozsa 算法，1992 
年；Bernstein-Vazirani 算法，1997 年）给出了经典查询和量子查询复 
杂性之间显著的差别。最终，Simon（1997 年）的一个例子提供了一个 
指数级加速。正是以这些工作为基础，才诞生了后面两个重要的量子算 
法||Shor 大数因子分解算法和 Grover 搜索算法。从此，量子优势也日益 
凸显，量子计算迅速引起全世界学者的关注，它利用量子系统所特有的叠 
加性、相干性和纠缠性，通过设计相关算法可以实现大规模并行计算，相 
对于经典计算，量子计算在信息存储、执行速度等方面可以实现本质上的 
超越。
此外，量子算法的一个相关技术是绝热演化。量子绝热理论保证了基 
态下的量子系统在哈密顿量改变时将保持接近基态，前提是这种变化足 
够慢，这取决于哈密顿量的光谱特性。绝热演化可以用于解决优化问题以 
及模拟通用量子计算机。量子近似优化算法（QAOA）正是基于绝热理论 
解决优化问题的一类主要算法。 
本章主要介绍几种基本的量子算法：Deutsch-Jozsa 算法、Simon 算 
法、Bernstein-Vazirani 算法和 QAOA 算法。 
5.1 Deutsch-Jozsa 算法 
5.1.1 量子并行性 
量子并行性是许多量子算法的基本特征之一，量子计算的并行性不
79 
同于经典计算的并行性，量子并行性使量子计算机可以同时计算函数 f(x) 在许多不同 x 
处的值。 
设 f(x) : f0; 1g ! f0; 1g 是具有单比特定义域和值域的函数，在量子计算机上，计算 
该函数的一个简单方法是：考虑初态为 jxijyi 的双量子比特计算机，通过适当的逻辑门 
序列可以把这个状态转换为 jxijy .f(x)i，其中 . 为模 2 加法。通常，量子比特的集合称 
为量子寄存器，简称寄存器。在这里，第一个寄存器 jxi 称为数据寄存器，第二个寄存器 
jyi 称为目标寄存器，映射 jxijyi .! jxijy . f(x)i 称为 Uf，且 Uf 为酉的。若 jyi = j0i， 
则第二个量子比特的最终状态为 f(x)。输入 jxijyi 映射为输出 jxijy . f(x)i 的量子线路 
如图 5.1 所示。 
图 5.1 同时计算 f(0) 和 f(1) 的量子线路 
在图 5.1 中，实现了 jxijyi .! jxijy.f(x)i。数据寄存器 jxi 输入的是叠加态 j0i + p2j1i
， 
再应用 Uf，即 
j0ip+2j1ij0i 
Uf .! j0ij0 . f(0)ip+2j1ij0 . f(1)i 
(5.1.1) 
由于 j0 . f(0)i = jf(0)i，且 j0 . f(1)i = jf(1)i，故得到状态 
j0ijf(0)ip+2j1ijf(1)i 
(5.1.2) 
其中，式 (5.1.2) 中不同的项同时包含 f(0) 和 f(1)，看起来似乎对 x 的两个值计算了 
f(x)。经典计算的并行是多重 f(x) 电路同时进行，而这里利用了量子计算机处于不同状 
态的叠加能力，因此单个 f(x) 线路就可以同时计算多个 x 的值。 
利用 Hadamard 变换（H 门），如图 5.2 所示，可以将这个过程推广到任意数目量子 
比特上的函数计算，该变换是把 n 个 Hadamard 门同时分别应用到 n 量子比特上。例如， 
当 n = 2 时，初态全为 j0i 的情况如下所示。 
j0ij0i H-2 
.! μj0ip+2j1i.μj0ip+2j1i.= j00i + j01i + j10i + j11i 
2 
(5.1.3) 
其中，H-2 表示两个 Hadamard 门的并行作用。 
图 5.2 双量子比特上的 Hadamard 变换 
更一般地，n 量子比特上的 Hadamard 变换从全 0 出发，即 
j0i-n H-n 
.! μj0ip+2j1i.-n 
(5.1.4)
80 
得到状态 
1 
p2nXx 
jxi (5.1.5) 
其中，求和是对 x 的所有可能取值且 x 的长度为 n，并用 H-n 表示这个作用。可以看 
到，Hadamard 变换产生了所有基态的平均叠加 3所有状态的概率幅全为 
1 
p2n ′，仅用 n 
个 H 门就可以产生 2n 个状态的叠加。 
对于单比特输入和单比特输出，可以采用下述方法将其扩展为 n 比特输入 x 和单比 
特输出 f(x)，从而实现函数 f(x) 对多个 x 的并行计算。为了制备 n+1 量子比特的状态 
j0i-nj0i，对前 n 位应用 Hadamard 变换，并连接实现 Uf 的量子线路，这样就产生了状 
态 
1 
p2nXx 
jxijf(x)i (5.1.6) 
例如，当 n = 3 时，为了制备 4 量子比特的状态 j0i-3j0i，对前 3 量子比特同时应用 
Hadamard 变换，得到数据寄存器 x 中的状态为 
1 
p23 
(j000i + j001i + j010i + j011i + j100i + j101i + j110i + j111i) (5.1.7) 
再连接实现 Uf 的量子线路，产生状态 
1 
p23 
(j000ijf(000)i + j001ijf(001)i + j010ijf(010)i + j011ijf(011)i + j100ijf(100)i 
+j101ijf(101)i + j110ijf(110)i + j111ijf(111)i) (5.1.8) 
在某种意义下，在表面上似乎只进行一次 f(x) 计算，量子并行性却使得 f(x) 的所 
有可能值同时被计算出来。一般而言，由于对量子态的测量会使量子状态发生坍缩现象， 
因此测量状态Xx 
jxijf(x)i也类似地只给出了某一个 x 的 f(x) 值，显然利用经典计算就 
能做到这一点。为了真正地从量子并行性中获得好处，不仅仅在于能够获得一个 f(x) 的 
值，更为重要的是，能够得到比从一个叠加态 j0i + p2j1i
中获得一个 f(x) 值更有价值的信 
息抽取能力，下面介绍的 Deutsch 算法就是这种能力的具体表现。 
5.1.2 Deutsch 算法简介 
Deutsch 算法是基于量子并行性和量子力学中的干涉性质结合起来实现的，显示了 
量子相干性的强大计算能力。考虑一个黑箱（Oracle），它可以计算一比特的函数 f(x) : 
f0; 1g ! f0; 1g，每做一次计算，我们称对黑箱做一次查询。 
存在 4 个这样的函数， 
f1(x) = x; f2(x) = x; f3(x) = 0; f4(x) = 1 (5.1.9) 
其中，x 2 f0; 1g，x 是 x 的逻辑非。对于 f1(x)、f2(x)，称它们为平衡的；对于 f3(x)、f4(x)， 
称它们为常数的。所要解决的问题是：如何用一次计算确定未知的函数 f(x) 是常数的还
81 
是平衡的？要得到该问题的答案，经典计算机需要对黑箱做两次查询，而量子算法只需要 
一次。Deutsch 算法的量子线路如图 5.3 所示。 
图 5.3 实现 Deutsch 算法的量子线路 
由图 5.3 可知，Deutsch 算法利用 Hadamard 门把第 1 量子比特 j0i 制备为叠加态 
j0ip+2j1i
，同样地，把 Hadamard 门应用到辅助量子比特 j1i 上制备叠加态 j0ip.2j1i
。 
Deutsch 量子算法的步骤如下所述。 
算法 5.1 Deutsch 算法 
（1）输入状态 j'0i = j01i。 
（2）j'0i 通过两个 Hadamard 门后，输出状态为 
j'1i = μj0ip+2j1i.μj0ip.2j1i. (5.1.10) 
（3）容易看出，对于每个 x 2 f0; 1g，如果把 jxi 
1 
p2
(j0i . j1i) 作为 Uf 的输入，就可 
以得到 Uf 的输出状态为 (.1)f(x)jxi 
1 
p2
(j0i . j1i)，即 
Uf jxi 
1 
p2
(j0i . j1i) = (.1)f(x)jxi 
1 
p2
(j0i . j1i) (5.1.11) 
于是，把 j'1i 作为 Uf 的输入，即 
Uf μj0ip+2j1i.μj0ip.2j1i.= 
1 
p2
(.1)f(0)j0ij0ip.2j1i 
+ 
1 
p2
(.1)f(1)j1ij0ip.2j1i 
(5.1.12) 
就得到了两种可能的 Uf 输出，即 
j'2i = 8>
>><>
>>: 
§μj0ip+2j1i.μj0ip.2j1i.; f(0) = f(1) 
§μj0ip.2j1i.μj0ip.2j1i.; f(0) 6= f(1) 
(5.1.13) 
（4）第 1 量子比特再通过 Hadamard 门，输出变为 
j'3i = 8>
>><>
>>: 
§j0iμj0ip.2j1i.; f(0) = f(1) 
§j1iμj0ip.2j1i.; f(0) 6= f(1) 
(5.1.14) 
如果 f(0) = f(1)，那么 f(0) . f(1) = 0；如果 f(0) 6= f(1)，那么 f(0) . f(1) = 1。因此， 
可将上述结果改写成 
j'3i = §jf(0) . f(1)iμj0ip.2j1i. (5.1.15)
82 
（5）测量第 1 量子比特，就可以确定 f(0) . f(1) 的值。 
于是，如果函数是常数的，对于第 1 量子的测量就会百分之百地得到 0；而如果函数 
是平衡的，那么测量结果肯定是 1。因此，应用量子线路只对函数 f(x) 一次计算的情况 
下，就可以确定 f(x) 是常数的还是平衡的全局性质。完成上述过程的经典计算机至少需 
要两次计算，而量子计算只需要一次。 
上述 Deutsch 量子算法的量子并行性显而易见，它体现了很多量子算法设计的本质 
特征，即通过精心选择函数和最终变换，从而有效地确定有关函数的有用全局信息，而这 
在经典计算机上是无法快速得到上述结果的。 
5.1.3 Deutsch-Jozsa 算法简介 
对于一个或为常数的或为平衡的 n 比特二进制函数 f : f0; 1gn ! f0; 1g，确定它为 
常数的还是平衡的问题可以描述为 Alice 从 0 到 2n . 1 的数中选一个数 x，以书信的形 
式把 x 寄给 Bob。Bob 收到信后，根据信中 x 的值计算 f(x) 的值，然后以书信的形式 
把 f(x) 的值寄回给 Alice。Bob 使用的函数只有两种类型，即对于所有的 x，f(x) 要么 
是常数的，要么是平衡的。若 f(x) 是平衡的，也就是说，恰好所有可能 x 值的一半使得 
函数值为 1，另一半使得函数值为 0。Alice 的目的是要用尽可能少的通信确定 Bob 所用 
的函数 f(x) 是平衡的还是常数的。在经典算法的情况下，Alice 的一封信只能发给 Bob 
一个 x 值，在最坏的情况下，Alice 要问 Bob 至少 2n=2 + 1 次才能确定函数的类型，而 
Deutsch-Jozsa 算法只需要通过对黑箱（Oracle）做一次询问就可以解决这个问题，其量子 
线路与 Deutsch 算法的量子线路类似，如图 5.4 所示。 
图 5.4 实现 Deutsch-Jozsa 算法的量子线路 
在图 5.4 中，带有“/”的直线表示通过此直线的是一组 n 量子比特，Hadamard 门 
被并行地作用到 n 量子比特上，即 
H-n = H - H - H - ￠ ￠ ￠ - H (5.1.16) 
下面观察线路中的状态变化。输入状态为 
j'0i = j0i-nj1i (5.1.17) 
j'0i 在通过 Hadamard 门，得到 
j'1i = X x2f0;1gn 
pjx2in μj0ip.2j1i. (5.1.18) 
接下来，使用 Uf : jxijyi ! jxijy . f(x)i 计算函数 f(x), 得到 
j'2i =Xx 
(.1)f(x)pjx2in μj0ip.2j1i. (5.1.19)
83 
当 x = 0 或 x = 1 时，我们知道，对单量子比特 jxi 有 
Hjxi = X z2f0;1g
(.1)xzjzi=p2 (5.1.20) 
于是，对输入 n 量子比特 jxi = jx0; x1; ￠ ￠ ￠; xn.1i 有 
H-njxi = H-njx0; x1; ￠ ￠ ￠ ; xn.1i 
= X z0￠￠￠zn.1
(.1)x0z0.x1z1.x2z2.￠￠￠.xn.1zn.1 jz0; z1; ￠ ￠ ￠ ; zn.1i 
p2n 
(5.1.21) 
上式可以写成更加紧凑的形式，即
H-njxi = Xz 
(.1)x￠zjzi 
p2n 
(5.1.22) 
其中，x ￠ z 表示对 x 和 z 取模 2 的内积，即 
x ￠ z = x0z0 . x1z1 . x2z2 . ￠ ￠ ￠ . xn.1zn.1 (5.1.23) 
因此，我们可以利用式 (5.1.22) 对 j'2i 的前 n 个量子比特应用并行的 Hadamard 门， 
得到 
j'3i =Xz Xx 
(.1)x￠z+f(x)jzi 
2n μj0i . p2j1i. (5.1.24) 
对于该输出态 j'3i，在计算基上测量这 n 个量子比特，如果 f 为常数的，则测量以 100% 的 
概率得到状态 j000 ￠ ￠ ￠ 0i；如果 f 是平衡的，那么测量到这个态的概率为 0。Deutsch-Jozsa 
算法可总结如下。 
算法 5.2 Deutsch-Jozsa 算法 
输入 对 x 2 f0; 1; ￠ ￠ ￠ ; 2n . 1g 和 f(x) 2 f0; 1g 进行变换 jxijyi ! jxijy . f(x)i 的 
Uf，已知对所有的 x 而言，f(x) 是常数的或者平衡的。 
输出 当且仅当 f(x) 是常数的，输出为 0。 
运行时间 计算 Uf 一次，总是成功的。 
过程 
（1）初始化状态：j0i-nj1i。 
（2）使用并行的 Hadamard 门产生叠加态： 
1 
p2n 
2n.1 Xx=0 
jxiμj0ip.2j1i.。 
（3）使用 Uf 计算 f(x) : 
1 
p2nXx 
(.1)f(x)jxiμj0ip.2j1i.。 
（4）进行 Hadamard 变换：Xz Xx 
(.1)x￠z+f(x)jzi 
2n μj0ip.2j1i.。 
（5）测量最终输出 z。
84 
因此，运行一次 Deutsch-Jozsa 算法，对函数 f(x) 仅查询一次就可以确定 f(x) 是常 
数的还是平衡的。但是在经典计算机上，只有经过 2n.1 + 1 次查询之后才可以确定函数 
f(x) 是否是常数的。但是，对于 Deutsch-Jozsa 算法有几点需要注意。首先，Deutsch 问 
题不是一个具有实质重要性的问题，它没有已知的应用；其次，在某种角度上，经典算法 
和量子算法很难相互比较，因为计算函数值的方法差别很大；最后，如果选择概率经典计 
算机，随机选择一些 x 值计算函数 f(x) 的值，则也可以以非常高的概率确定 f(x) 是常 
数的还是平衡的，这种概率模型比我们考虑的确定性模型或许更加现实。 
5.2 Simon 算法 
给定一个映射 f : Zn2 
! Zm2
，其中 n > m，存在一个 s 2 Zn2
对所有的 x; x0 2 Zn2
， 
满足性质 f(x) = f (x0) 的充分必要条件是 x = x0 或 x . x0 = s，其中 . 表示模 2 加 
法。Simon 算法通过一系列量子计算步骤可以求出满足上述条件的 s。该问题的经典算 
法复杂度是指数级的，而 Simon 算法可以在多项式时间内求解，这说明了对于特定问题， 
量子算法比经典算法更快。Simon 算法的量子线路如图 5.5 所示。 
图 5.5 Simon 算法的量子线路 
Simon 算法的步骤描述如下。 
算法 5.3 Simon 算法 
（1）首先将两个量子寄存器初始化为 j0nij0mi。 
（2）对第一个量子寄存器中的每一个量子比特执行 H 门变换，得到量子态 
1 
p2n 
2n.1 Xi=0 
jiij0mi 
（3）对量子态 
1 
p2n 
2n.1 Xi=0 
jiij0mi 作酉变换 Uf，得到量子态 
1 
p2n 
2n.1 Xi=0 
jiijf(i)i。 
（4）测量第二个量子寄存器，假设测量结果为 y，则原来的量子态发生坍缩，坍缩后 
的量子态为 
1 
p2
(jxijyi + jx . sijyi)，其中 y = f(x) = f(x . s)。 
（5）对第一个量子寄存器中的每个量子比特执行 H 门变换，得到量子态 
H-n μ 1 
p2jxi + 
1 
p2jx . si.= 
1 
p2Xj 
(.1)x￠j 
2n=2 jji + 
1 
p2Xj 
(.1)(x.s)￠j 
2n=2 jji 
=Xj 
(.1)x￠j + (.1)(x.s)￠j 
2(n+1)=2 jji 
=Xj 
(1 + (.1)s￠j)(.1)x￠j 
2(n+1)=2 jji (5.2.1)
85 
其中，x ￠ j = xn.1jn.1 . xn.2jn.2 . ￠ ￠ ￠ . x0j0，s ￠ j 的定义类似。如果 s ￠ j = 0，则量子 
态 jji 的概率幅等于 
(.1)x￠j 
2(n.1)=2 
。反之，如果 s ￠ j = 1，则量子态 jji 的概率幅等于 0。所以 
第一个量子寄存器中的量子态为Xj0 
jj0i，其中每一个 jj0i 均满足 s ￠ j0 = 0。 
（6）对第一个寄存器进行测量，测量的结果 j1 一定满足 s ￠ j1 = 0。 
（7）重复步骤（1）.（6）O(n) 次后，得到一组线性无关的向量组 j1; j2; ￠ ￠ ￠ jn。建立 
二元域上的线性方程组，由于向量组线性无关，因此方程组的解存在，我们可以通过求解 
线性方程组得到 s。 
下面简单分析 Simon 算法的计算复杂度。Simon 算法有两个量子寄存器，第一个量 
子寄存器的位数是 n，第二个量子寄存器的位数是 m，其中 n 6 m，因此量子算法的空间 
复杂度是 O(m)。对第一个量子寄存器的每一位量子比特做 H 门变换，然后对两个量子寄 
存器作一次酉变换，再对第一个量子寄存器的每一位量子比特作 H 门变换，之后再测量 
两个量子寄存器，因此查询复杂度是 O(n)，而且要重复计算 O(n) 次，因此 Simon 算法的 
总查询复杂度是 O(n2)。对第一个量子寄存器的每一个量子比特作 H 门变换可以同时进 
行，因此重复 O(n) 次计算后的总时间复杂度是 O(n)，且算法的成功概率是 O(1)。Simon 
算法的一个重要意义在于它启发了 Shor 算法。 
5.3 Bernstein-Vazirani 算法 
我们已经介绍过 Deutsch-Jozsa 量子算法，它仅需要运行一次就可以辨别给定函数是 
常数的还是平衡的，而经典算法则需要运行 O(N = 2n) 次才能实现该目的。Bernstein 和 
Vazirani 运用 Deutsch-Jozsa 算法有效地解决了访问量子数据库的问题。问题具体可以描 
述为
给定黑箱可以计算的布尔函数 fs : f0; 1gn ! f0; 1g，即 
fs(x) = s ￠ x; (5.3.1) 
其中，s 2 f0; 1gn 是一个未知的向量，也称隐藏字符串，s ￠ x = s1x1 . s2x2 . ￠ ￠ ￠ . snxn。 
我们需要找到隐藏字符串 s 的具体值。 
如果运行经典算法，则需要调用黑箱 n 次以确定 s 的 n 位数值，算法的查询复杂度 
为 O(n)。事实上，由 fs(10 ￠ ￠ ￠ 0) = s1; fs(01 ￠ ￠ ￠ 0) = s2; ￠ ￠ ￠ ; fs(00 ￠ ￠ ￠ 1) = sn 共 n 次黑箱 
调用可以确定 s = (s1; s2; ￠ ￠ ￠ ; sn)。然而运行 Bernstein-Vazirani 量子算法仅需要调用黑 
箱一次就可以决定 s。Bernstein-Vazirani 算法的线路图与图 5.4 类似，只需要将函数 f 替 
换为 fs 即可。Bernstein-Vazirani 算法的步骤描述如下。 
算法 5.4 Bernstein-Vazirani 算法 
（1）两个寄存器的初始状态为 j0nij0i。 
（2）对第二个寄存器的量子比特执行 X 门操作，系统状态转化为 j0nij1i。
86 
（3）对两个寄存器的每个量子比特执行 H 门操作，系统状态转化为 
. 1 
2n=2Xx 
jxi!μj0i . p2j1i. 
（4）对两个寄存器的量子比特执行酉变换 Uf，得到量子态 
. 1 
2n=2Xx 
(.1)s￠xjxi!μj0ip.2j1i. 
（5）对第一个寄存器执行 H-n 操作，系统演化为 
. 1 
2nXx 
(.1)s￠xXy 
(.1)x￠yjyi!μj0ip.2j1i.=. 1 
2nXx Xy 
(.1)(s.y)￠xjyi!μj0ip.2j1i. 
=jsiμj0ip.2j1i. (5.3.2) 
（6）测量第一个寄存器将以 100% 的概率得到 s 的值。 
5.4 QAOA 算法 
量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是由 
Farhi，Goldstone 和 Gutmann 于 2014 年提出的多项式时间算法，用来近似求解组合优 
化问题。一般来说，组合优化是从有限数量的对象中寻找使成本函数最小化的目标。组 
合优化在包括降低供应链成本、车辆路径、作业分配等实际问题中得到了广泛应用。现 
实中，很多组合优化问题都是 NP- 难的问题，不存在多项式时间的经典算法精确求解。 
往往在实际生活中，有些问题没有必要找到完美精确解，找到一个符合期望的近似解就 
足够了。于是遗传算法、退火算法和神经网络等近似优化算法（AOA）被提出用于多项式 
时间求解次优解，而量子优化算法（QAOA）的价值在于展示量子优越性。 
QAOA 算法的一个重要应用就是最大切割问题（MAX-CUT）。给定一个由顶点 i 2 
V (顶点也常称为结点) 和边 (i; j) 2 E 构成的无向图 G，求解最大切割问题就是要得到 
两个子集 S0 和 S1，使得 S0 [ S1 = V ，S0 \ S1 = ?，且图 G 中 i 2 S0 和 j 2 S1 的边 
(i; j) 的数量尽可能地多。简单来说就是将图中的顶点分成两组，使得连接这两组中顶点 
的边的数目最多。两顶点杠铃图如图 5.6 所示。 
图 5.6 杠铃图 
两顶点杠铃图共有 4 种方法二分顶点。我们把集合 S0 或 S1 中的顶点表示为 0 或 
1，形成一个长度为 n 的比特串。4 种划分可以表示成 f00; 01; 10; 11g，如图 5.7 所示。其 
中从左往右数第 1 个比特对应的结点为 v1，第 2 比特对应的结点为 v2，图中是以量子比 
特的形式展现的。只有存在连接不同集合中的顶点时才绘制边，中间的符号 X 表示需要
87 
切割的边。于是，直观上可以看到杠铃图存在两种相同的最大切割，即图 5.7 中的第 2 个 
和第 3 个分组。更一般地，任意一个 n 顶点的图，其划分的情形总数是 2n。对于顶点数 
目较少的情况，能够通过枚举法找到最大切割问题的最优解。然而，一旦顶点数目增加到 
足够大时，相应的计算时间复杂度也将呈指数级增加，就会形成 NP-难的问题。 
图 5.7 杠铃图的划分情况 
接下来，我们将展示如何利用量子近似优化算法（QAOA）求解最大切割问题。出发 
点是将最大切割的比特串视为编码代价函数的哈密顿量的基态。首先需要引入哈密顿量， 
哈密顿量用来描述物理系统，以矩阵形式表示，该矩阵的特征值均为实数。哈密顿量的本 
征向量表示相应物理系统所处的各个本征态，而本征值表示相应本征态对应的能量。对 
于最大切割问题的哈密顿量形式，可以通过构造经典函数返回值确定。具体来说，如果 
图 G 中任意一条边所对应的两个结点跨越不同集合，那么返回 1（裁剪的边数或边的权 
重），否则返回 0。更严格的数学定义为 
Cij = 
1
2 
(1 . zizj) (5.4.1) 
其中，如果顶点 i 属于集合 S0，则 zi 的值为 +1，否则 zi 的值为 .1。于是，图 G 的最 
大切割值等于各条边切割贡献之和，即 
MAX-CUT =Xij 
Cij (5.4.2) 
就杠铃图而言，存在 4 个分组，把它看成一个系统的 4 个孤立状态 j00i、j01i、j10i、j11i， 
每种划分对应的切割值可以看成是系统处于该状态时的能量。因此，杠铃图系统处于 j00i 
态的能量为 0，处于 j01i 态的能量为 1，处于 j10i 态的能量为 1，处于 j11i 态的能量为 
0。杠铃图的哈密顿量的矩阵形式表达为 
H =266664 
0 0 0 0 
0 1 0 0 
0 0 1 0 
0 0 0 0
377775
= I . .z
1.z
2 
2 
(5.4.3) 
其中，.z
1 表示对第 1 个量子比特位作用 Pauli Z 矩阵，对其余量子比特位作用单位矩阵， 
即 .z
1 = .z -I，类似地，.z
2 = I -.z。推广到更复杂的最大切割系统，由于其切割值为所 
包含的杠铃图系统切割值之和，所以对应于该复杂系统的哈密顿量表示为 
H = X (i;j)2E 
I . .z
i .z
j 
2 
(5.4.4)