有一个古老的数学命题说,
当参加宴会的人数为5时, 上述命题不再成立. 图二给出了一个反例. 宴会人数大于6, 我们只要考察其中任意6个人之间的关系, 即可知命题成立. 因此, 可以得出这样的结论: 要使宴会命题成立, 宴会的人数有一个下限. 这个下限, 在数学上被称为Ramsey数, 以纪念英年早夭的英国数学家F. P. Ramsey (1903 - 1930, 去世时年方26岁).
Ramsey考虑了这个问题的推广. 比如要使宴会中的一定存在四个人两两相识或陌生, 宴会人数的下限是否存在, 如果存在, 是多少? 五个人, 六个人, 乃至多人的情形将如何? 甚至, 对于相识和陌生人数不等的情形又如何? 1930年, 他最终能够证明这样的下限对任意情况都是存在的. 这样一个定理如今以他命名, 被称为Ramsey定理, 大意如下:
Ramsey证明了Ramsey数对于任意正整数 $ s $ 和 $ t $ 都存在, 却没有给出它的算法. 事实上, $R(s, t)$ 的计算是困扰数学家的难题之一. 迄今为止, $s > 3, t > 3$ 的Ramsey数人们仅仅知道9个, 其他的数人们仅知道他们的大致范围 [1]. 使用穷举方法, 对于有 $n$ 个人参加的宴会, 共有$2^{(n-1)n/2}$ 种情形. 譬如, 已知 $R(5, 5)$ 在 $43 - 49$ 之间. 为了验证 $R(5, 5) = 43$ 是否成立, 需要穷举 $2^{903}$ 种情形. 使用2 GHz的计算机 (每秒计算 $2^{10}$ 次), 仍需 $10^{261}$ 年. 对比之下, 宇宙的年龄才 $10^{11}$ 年.
为了说明Ramsey数的计算复杂度, 匈牙利著名数学家Paul Erdos(1913 - 1996)曾讲过一个故事 [2].
现在物理学家正在加入这场盛宴. 美国物理学家Frank Gaitan和Lane Clark提出, Erdos和其他数学家不必对计算Ramsey数的复杂性感到悲观. 因为未来量子计算机也许可以解决这个问题 [5]. 据APS Physics报道, 他们提出了一种可以计算Ramsey数的量子算法 [4]. 在这种算法中, 他们引入了一个 Hamilton量, 其态空间包含了所有图的构型. 同时当图的顶点的个数小于Ramsey数时, 此Hamilton量的基态能量为零. 否则基态能量不为零. 他们首先使用一个易于获得的含时Hamilton量, 然后绝热地演化到前述Hamilton量, 最后再测量此时的基态能量. 需要注意的是, 由于量子力学的特性, 量子计算给出的结果是随机性的. 只能够通过多次测量, 以较高的概率确定Ramsey数的值.
宴会定理: 在一场不少于6个人宴会中, 一定存在三个人, 他们之间要么彼此相识, 要么彼此不相识.图一用图形表示了宴会定理情形之一.
 |
| 图 一: 用图表示的六人宴会. 其中使用图的顶点作为与会人士, 蓝色的边表示陌生, 红色的边表示相识. 宴会定理断言, 一定会存在一个单色(蓝色或红色)的三角形. 读者可以挑战这里的一个Java applet. |
当参加宴会的人数为5时, 上述命题不再成立. 图二给出了一个反例. 宴会人数大于6, 我们只要考察其中任意6个人之间的关系, 即可知命题成立. 因此, 可以得出这样的结论: 要使宴会命题成立, 宴会的人数有一个下限. 这个下限, 在数学上被称为Ramsey数, 以纪念英年早夭的英国数学家F. P. Ramsey (1903 - 1930, 去世时年方26岁).
 |
| 图 二: 一个顶点图使用双色染色但不存在单色三角形的例子. 图例同图一. |
Ramsey考虑了这个问题的推广. 比如要使宴会中的一定存在四个人两两相识或陌生, 宴会人数的下限是否存在, 如果存在, 是多少? 五个人, 六个人, 乃至多人的情形将如何? 甚至, 对于相识和陌生人数不等的情形又如何? 1930年, 他最终能够证明这样的下限对任意情况都是存在的. 这样一个定理如今以他命名, 被称为Ramsey定理, 大意如下:
对于任意正整数 $s$ 和 $t$, 存在一个正整数 $n$, 使得当一场宴会的人数不少于 $n$ 时, 其中一定存在要么$s$个人相识要么 $t$ 个人不相识的情况.这样的整数 $n$ 统称为Ramsey数, 记作 $R( s, t )$. 宴会定理是Ramsey定理的一个特例, 即 $ s = 3, t = 3$, 而 $R( 3, 3 ) = 6$.
Ramsey证明了Ramsey数对于任意正整数 $ s $ 和 $ t $ 都存在, 却没有给出它的算法. 事实上, $R(s, t)$ 的计算是困扰数学家的难题之一. 迄今为止, $s > 3, t > 3$ 的Ramsey数人们仅仅知道9个, 其他的数人们仅知道他们的大致范围 [1]. 使用穷举方法, 对于有 $n$ 个人参加的宴会, 共有$2^{(n-1)n/2}$ 种情形. 譬如, 已知 $R(5, 5)$ 在 $43 - 49$ 之间. 为了验证 $R(5, 5) = 43$ 是否成立, 需要穷举 $2^{903}$ 种情形. 使用2 GHz的计算机 (每秒计算 $2^{10}$ 次), 仍需 $10^{261}$ 年. 对比之下, 宇宙的年龄才 $10^{11}$ 年.
为了说明Ramsey数的计算复杂度, 匈牙利著名数学家Paul Erdos(1913 - 1996)曾讲过一个故事 [2].
假设有个比我们强大很多的外星人军团在地球登陆, 要求地球人给出 R(5, 5) 的准确值否则将会摧毁地球. 那么, 我们应该立刻集合所有数学家和所有计算机来找到它. 但假如他们要求的是 R(6, 6) 的值, 我们转而应当设法消灭强大的外星人.
现在物理学家正在加入这场盛宴. 美国物理学家Frank Gaitan和Lane Clark提出, Erdos和其他数学家不必对计算Ramsey数的复杂性感到悲观. 因为未来量子计算机也许可以解决这个问题 [5]. 据APS Physics报道, 他们提出了一种可以计算Ramsey数的量子算法 [4]. 在这种算法中, 他们引入了一个 Hamilton量, 其态空间包含了所有图的构型. 同时当图的顶点的个数小于Ramsey数时, 此Hamilton量的基态能量为零. 否则基态能量不为零. 他们首先使用一个易于获得的含时Hamilton量, 然后绝热地演化到前述Hamilton量, 最后再测量此时的基态能量. 需要注意的是, 由于量子力学的特性, 量子计算给出的结果是随机性的. 只能够通过多次测量, 以较高的概率确定Ramsey数的值.
由于量子算法可以使用普通计算机上来模拟, 尽管速度会非常慢, Gaitan和Clark使用他们的算法对较小的几个Ramsey数的值进行了模拟并与数学家给出的结果相符 (表 一).
 |
表 一: Gaitan & Clark使用他们的算法对小Ramsey数进行的模拟结果. |
Gaitan和Clark的算法, 给使用量子计算机解决数学和科学中的计算难题带来了新的希望. 人们已知, 对于某些能够在经典计算机(Universal Turing Machine)上快速验证(P), 但至今未找到算法快速解决的问题(NP), 可能能在量子计算机上快速解决(BQP). 整数分解质因数的 Shor算法提供了第一个这样的例子. 进一步, 量子计算机还可能快速解决某些甚至不能在经典计算机上快速验证的问题. Gaitan和Clark的算法有可能证明量子计算机的某些远超经典计算机的计算能力. 无论如何, 物理学家加入这场数学盛宴, 将给未来科学带来难以预计的震撼.
 |
| 图 三: 量子计算, 在计算复杂性中可能的位置. P 表示可以在多项式时间内解决的问题. NP表示, 可以在多项式时间内验证(证实)的问题. 类似的co-NP则是可以在多项式时间内证否的问题. NP-complete 或 NPC 是NP问题中最难的一类. PSPACE 是可以以多项式空间内, 以多项式时间解决的问题. BQP是量子计算机可以以多项式时间解决的问题. 在计算科学中, NP = P? 是个悬而未决的重大问题. 进一步, 人们问, P = PSPACE? 一般认为, NP != P. 而对量子计算来说, BQP则被认为包含P, 与NP有交集但不包含NP的全部 [3]. |
参考:
[1] Weisstein, Eric W. "Ramsey Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RamseyNumber.html
[2] L. Graham and Joel H. Spencer, in Scientific American (July 1990), p. 112-117
[3] http://en.wikipedia.org/wiki/Quantum_computer#Relation_to_computational_complexity_theory
[4] Synopsis: Quantum Search for Elusive Numbers
[5] Frank Gaitan and Lane Clark, Ramsey Numbers and Adiabatic Quantum Computing, PRL 108, 010501 (2012)
没有评论:
发表评论