(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

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

Advertisements

2 thoughts on “(zz)量子线性方程算法

发表评论

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