走进科学
某些计算难题只可能在量子计算机上解决
Credit 123Rf
研究人员提出了一个全新的计算问题，证明其在一个经典的冯诺依曼计算机上即便不是无解的，也将是非常困难的；但是理论上它可以用量子技术来高效率地解决。这个被称为高斯玻色子抽样的问题是几年前提出的一个类似经典抽样的计算问题，目的是展示量子计算机具有的不可替代的潜在优势。
来自捷克布拉格技术大学和德国帕德博恩大学的研究人员在最近一期《物理评论》(Physical Review Letters)上发表了一篇关于高斯玻色子取样的论文。
总体而言，高斯玻色子抽样问题与Scott Aaronson和Alex Arkhipov在2011年提出的原始玻色子抽样问题极其相似。在这两个问题中，给予光子稳定输入频率，找出测量从光学系统出现的某些光子模式的概率。在复杂性理论中，玻色子抽样被认为是一个＃P-hard问题，这使得传统计算机不可能在有限的时间里解决这个问题。
因为目前还没有能够解决玻色子抽样问题的量子计算机，几个研究团队决定另辟蹊径，试图用量子光学实验来解决这个问题。结果证实本质上的计算难度无法通过设计实验的手段来绕过。这些实验的原本最大难点之一是产生大量的单光子。由于完全确定性的单光子源目前尚不存在，迄今为止所进行的所有实验都使用了概率性而不是确定性的光子源。
使用概率光子源的缺点是随着光子数目的增加，产生光子的成本呈指数级增长。到目前为止，使用的光子数量最多的是五个，这还不足以显示使用量子计算机的优势。
为了在实验中方便地获得更多的光子，研究人员专门研究了使用高斯态的玻色子取样。虽然高斯状态已经被用于各种实验，但它们的高斯性质从来没有被专门研究过。这些领域的优势是实验成本较低。
论文主要作者汉密尔顿接受Phys.org采访时说：“我们设计的实验方案一个最大的优点是能够更多使用我们指定输入状态的光子。这意味着，如果光子数量是实验物理学家的主要瓶颈，那么使用高斯状态的光子应该能更容易完成实验。”
研究的主要结果之一是，尽管实验如今更容易实现，但高斯玻色子抽样仍然是一个P-hard问题，因此，像玻色子抽样一样，也有可能作为一个体现量子计算优势的实例，两代计算机的分野。具体而言，研究人员发现，高斯玻色子采样与一个称为Hafnian的矩阵函数有关，这是一个如此困难的问题，目前还没有可以有效地逼近解的算法。