量子科技中心_量科网

在私有同步消息（PSM）模型中，\(k\) 个参与者分别获得输入 \(x_i\in\{0,1\}^n\)，然后各自向一名裁判发送消息，裁判应学习到 \(f(x_1,...,x_k)\)，但不得获取关于 \((x_1,...,x_k)\) 的其他信息。PSM 模型作为安全多方计算的最小模型被提出，并与布尔函数复杂性存在关联。在量子设定中，PSM 与非局域量子计算（NLQC）相关。目前，实现 PSM 所需的通信和关联成本仍缺乏深入理解。在此，该团队给出了（量子）PSM 模型的新上下界。对于下界，该工作表明：1) Nečiporuk 度量限制了完美正确性下 \(k\) 方量子 PSM 所需的纠缠量，从而对显式函数给出了二次下界。2) \(f(x_1,x_2)\) 的通信矩阵的秩限制了完美隐私但非完美正确性下的双方量子 PSM。这为经典 PSM 在非完美正确性下提供了一个此前未知的下界。在允许量子通信和共享纠缠时，这些是首次利用隐私条件推导出的量子 PSM 下界。对于上界，该研究证明：1) 设 \(s\) 为计算 \(f\) 的量子电路规模，\(d_f\) 为电路深度，\(k\) 为参与者数量，\(n\) 为每个参与者接收的比特数，\(\varepsilon\) 为正确性参数，则 \(\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/\varepsilon)\)。2) \(f\) 的傅里叶 1 范数的平方 \(\Vert \hat{f}\Vert_1^2\) 上界了经典 PSM 复杂度，即 \(\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)\)。在证明第一个上界时，该团队将现有基于 \(T\) 深度的 NLQC 技术从 2 方推广至 \(k \geq 2\) 方，并考虑了 Clifford 层受限于小光锥的情况。