Classically verifiable quantum advantage from a computational Bell test
Classically verifiable quantum advantage from a computational Bell test
复制标题
DOI：
10.1038/s41567-022-01643-7
复制
发表时间：
2021-04
期刊：
影响因子：
19.6
通讯作者：
Gregory D. Kahanamoku-Meyer;Soonwon Choi;U. Vazirani;N. Yao
中科院分区：
文献类型：
--
作者：
Gregory D. Kahanamoku-Meyer;Soonwon Choi;U. Vazirani;N. Yao
现有的量子计算优势的实验证明存在局限性，即验证量子设备的正确性需要指数级昂贵的经典计算。在这里，我们提出并分析了一个交互式协议，以证明量子计算的优势，这是有效的经典验证。我们的协议依赖于一类称为陷门无爪函数的加密工具。虽然这种类型的功能已经应用到量子优势协议之前，我们的协议采用了一个令人惊讶的连接贝尔不等式，以避免需要一个苛刻的密码属性称为自适应硬核位，同时保持基本上没有增加量子电路的复杂性，没有额外的假设。利用宽松的密码协议的要求，我们提出了两个陷门无爪函数的建设，拉宾的功能和Diffie-Hellman问题的基础上，这还没有在这种情况下使用之前。我们还提出了两个独立的创新，提高了我们的实现效率，并可以应用到其他量子密码协议。首先，我们给出了一个丢弃所谓垃圾比特的方案，消除了量子电路中可逆性的需要。其次，我们展示了一种自然的后选择方式，它降低了证明量子优势所需的保真度。结合这些结果，我们描述了一个蓝图，用于实现我们的协议在里德伯原子为基础的量子设备，使用硬件本地操作，已经被实验证明。
Existing experimental demonstrations of quantum computational advantage have had the limitation that verifying the correctness of the quantum device requires exponentially costly classical computations. Here we propose and analyse an interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies on a class of cryptographic tools called trapdoor claw-free functions. Although this type of function has been applied to quantum advantage protocols before, our protocol employs a surprising connection to Bell’s inequality to avoid the need for a demanding cryptographic property called the adaptive hardcore bit, while maintaining essentially no increase in the quantum circuit complexity and no extra assumptions. Leveraging the relaxed cryptographic requirements of the protocol, we present two trapdoor claw-free function constructions, based on Rabin’s function and the Diffie–Hellman problem, which have not been used in this context before. We also present two independent innovations that improve the efficiency of our implementation and can be applied to other quantum cryptographic protocols. First, we give a scheme to discard so-called garbage bits, removing the need for reversibility in the quantum circuits. Second, we show a natural way of performing postselection that reduces the fidelity needed to demonstrate quantum advantage. Combining these results, we describe a blueprint for implementing our protocol on Rydberg atom-based quantum devices, using hardware-native operations that have already been demonstrated experimentally.