量子优越性实验的经典模拟需要上万年，如何验证量子计算的正确性

目前已有三个国家展示了量子计算优越性，这些实验的经典模拟估计时间基本都在1万年以上。但是，如何验证量子计算的正确性呢，等一万年吗？当然不可能！因此我们需要一种可以快速验证量子计算正确性的经典方法。

在一篇8月1日发表于《自然·物理学》的论文中[1]，加州大学伯克利分校的Norman Yao及其合作者提出并分析了一种用于展示量子计算优越性的交互式协议，该协议是有效的经典可验证的。

Norman Yao

论文写道，现有的量子计算优越性实验演示具有局限性，即验证量子设备的正确性需要付出指数级代价的经典计算。他们的协议依赖于一类称为陷门无爪函数(trapdoor claw-free function，TCF)的加密工具。该协议消除了对自适应hardcore bit(一种严苛的加密属性)的需要，在量子电路中基本上没有开销，并且没有额外的加密假设。

首先，他们演示了贝尔不等式测试中的一个想法如何能够达到与自适应hardcore bit相同的加密目的。从本质上讲，这种交互协议是CHSH游戏的变体，其中一个玩家由一个密码结构代替。通常，在CHSH中，两个量子方被要求产生经典设备不可能产生的关联。如果强制实施类空间分离来排除双方之间的通信，那么相关性就构成了量子性的证明。在本文的例子中，类空间分离被加密问题的计算难度所取代。特别地，量子证明者(prover)持有一个量子比特，其状态依赖于加密秘密。从贝尔定理的角度来看，该协议可以被视为“单探测器贝尔测试”——加密任务产生的单量子比特状态，与通过纠缠第二个量子比特并用另一个探测器测量它产生的单量子比特状态相同。就像在CHSH游戏中，量子设备以大约85%的概率通过验证者(verifier)的测试，但经典设备最多只能以75%的概率成功。这种成功概率的有限差距正是量子优势的可验证测试。

下图显示了完整协议。该协议由证明者和验证者之间的三轮交互组成(一轮是来自验证者的挑战，随后是证明者的响应)。

第一轮在两个位串上生成多量子比特叠加，这在密码学上很难进行经典计算。第二轮将这种叠加映射到一个辅助量子比特的状态，保留足够的信息，确保最终的单量子比特状态也很难用经典方法计算。第三轮将这个单个量子比特作为CHSH式测量的输入，允许证明者生成一个与加密秘密相关联的数据比特，这种方式在经典情况下是不可能的。

交互式量子优越性协议的示意图

其次，通过消除对自适应hardcore bit的需要，他们提出了两种加密结构，第一种是基于判定性的Diffie-Hellman问题(DDH)，第二种是利用函数fN(x)=x2modN，其中N是两个质数的乘积，它构成了Rabin密码系统的主干。一方面，DDH很有吸引力，因为该问题的椭圆曲线版本对于经典计算机特别困难。另一方面，x2modN可以更有效地实现，其难度相当于因式分解。作者希望这两种结构将为寻找更多具有理想性质(小密钥尺寸和高效量子电路)的TCF提供基础。

他们还提出了两项独立的创新：一个固有的后选择方案，用于增加噪声设备通过测试的概率，另一个方法是大幅减少量子电路可逆性要求引起的开销。前者允许量子设备以较低的量子保真度换取整体运行时间的成比例增加，同时仍然通过加密测试。后者是一种特定于该协议结构的基于测量的非计算(uncomputation)方案，可将经典电路转换成基本上零开销的量子电路。

他们从数值上分析了这种后选择方案对于特定TCF x2modN的有效性。为了给函数的输出增加冗余，他们将这种TCF映射到函数(3ax)2mod(32aN)，用于可调整数a，并在通用噪声模型下模拟电路。

对于a=0，电路实现了原始函数x2modN，其中，在没有后选择的情况下，需要约0.83的总电路保真度来实现量子优越性。如下图所示，对于a=0，TCF中的固有冗余使得他们的后选择方案将优越性阈值变为约0.51的保真度。对于a=2，具有F≳0.1的电路保真度仍高于量子优越性阈值，而对于a=3，所需的电路保真度下降到1%以下。执行后选择会产生额外的运行时成本，但是仅4.7倍的开销就已经能够在10%的整体电路保真度下实现量子优越性。至关重要的是，运行时的增加主要是由于重新运行量子电路，并不意味着需要更长的实验相干时间。

后选择方案的性能

最后，着眼于TCF x2modN，提供了针对近期量子设备的显式量子电路。他们表明，量子优势的可验证测试可以用大约103个量子比特和大约105的门深度来实现。然后设计了一个一个针对可编程里德堡量子计算平台优化的x2modN的具体实现。对应于里德堡阻塞机制的自然物理相互作用可以直接实现多量子比特控制的任意相位旋转，而无需将此类门分解为通用的双量子比特操作。访问此类原生门会立即将实现量子优势的门深度降低一个数量级。

实现x2modN的基本相位电路。其中，n是输入寄存器的长度，m=n+O(1)是输出寄存器的长度。可以修改该电路以减少门和量子比特数。

在里德堡原子中实现x2modN的蓝图。a.具有里德堡阻塞相互作用的中性原子的3D阵列的示意图。b.示例：里德堡原子可以被捕获在光镊阵列中。处于里德堡激发态的原子(红色)可以改变附近原子(蓝色)的能级。d.通过|0⟩↔|r⟩之间的π脉冲序列实现多量子比特控制的相位旋转。

参考文献：

[1]https://www.nature.com/articles/s41567-022-01643-7