微软成功证明浅量子电路性能可成倍提高

目前已经有不少证据表明：量子计算机可以突破传统计算机的瓶颈和束缚。例如谷歌近期宣布的53-qubit的量子计算机Sycamore，传统计算机需要10000年才能计算出的任务在这台计算机上只需要3分钟20秒就能完成，实现了“量子至上”。 J)Ol"LXV  
9(Jy0]E~  
1
fRP1  
而现在量子领域又有重大发现，在得到Microsoft Quantum支持下一支科研团队证明了证明量子计算机可以显着改善计算问题的时间复杂度。在一篇名为《浅量子电路和无约束扇形浅经典电路之间的指数分离》（Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits）的论文中，一支团队在微软的支持下证明了浅量子电路可以解决在浅经典无边界电路领域中无法解决的问题。 gvlFumg
2  
W "k|K:  
该团队由Microsoft Quantum的高级研究员Robin Kothari，滑铁卢大学的Luke Schaeffer（也在Microsoft Quantum实习），麻省理工学院的Adam Bene Watts和加州大学伯克利分校的Avishay Tal组成。该团队的这项重大发现是卢克·谢弗（Luke Schaeffer）在世界上最大的量子计算会议-量子信息处理年度会议（QIP）上提出的。 OT@yPG  
Mt=R*M}D0  
想要更好的了解这支团队的重大发现，我们需要补充下量子计算上的相关知识。和传统计算机处理0和1两个位不同，量子计算机在qubit上进行，这些量子位可以在任意给定的瞬间以两种状态的量子叠加。为了使量子计算机能够按需执行，我们必须借助量子闸/量子门（Quantum Gates）对它们进行某些操作。为简单起见，可以将这些普通逻辑门视为“且”（AND）、“或”（OR）、“非”（NOT）状态。 x;(g  
3daC;;XO  
普通逻辑门的组合创建经典电路，而量子门的组合创建量子电路。在前者能够解决后者无法解决的问题之后，先前已证明一种特殊类型的量子电路浅量子电路优于浅经典有界电路。 kT2Wm/L  
X.eB ;w/}  
在最新研究中，浅层量子电路的尺寸要与经典电路（浅层无界电路）的出色表现相提并论。团队证明： v^TkDf(Oz  
=JxFp, Xr  
...浅量子电路可以解决浅经典的无界电路无法解决的问题，除非它们使用指数级数量的量子门。 a%*_2#  
~ aA;<#  
微软希望这项新的进步能够激发其他人冒险进入量子计算机领域，并在他们的帮助下找到解决实际问题的解决方案。有关一般研究和量子电路的详细信息，请参阅博客文章。您还可以在团队在此处发表发现的地方研究该论文。 wPgDy  
QtlT&|$   
论文链接：https://arxiv.org/pdf/1906.08890.pdf