研究证明经典计算机模拟随机量子电路的难度

量子计算机是利用量子力学现象进行计算的技术，最终可能在许多复杂的计算和优化问题上超越经典计算机。虽然一些量子计算机在某些任务上取得了显着的成果，但它们相对于经典计算机的优势尚未得到最终和一致的证明。

曾在IBMQuantum任职的GoogleQuantumAI研究员RamisMovassagh最近进行了一项理论研究，旨在从数学上证明量子计算机的显着优势。他发表在《自然物理学》上的论文从数学上表明，对于经典计算机来说，模拟随机量子电路并估计其输出是所谓的#P-hard(即，这意味着非常困难)。

“量子计算领域的一个关键问题是：量子计算机是否比经典计算机更强大?”进行这项研究的拉米斯·莫瓦萨(RamisMovassagh)告诉Phys.org。“量子霸权猜想(我们将其重新命名为量子首要猜想)说是的。然而，从数学上来说，它一直是一个需要严格建立的重大开放问题。”

研究人员最近一直试图通过理论和实验研究以各种方式证明量子计算机相对于经典计算机的优势。从数学上证明这一点的关键是证明经典计算机很难以高精度和小误差范围获得量子计算机的结果。

Movassagh解释道：“2018年，一位同事在麻省理工学院发表了演讲，当时的一项最新结果试图为随机电路采样(RCS)的难度提供证据。”“RCS是从随机量子电路的输出中进行采样的任务，谷歌刚刚提出将其作为证明量子首要性的主要候选者。我当时在场，以前从未研究过量子复杂性;事实上，我记得作为一名研究生，我什至发誓我永远不会在这个领域工作!”

Movassagh的同事于2018年在麻省理工学院提出的数学证明并没有最终解决证明量子首要性的长期存在的问题，但它是实现这一目标的相当大的进步。该证明是通过一系列近似和所谓的级数截断来实现的;因此，它有些间接，并引入了不必要的错误。

莫瓦萨说：“我喜欢通过数学来解决重大的开放性问题，尤其是当数学是直接的、该领域的专家不太了解并且很漂亮的时候。”“在这种情况下，我觉得我可能会找到更好的证明，并天真地认为，如果我以正确的方式解决问题，那么我可能会解决这个大的开放问题。所以，我开始研究它。”

Movassagh提出的数学证明与迄今为止介绍的数学证明有很大不同。它基于一组新的数学技术，这些技术共同表明平均情况(即随机量子电路)的输出概率与最坏情况(即最人为的)一样困难。

“这个想法是，你可以使用论文中提出的凯莱路径在任意两个任意电路之间进行插值，在这种情况下，这被认为是在最坏情况和平均情况之间，”莫瓦萨说。“凯莱路径是一种低次代数函数。由于已知最坏情况是#P困难(即，一个非常困难的问题)，因此使用凯莱路径可以插值到平均情况并表明随机电路本质上与最坏情况一样困难，概率很高。”

与过去得出的其他数学证明相比，Movassagh的证明不涉及任何近似，并且非常直接。这意味着它允许研究人员明确限制所涉及的错误并量化其稳健性(即其对错误的容忍度)。

自从Movassagh首次提出证明以来，他的研究小组和其他团队都对其进行了进一步测试并提高了其稳健性。因此，它可以很快为旨在改进证明或利用它来强调量子计算机潜力的其他研究提供信息。

Movassagh说：“我们实现了估计量子电路输出概率的难度的直接证明，这些为量子电路的经典模拟提供了计算障碍。凯莱路径和Berlekamp-Welch有理函数版本等新技术“对于量子密码学、计算和复杂性以及编码理论都有独立的兴趣。目前，这是最终反驳扩展教会图灵理论的最有希望的路径，这是量子复杂性理论的迫切目标。”

Movassagh最近的工作极大地促进了正在进行的研究工作，探索量子计算机相对于经典计算机的优势。在未来的研究中，他计划以目前的证明为基础，从数学上证明量子计算机在解决特定问题方面的巨大潜力。

莫瓦萨补充道：“在我接下来的研究中，我希望将这项工作与其他任务的难度联系起来，以更好地找出量子系统的易处理性。”“我正在研究这项工作在量子密码学等方面的应用。最后但并非最不重要的一点是，我希望证明量子首要猜想，并证明扩展丘奇-图灵论文是错误的!”

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！