2018年10月19日,《Science》官网刊登了一篇文章——《Quantum advantage with shallow circuits》,该文章由IBM和慕尼黑工业大学研究人员共同合作的成果。论文首次严格证明了在对计算能力做相同的限制的时候,量子计算机能力,能够完全超越经典计算机。这将是量子计算领域一新的里程碑,也为量子计算机的开发和应用指出一条更容易达到“量子霸权”的路线。

第一快讯|《Science》量子计算机被证明超越了经典计算机-量子客

论文指出:

量子效应可以增强信息处理能力并加速某些计算问题的解决方案。 是否可以在特殊环境中严格证明量子优势或者使用最新设备,通过实验证明量子优势——一直是一个具有争论性的主题。 我们证明了在一个恒定时间内运行的并行量子算法比它们的经典算法更具有有效性; 它们可以更好地解决与二元二次型相关的某些线性代数问题。 我们的工作给出了计算量子优势的无条件证明,同时确定了它的起源:它是量子非局域性的结果。 所提出的量子算法是近期实验实现的合适候选者,因为它仅需要在二维量子像素网格(量子比特)上具有最近邻门的恒定深度量子电路。

他们预计量子计算机在解决某些计算问题方面比经典计算机更好。 这种期望是基于计算复杂性理论中的(有根据的)推测,但是量子算法和经典算法的能力之间的严格比较很难执行。 Bravyi等人。 从理论上证明,并行量子电路解决某些线性代数问题所需的“步长”数量与问题大小无关,而这个数字与类似经典电路的大小呈对数增长。 这种所谓的量子优势源于量子电路中存在的量子关联,类似的经典电路中并不存在。

点评:首先这是一项开创性的工作,可以说是在“量子霸权”(quantum supremacy)上的一个里程碑。其次作为理论工作,能够发表在NS级别上的期刊,更是对此项工作的认可。

参考文献:

【1】Bravyi S, Gosset D, Koenig R. Quantum advantage with shallow circuits[J]. 2017.