线性方程组的量子算法


[0811.3171] Quantum algorithm for solving linear systems of equations

这篇论文中提出了一个非常漂亮的量子算法,把求解稀疏矩阵方程的复杂度由O(n)降低到log(n)。我们现有的量子算法,比如Shor算 法,Grover算法大都只能对经典算法作出多项式性的改进,可这个算法把最好的经典算法效率作出了指数性的提高。更加重要的是,这是第一个解决了我们科 学和工程中最常见的问题的量子算法。像Shor算法那样破解密码毕竟用途有限。在实际的工程和科研中,我们遇到最多的问题就是解线性方程组,且我们遇到的 大部分线性方程组都是稀疏的,维度也非常高。经典算法为了解决这个问题,作出了诸多努力,但是现在最好的算法也只能达到O(n)的复杂度。这个量子算法告 诉我们,利用量子计算机解我们经典世界最常遇到的线性方程组,会非常非常快,我们可以解近乎无限维的稀疏线性方程组。我相信这会帮助我们解决以前无法解决 的问题,长期天气预报,更加有效的网络检索处理。问题只在于,我们什么时候才能造出真正实用的量子计算机。

Advertisements

发表评论

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