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公司,不知道他家买这个是要干啥呢?

Advertisements

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

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s