量子优势及其高效认证难以同时实现

具有讽刺意味的是，物理学家们已经证明，可以用来表明量子计算设备能解决古典计算机无法解决的一些问题也无法有效地证明这种“量子至上”已经实现了，各种各样的计划。在量子计算中，认证问题对于正式验证量子器件的卓越计算能力至关重要。

来自德国，Dominik Hangleiter，Martin Kliesch，Jens Eisert和Christian Gogolin的团队在最近一期“ 物理评论快报”上发表了一篇关于量子至上认证工作的论文。

柏林自由大学的Hangleiter告诉Phys.org，“我们严格证明了该领域许多人的直觉，即为量子至上论证提出的证明随机抽样方案需要指数级的样本。” “我们工作中最有趣的发现之一是，这是因为它首先能够证明近似的采样硬度，即采样分布的平坦度。我们的工作也指出了一种可能的方法。这种困境：互动或量子认证协议。“

术语“量子至上”指的是量子计算设备可以解决一些实际上不可能用于经典计算机解决的问题的可能性。对于经典计算机来说，一个被认为难以处理的问题是从指数大型数据集中的某些非常平坦的分布(其中所有结果几乎同样可能)的随机抽样。

目前，没有通用的，容错的量子计算机可用于实验，但即使是今天可用的有限量子装置也被认为能够执行随机采样任务。直观地说，这是因为量子设备可以在集合的所有元素的正确叠加中准备状态，而经典设备需要逐个访问指数级的多个概率。

所有物理设备(量子或经典)的局限之一是它们只能进行近似采样。因此，为了证明量子至上，研究人员必须证明量子器件的近似采样足够接近理想采样，因此对于经典计算机来说它仍然是难以处理的。

这个概念的所有当前证明，称为近似采样硬度，使用小的二阶矩。在随机抽样任务中，随机选择分布。基本上，小的第二时刻意味着随机选择的分布集中在均匀分布周围，因此非常平坦。

在新论文中，研究人员表明，小的第二时刻也禁止单独使用样本进行有效认证。也就是说，具有小的二阶矩的采样分布不能用多项式的许多样本来证明，而是需要指数地多个样本。这使得认证在合理的时间内执行效率低下且不切实际。

结果适用于各种广泛使用的采样方案，包括玻色子采样和通用随机电路采样等。但是，结果并不意味着任何方法都无法进行有效的认证。相反，研究人员希望这些研究结果将推动替代认证计划的发展，以及适用于具有更大二阶矩的分布的近似采样硬度的证明。

“我们的工作指导了寻找可行认证计划的方式，”Hangleiter说。“特别是，使用特定于设备的知识来利用认证通常是有意义的。研究的一个方向是为量子采样方案开发特定于设备的认证方案，但是进一步思考，也可以进行更复杂的任务。量子计算机。

“量子采样方案是非常'干净'的量子至上主义提议，因为它们允许复杂性 - 理论上的硬度论证。同时，它们还没有真正的应用(还)。第二个研究方向是开发方案这在近期设备上是可行的，但也很难，这也解决了一个有用的任务，以及找到已知采样方案的应用。“