量子科技中心_量科网

经典地，在量子设备上检验反对易算子的存在性是支撑经典验证量子计算近期进展的关键工具。虽然此类检验可以基于密码学假设，但已知的构造依赖于高度结构化的假设，例如陷门爪函数。在本文中，研究人员试图通过从（特定形式的）反对易性经典检验中构建强密码学来解释这一现状。具体而言，该团队提出了非对易性检验（ToNC）的概念，这是一种量子证明者与经典验证者之间的交互协议，其中证明者的最后一轮响应是通过测量两个二元可观测量 \(P_0, P_1\) 之一获得的，具体取决于验证者的挑战比特 \(c\)。该研究证明，在广泛参数范围内，ToNC 蕴含经典通信的密钥协商（KA），而 ToNC 与单向函数结合则蕴含不经意传输（OT）。在此过程中，该团队开发了相关工具，并首次给出了后量子 KA 和 OT 的困难性放大结果，其中通信是经典的但敌手可能是量子的。具体而言，该工作证明了以下具有独立意义的结果： - 后量子硬核测度定理：对于任意高效可采样的高最小熵分布 \(D\)，其样本为 \((x,b)\) 对，且量子电路从 \(x\) 预测 \(b\) 的优势至多为 \(\delta\)，则存在一个密度为 \((1-\delta)\) 的子分布 \(M\preceq D\)，在该子分布上 \(b\) 近乎最优地量子难以预测。 - 后量子交互式异或引理：给定任意经典交互式协议，如果量子敌手猜测私有挑战者比特 \(b\) 的优势至多为 \(\delta\)，则两次顺序重复将预测挑战者比特异或值 \(b_1\oplus b_2\) 的优势降低至至多 \(\delta^2+\rm{negl}(\lambda)\)。