Title: Sample complexity of device-independently certified "quantum supremacy" Show Chinese title

Title: 设备无关认证的“量子霸权”的样本复杂度

Abstract: Results on the hardness of approximate sampling are seen as important stepping stones towards a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, IQP circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any non-interactive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results: namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments. Show Chinese abstract

Abstract: 关于近似采样的难度结果被视为展示量子设备优越计算能力的有说服力演示的重要步骤。 此类实验最突出的建议包括玻色子采样、IQP电路采样和通用随机电路采样。 任何此类演示的关键挑战是验证正确实现。 对于所有这些例子，实际上对于所有足够平坦的分布，我们证明了从经典样本和目标分布描述进行非交互式验证需要指数级多次使用该设备。 我们的证明依赖于近似难度结果的核心属性：即，作为依赖于定义问题实例的随机酉矩阵的随机变量的采样分布具有较小的二阶矩。