[0811.3171] Quantum algorithm for solving linear systems of equations

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

今天看到的一篇很cool的论文是讨论用肉眼能否看到纠缠。结论是多个人合作，用肉眼是可能”看到”纠缠的。这真是一个很有趣的题目，想人所不愿意想，把”不可能”变成可能。

Possible entanglement detection with the naked eye

Nicolas Brunner, Cyril Branciard, and Nicolas Gisin

Group of Applied Physics, University of Geneva, CH-1211 Geneva 4, Switzerland

The human eye can detect optical signals containing only a few photons. We investigate the possibility to demonstrate entanglement with such biological detectors. While one person could not detect entanglement by simply observing photons, we discuss the possibility for several observers to demonstrate entanglement in a Bell-type experiment, in which standard detectors are replaced by human eyes. Using a toy model for biological detectors that captures their main characteristic, namely, a detection threshold, we show that Bell inequalities can be violated, thus demonstrating entanglement. Remarkably, when the response function of the detector is close to a step function, quantum nonlocality can be demonstrated without any further assumptions. For smoother response functions, as for the human eye, postselection is required.

量子力学数学表示告诉我们，量子测量时，量子态塌缩，最后会稳定到系统的量子本征态上面，无法逆转。这实际是量子测量的冯.诺伊曼表示，对应的一种很强的量子测量过程。

但是实际测量一个量子系统没有这么简单。比如，我们通过测量也许只能得到量子系统的部分信息，量子态并没有完全塌缩，那么我们还是可以翻转这个量子测量过程的。假设一个量子阱中束缚了一个电子，只有它自旋向上时才能被测量到，但是探测器的效率并不是100%。那么当探测器没有测量事件时，电子可能是自旋向上，也可能向下，并没有完全塌缩。然后对这个量子态旋转180度，再次测量。如果仍旧没有测量事件发生，那么我们实际上就把量子态恢复到测量前的状态了。当然，这个方案只能以一定的概率实现。

最近的物理评论快报报道了在超导量子比特中实现了这个方案。为了验证方案的可靠性，他们最后用了量子全息术来测量量子态，得出量子态的保真度。他们发现，当测量概率小于等于0.6时，量子态的保真度大于0.7。更高的测量成功率会破坏这个方案。更加详细的分析讨论，见下面的这个评述。