2012年1月26日星期四

经典和量子的"冒牌排序"

计算机科学中有一个近乎玩笑的排序算法称为"冒牌排序" (bogosort), 又叫作"猴子排序" (Monkey Sort). 这个算法被称为"典型的糟糕算法". 实现它的步骤是:
第一步: 检查数组是否有序;
如果有序返回结果;
如果乱序:
第二步: 随机排列该数组, 返回第一步.
"冒牌排序"等价于把一堆扑克随机洗牌, 然后检视是否有序. 如果无序, 则继续重复下去. 可想而知, 这个算法的效率是极其低下的. 它的平均时间复杂度为$O(n \cdot n!)$. 相对比之下, 常用的快速排序平均只需要 $O(n \cdot \log n)$ 次操作.

有个调侃量子计算机的笑话, 说利用冒牌排序可以在 $O(n)$ 次操作中完成排序. 原理如下:
第一步: 利用量子计算机将数组随机排列. 根据量子力学的多世界诠释, 每一种可能的排列都会出现在某一个宇宙中.
第二步: 检查每一个宇宙中的数组是否有序. 在每个宇宙中, 这需要 $n-1$ 次操作.
第三步: 摧毁仍然乱序的宇宙. 唯一的幸存者只看到过 $n-1$ 次操作.
算法第三步的实现交给读者作为练习.

当然实际上这个算法的第三步是不可能实现的 (假定多世界诠释是对的, 并且这个数组是量子数组). 因为首先每次测量将会使观察者选择某一个具体的世界, 量子数组亦将选择某一种排列方式. 观察者当然不可能再跳出这个宇宙 (即使摧毁这个宇宙, 因为观察者是宇宙的一部分), 更不用说摧毁其他宇宙.

2012年1月10日星期二

爱因斯坦的 $c$

Philip Gibbs 在他的 vixra blog 发文章解释相对论中广泛应用符号 $c$ 代表真空光速. 他指出, 实原本1905年9月26号发表在Annalen der Physik 322 (10): 891–921上"论动体的电动力学"中, 爱因斯坦是使用 $V$ 作为真空光速的; 但在1907年, 他忽然切换到 $c$ [1]. Gibbs 指出并分析了下面几个来源:

1. $c$ 代表拉丁文速度 celeritas. 这是Issac Asimov首先在科幻杂志上指出的 [2]. 尽管在历史上曾出现过用$c$表示速度的文章, 但并没有直接证据表明这就是 $c$ 真正的来源.

2. $c$ 代表波速, 是欧拉首先在2维波动方程中引入的 [3]. 欧拉习惯上使用相邻的符号, 比如 $a, b, c$; $x, y, z$; $p, q, r$. 这影响了数代数学家. 在欧拉发展2维波动方程时, 他使用了 $a, b$ 作为其他常数, 因此很自然地使用 $c$ 作为下一个他遇到的常数, 波速.

3. $c$ 代表英文常数constant. 这是1856 由Weber 和 Kohlrausch 首先引入在电磁学中的 [4]. 他们导出一个具有速度量纲的常数, 并用 $c$ 表示. 代表了电力和磁力的相对大小. 在麦克斯韦理论中, 这被统一为光速.

--
[1]: 维基文献保存了爱因斯坦的文章: http://en.wikisource.org/wiki/On_the_Electrodynamics_of_Moving_Bodies
费米实验室搜集的爱因斯坦奇迹年文章 (此中使用 $c$, 但在脚注中说明是由英译本更改的):
http://www.fourmilab.ch/etexts/einstein/specrel/www/
1907 年:
A. Einstein, “On the Relativity Principle and the Conclusions Drawn From It”, Jahrbuch der Radioaktivität und Elektronik 4, pgs 411—462 (1907)

[2]: Isaac Asimov “C for Celeritas” in “The Magazine of Fantasy and Science Fiction”, Nov-59 (1959), reprinted in “Of Time, Space, and Other Things”, Discus (1975), and “Asimov On Physics”, Doubleday (1976)

[3]: L. Euler, “Eclaircissemens Plus Detailles Sur La Generation et La Propagation Du Son Et Sur La Formation De L’Echo”, “Memoires de l’acadamie des sciences de Berlin” [21] (1765), 1767, pgs 335—363 in “Opera physica miscellanea epistolae. Volumen primum”, pg 540

[4]: R. Kohlrausch and W.E. Weber, “Ueber die Elektricitätsmenge, welche bei galvanischen Strömen durch den Querschnitt der Kette fliesst”, Annalen der Physik, 99, pg 10 (1856)

2012年1月6日星期五

物理学家加入数学盛宴

有一个古老的数学命题说,
宴会定理: 在一场不少于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)