近日，IBM Quantum公司的Ramis Movassagh及其研究小组取得一项新进展。经过不懈努力，他们揭示了随机量子电路的难度。相关研究成果已于2023年7月27日在国际知名学术期刊《自然—物理学》上发表。
该研究团队证明了估计随机量子电路的输出概率对于任何经典计算机来说都是#P-难度。研究人员还将他们的结果扩展到量子计算的受限模型，即瞬时量子多项式时间(IQP)电路。为了实现这一点，研究人员通过将量子电路模拟的最坏情况减少到平均情况。结果对估计误差的鲁棒性为经典算法性能提供了新的难度标准。这一结果表明，对于大多数量子电路的近似经典模拟，存在指数难度势垒。
据悉，随着摩尔定律达到极限，量子计算机正在兴起，有望大幅超越经典计算机。目前，构建超过100个量子比特的量子处理器是有可能的，这有望超出经典模拟的范围。这些发展一直伴随着预期，在某个阶段，量子计算机应该能够执行任何经典计算机几乎不可能完成的任务。达到这个阈值的主要候选是随机电路采样，它涉及在实现一系列随机量子操作后对量子计算机的输出进行采样。然而，经典计算机模拟随机量子电路的难度很难从理论上提供保证。
附：英文原文
Title: The hardness of random quantum circuits
Author: Movassagh, Ramis
Issue&Volume: 2023-07-27
Abstract: As Moore’s law reaches its limits, quantum computers are emerging that hold promise to dramatically outperform classical computers. It is now possible to build quantum processors with over 100 qubits, which are expected to be beyond the reach of classical simulation. These developments have been accompanied by the anticipation that, at some stage, a quantum computer should be able to perform a task that is practically impossible for any classical computer. The lead candidate for reaching this threshold is random circuit sampling, which involves sampling the output of a quantum computer after implementing a sequence of random quantum operations. However, it is difficult to provide theoretical guarantees on the hardness of simulating random quantum circuits by classical computers. Here we prove that estimating the output probabilities of random quantum circuits is #P-hard for any classical computer. We also extend our results to a restricted model of quantum computation known as instantaneous quantum polynomial-time (IQP) circuits. We achieve this by a worst-case to average-case reduction for quantum-circuit simulation. The robustness of our result to the estimation error serves as a new hardness criterion for the performance of classical algorithms. Our results suggest that there is an exponential hardness barrier for the approximate classical simulation of most quantum circuits.
DOI: 10.1038/s41567-023-02131-2
Source: https://www.nature.com/articles/s41567-023-02131-2