D-wave的量子计算机不可能那么坑爹……吗?

这个本来也是发在果壳的日志上的,觉得还算适合就搬到这里来了,请注意仍然要遵守首页上的CC协议啊……

这几天炒得很热的,国内有自制蘑菇云,国外有D-wave的量子计算机。貌似果壳(和松鼠会资讯)也要做一做这个,我就先不泄漏什么,大家可以等着看。

不过嘛,既然要写这个日志,还是要讨论一下D-wave他们家的东西的。我本来想说简单介绍一下的,不过量子计算机这种东西太复杂了,简单介绍不一定容易明白,大家就将就一下吧……

话说大自然是不喜欢高能量的东西的,因为高能量往往意味着不大稳定。所以,随便一个物理体系,如果你不给它什么能量的话,它慢慢慢慢就会到达最低能量的状态,学名叫基态。

说到这里的话,学计算机的人可能就开始想到些什么了:这不就是解了一个最优化问题么?嗯,正是这样,自然就是不断在解各种各样的最优化问题。

这里无节操广告一下,关于自然解优化问题的一个例子,可以参考松鼠会的文章:http://songshuhui.net/archives/33649

言归正传,D-wave的Rainier芯片,也就是D-wave One里的芯片,其实就是干的这个活。芯片就是一个物理体系,它的能量依赖于一系列参数,还有它内部的128个量子位的0-1取值。它能优化的函数只能是关于这些量子位的一个二次函数,不过这个问题已经很不容易了。更精确地讲,这个叫QUBO(我希望没有记错)的问题是NP-hard的。如果能高速度解决它的话,那很多问题都可以迎刃而解。

对于一般的物理体系来说,能量的降低是通过热扰动来进行的。通过热扰动,物理体系可以以小概率“借到”足够的能量,跳出局部最优达到全局最优。不过问题是,要是局部最优“很深”,也就是说要借的能量很大才能跳出去的话,仅仅通过热扰动就需要非常长的时间。大概也是这个原因,一般也没人去用真实的物理系统去优化某个函数。当然,这种热扰动的物理直觉可以用来做优化问题的heuristic,这里就按下不表,大家可以期待《人算不如天算》这个系列的新文章,如果我还能写得出来的话……

好了,对于量子体系,它们有一种特殊的量子过程来干这个事情,那就是量子隧穿效应。它可以无视“借”能量的要求,直接就“穿越”过去了……好比从山这边到山那边,热扰动干的是晃来晃去,而且喜欢下山多于喜欢上山,但是因为它真的喜欢晃来晃去,所以也有机会跑到山的另一边。而量子隧穿,则是看见山就打隧道,一招开山掌,还不用力气……然后打完隧道就直接晃过去,哪里能量低就更喜欢呆在哪里。

于是,D-wave就是借助量子隧穿效应来进行优化计算的。这当然比经典下的要快多了,它会穿隧道么。最新的那篇nature论文其实也就是在说,D-wave的技术的确利用了量子效应。

但是,它有多快呢?目前没有证据表明,D-wave的芯片可以在多项式时间里解决QUBO。它的计算时间依赖于基态和第二低能的态的能量差,但我们对于这个能量差没有一个很好的界,于是也就不太能证明这个事情。不过按照实践的情况来看的话,还是比传统的计算机要快得多,当然快多少我们具体是不知道的。

但是D-wave最坑爹的地方还不在这里。实际上,D-wave的芯片不是一般科学界所说的量子计算机。

一般我们说的量子计算机,是指用量子门电路操纵量子位来进行计算的计算设备。它利用了量子物理最基本的性质:量子状态是可以叠加的。打个不太恰当的比喻,传统计算机可以操纵n维的空间,量子计算机操纵的则是2^n维的空间。不过,这个2^n维的空间可不是随便操纵的,只能用所谓“酉变换”来进行,所以也没有想象中什么“同时搜索所有解答”那么强大。

顺便说一下,这个貌似也是对量子计算机的误解之一。量子计算机是不能同时搜索所有解答的。它可以对混合态进行运算,但是运算出来的结果本身也是混合了起来的。只有对特定的问题,我们才能用特定的算法从混合的结果中抽取我们需要的信息。

至于D-wave的芯片,正如前面所说,它利用的是量子隧穿效应,它的这项计算技术名为量子退火,与量子门电路是非常不同的。比如说,能在量子门电路上运行的Shor算法(就是能快速分解大合数,搞出来了会对各种密码系统,比如说椭圆曲线、离散对数和RSA,有威胁的那个算法),实际上不能在D-wave的芯片上运行。而量子退火与量子门电路的计算能力是否等价,至今仍然没有定论。不过一般的意见是认为量子退火的计算能力比不上量子门电路的计算能力。

不过这也不是说D-wave的芯片一无是处,起码它在解决QUBO上的速度是独树一帜的,而QUBO这个优化问题本身又可以在人工智能等方面找到应用。据说Google就跟D-wave合作过,用D-wave的量子退火芯片来做图像识别,貌似效果还不错。而且如果我们考虑到可以进行量子门电路计算的量子计算机设计,能利用的量子位数目至今不超过10,能分解的最大的合数是15的话,那将D-wave的芯片看成是量子物理在计算方面目前最顶尖的应用,那其实也说得过去。

以上概括一下,其实就是:

D-wave的芯片不是传统意义上利用量子门电路进行计算的芯片,严格意义来讲不是一般说的量子计算机,估计计算能力也没那么强;然而,如果将量子计算机定义为关键的计算过程依赖于量子效应的计算机的话,那么D-wave的芯片可以被称为量子计算机。另外,D-wave的芯片不是万能的,它只能解决一个特定的问题,不过这个特定的问题应用范围比较广,所以还是比较有意义的。

最后插播新闻:D-wave卖出了第一台D-wave One,这次的冤大头是Lockheed Martin公司,不知道他家买这个是要干啥呢?

(zz)量子线性方程算法

matrix 发表于 2008年12月06日 17时00分 星期六
来自P-=-NP部门

Aram Harrow和同事刚刚在预印本网站发表了一篇论文:解决线性方程系统的量子算法PDF)。以下引用格致的介绍

我们现有的量子算法,比如Shor算法,Grover算法大都只能对经典算法作出多项式性的改进,新算法把最好的经典算法效率作出了指数性的提高,把求解稀疏矩阵方程的复杂度由O(n)降低到log(n)。更加重要的是,这是第一个解决了科学和工程中最常见的问题的量子算法。像Shor算法那样破解密码毕竟用途有限。在实际的工程和科研中,我们遇到最多的问题就是解线性方程组,且我们遇到的大部分线性方程组都是稀疏的,维度也非常高。新量子算法将能非常迅速的解决常见的线性方程组。唯一的问题是我们需要一台真正的量子计算机,MIT斯坦福马里兰,现在瞧你们的了。

source: http://science.solidot.org/article.pl?sid=08/12/06/0859256

相当不错~~~有这个动力的话量子计算机问世又近了一步了~~~

(zz)第46个梅森素数被发现

source: http://science.solidot.org/article.pl?sid=08/09/12/0559219

matrix 发表于 2008年9月12日 14时00分 星期五
来自真运气部门

第44个梅森素数是于2006年9月发现的,但在短短半个月内,GIMPS分布式计算接连发现了两个梅森素数。

2008年8月23日,一台GIMPS客户端计算机报告发现了第45个梅森素数,第一轮验证已经完成,确认是一个新的素数,第二轮验证的完成日期是9月11日。但始料未及的是,9月6日,又一台计算机报告发现了第46个梅森素数,独立验证确认这也是一个新素数,第二轮验证预订于14日。GIMPS将于下周透露细节。

我只能说运气太好了~~~要不就不发现~~~一发现就是两个~~~又有人能领奖金了~~~

(zz)“卤莽”软体升级,能更快的发现“对称”

matrix 发表于 2008年6月13日 14时35分 星期五
来自五次方程式部门

密歇根大学计算机科学家开发的一款开源软件(中文),能将寻找复杂方程式中对称的时间,从数日缩减为数秒。找寻对称是一种能突显通往答案捷径的方法。例如,验证火车时刻表的安全性、确认软件与硬件设计中的臭虫,或着加速一般搜寻任务。

名为saucy(卤莽)的软件由研究人员在2004年开发出来,它能加速基础计算机科学问题的解法,能迅速解答所谓的图自同构问题(graph automorphism problem)。当前软件升级增加了新算法,能更快的发现最短路径和对称。它将复杂方程式转换成图,并在顶点的排列中寻找相似性。在实验测试中,在不到0.5秒内,新软件在全世界路由器的网际网络连接图中捕捉到1083,687个不同的对称。图中的对称性意味着路由器可以被移来移去而不会改变(网络的)运作。在搜寻 Illinois州城市与乡镇之间公路网对称性的过程中,新的算法在0.5 秒内捕捉了104843个对称,而先前最强的演算法花了16分钟。

论文(PDF)

source: http://software.solidot.org/article.pl?sid=08/06/13/0641226

下载了论文来看~~~还是勉强看得明白的~~~算法的思路上还算自然~~~这个算法快的原因一个是面对稀疏图~~~这样的话同一个时间要考虑的结点数目就少了很多~~~另一个原因(据他们说是主要原因)就是观察到大多数图的自同构对称都只涉及到很少几个顶点~~~图的自同构对称置换可以构成一个置换群~~~称为Aut(G)~~~而他们观察到这个群可以由少数几个各自只涉及为数不多的顶点的置换生成出来~~~于是就有了他们的算法~~~

最近课上得差不多了~~~开始钻研图论~~~

(zz)魔方最少还原步数降至23步

source: http://science.solidot.org/article.pl?sid=08/06/06/062235

matrix 发表于 2008年6月06日 14时00分 星期五
来自上帝算法部门

3月份我们曾报道,Tomas Rokick正在开发一个非常高效的方法研究魔方最少的还原步骤,他证明任何魔方都可以在25步内还原。现在根据Tomas Rokick个人主页的更新,他宣布任意结构的魔方都可以在23步内解决。他之前进行运算的工作站为8G内存和1.6GHz Q6600 CPU,现在已经升级为一台超级计算机,索尼图形图像运作公司(Sony Pictures Imageworks)提供给他使用(当然是在电影制作空闲时间内)。在这个曾经制作了《蜘蛛侠3》和《冲浪企鹅》的工作室的帮助下,新的计算结果暗示任意结构的魔方可能的解决步数是21,22或23步。

果然是很好很强大~~~不知道极限是多少?~~~

(zz)一次成功的冷核聚变实验?

matrix 发表于 2008年5月24日 21时28分 星期六   来自冷静观察部门

冷核聚变(Cold Fusion)是指在接近常温常压和相对简单的设备条件下发生核聚变反应。多个轻原子核被强行聚合形成一个重原子核,并伴随能量释放。1989年3月23 日南安普敦大学的Martin Fleischmann和犹太大学的Stanley Pons宣称成功进行了冷核聚变实验,引起轰动,但其他科学家却无法重复该实验,美国能源部的调查报告认为实验不可信。之后从事冷核聚变的科学家都非常谨慎,前天(22日)日本大阪大学的荒田吉明(Yoshiaki Arata)教授和上海交大的张月昌(Yue Chang Zhang)教授向公众演示了冷核聚变实验,包括6家报纸和2家电视台在内的60余人在场观看了这次引入注目的实验。实验原理是基于他们曾经出版的论文(12),方法是用高压将氘气压入包含锆氧化物(ZrO2)和钯纳米粉末的真空单元内。实验产生了大量能源,并观察到氦-4(融合的信号)。这一演示证明这种方法是高度可重复的。

source: http://hardware.solidot.org/hardware/08/05/24/1314226.shtml

如果这是真的就好了~~~冷核聚变向来是人类的梦想~~~不用复杂的托卡马克装置也不用激光更不用维持一个等离子火球就可以享受聚变的能量~~~

不过由于以前的一些虚假实验,我们还是要比较小心~~~不要这么快庆祝~~~ 

update:已经被强烈怀疑是造假了~~~看来聚变能源还是任重道远啊~~~

(zz)忆阻器(Memristor)——电路的第4种基本元件

Source: http://science.solidot.org/science/08/05/02/1127232.shtml
matrix 发表于 2008年5月02日 19时25分 星期五
来自拷贝电路部门

基础电子学教科书列出三个基本的被动电路元件:电阻器、电容器和电感器;电路的四大基本变量则是电流、电压、电荷和磁通量。任教于加州大学伯克利分校,并且是新竹交通大学电子工程系荣誉教授的蔡少棠(Leon Chua),37年前就预测有第四个元件的存在,即忆阻器(memristor),实际上就是一个有记忆功能的非线性电阻器。

惠普公司实验室的研究人员最近证明忆阻器的确存在,研究论文在5月1日的《自然》期刊上发表。加州大学伯克利分校电机工程和计算机科学系教授蔡少棠,1971年发表《忆阻器:下落不明的电路元件》论文,提供了忆阻器的原始理论架构,推测电路有天然的记忆能力,即使电力中断亦然。惠普实验室的论文则以《寻获下落不明的忆阻器》为标题,呼应前人的主张。蔡少棠接受电话访问时表示,当年他提出论文后,数十年来不曾继续钻研,所以当惠普实验室人员几个月前和他联系时,他吃了一惊。
忆阻器可使手机将来使用数周或更久而不需充电;使个人电脑开机后立即启动;笔记型电脑在电池耗尽之后很久仍记忆上次使用的信息。忆阻器也将挑战掌上电子装
置目前普遍使用的闪存,因为它具有关闭电源后仍记忆数据的能力。利用惠普公司这项新发现制成的晶片,将比今日的闪存更快记忆信息,消耗更少电力,占用更少
空间。忆阻器跟人脑运作方式颇为类似,惠普说或许有天,电脑系统能利用忆阻器,像人类那样将某种模式(patterns)记忆与关联。

Simond又要更新他的课程了~~~而且很有可能是下一年的ADS~~~
话说这种东西真是好啊~~~有记忆能力~~~又可能带来新的变革~~~希望成功~~~
话说这是我第一篇在Ubuntu下发的帖~~~迟些我会写个小文章介绍一下~~~还有一个大的科普的一部分~~~