2025-11-12T15:52:09.916354

Quantum bounds for compiled XOR games and $d$-outcome CHSH games

Baroni, Vu, Bourdoncle et al.
Nonlocal games play a crucial role in quantum information theory and have numerous applications in certification and cryptographic protocols. Kalai et al. (STOC 2023) introduced a procedure to compile a nonlocal game into a single-prover interactive proof, using a quantum homomorphic encryption scheme, and showed that their compilation method preserves the classical bound of the game. Natarajan and Zhang (FOCS 2023) then showed that the quantum bound is preserved for the specific case of the CHSH game. Extending the proof techniques of Natarajan and Zhang, we show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games: XOR games and d-outcome CHSH games. We also establish that, for any pair of qubit measurements, there exists an XOR game such that its optimal winning probability serves as a self-test for that particular pair of measurements.
academic

Quantum bounds for compiled XOR games and dd-outcome CHSH games

基本信息

  • 论文ID: 2403.05502
  • 标题: Quantum bounds for compiled XOR games and dd-outcome CHSH games
  • 作者: Matilde Baroni, Quoc-Huy Vu, Boris Bourdoncle, Eleni Diamanti, Damian Markham, Ivan Šupić
  • 分类: quant-ph (量子物理)
  • 发表时间/会议: Accepted in Quantum 2025-08-08
  • 论文链接: https://arxiv.org/abs/2403.05502

摘要

非局域游戏在量子信息理论中发挥着关键作用，在认证和密码协议中有众多应用。Kalai等人(STOC 2023)引入了一种使用量子同态加密方案将非局域游戏编译为单证明者交互式证明的程序，并证明了他们的编译方法保持游戏的经典界。Natarajan和Zhang(FOCS 2023)随后证明了对于CHSH游戏的特定情况，量子界得以保持。本文扩展了Natarajan和Zhang的证明技术，证明Kalai等人的编译程序对两类游戏保持量子界：XOR游戏和d-结果CHSH游戏。我们还建立了对于任何一对量子比特测量，存在一个XOR游戏，使得其最优获胜概率可以作为该特定测量对的自我测试。

研究背景与动机

核心问题

本研究要解决的核心问题是：如何将需要多个空间分离设备的Bell非局域性认证工具转换为单设备设置，同时保持其量子优势。

问题重要性

  1. 实用性需求：Bell非局域性虽然在理论上提供了信息论安全保证，但需要至少两个不通信的参与方在空间上分离，这在实验上极具挑战性
  2. 计算平台兼容性：现有的Bell型场景与量子计算平台不兼容，因为无法在集成设备上强加空间分离和通信禁止
  3. 认证工具的普及：将认证工具从多设备转换为单设备设置将显著提升其适用性

现有方法局限性

  1. 空间分离要求：传统Bell非局域性需要物理空间分离，限制了应用场景
  2. 有限的理论结果：Kalai等人的编译方法只证明了经典界的保持，缺乏量子界的上界
  3. 特定游戏限制：Natarajan和Zhang的结果仅适用于CHSH游戏，缺乏通用性

研究动机

利用量子同态加密(QHE)通过隐藏完整输入信息来模拟空间分离，从而将非局域游戏编译为单证明者交互式证明，并证明这种编译保持量子界。

核心贡献

  1. 扩展量子界保持定理：证明了Kalai等人的编译程序对XOR游戏和d-结果CHSH游戏保持量子界，误差仅为安全参数的可忽略函数
  2. 建立密码学SOS分解框架：基于Natarajan和Zhang的技术，发展了适用于更广泛游戏类别的密码学平方和(SOS)分解方法
  3. 实现计算自我测试：
    • 对任意一对量子比特测量的自我测试
    • 三个反对易量子比特可观测量的自我测试
  4. 提供新的理论工具：引入伪期望映射(pseudo-expectation map)，将非局域可观测量的多项式映射到编译游戏中观察到的关联

方法详解

任务定义

输入：非局域游戏G，量子同态加密方案QHE 输出：编译后的单证明者交互式游戏G' 约束：保持原游戏的量子界，误差仅为安全参数κ的可忽略函数

核心技术框架

1. 编译协议(KLVY编译)

对于双方非局域游戏：

  • 第一轮：验证者发送加密问题 xˉ=Enc(x)\bar{x} = \text{Enc}(x) 给证明者，收到加密答案 aˉ=Enc(a)\bar{a} = \text{Enc}(a)
  • 第二轮：验证者明文发送问题 yy 给证明者，收到明文答案 bb
  • 判定：使用谓词 V(Dec(aˉ),b∣Dec(xˉ),y)V(\text{Dec}(\bar{a}), b|\text{Dec}(\bar{x}), y) 判断输赢

2. 伪期望映射

定义线性算子 E~\tilde{E}，将测量可观测量的齐次2次多项式映射到编译游戏中的关联：

E~[AxBy]=Cx,y,E~[ByAx]=Cy,xT\tilde{E}[A_x B_y] = C_{x,y}, \quad \tilde{E}[B_y A_x] = C^T_{y,x}

E~[AxAx′]=δx,x′,E~[ByBy′]=Sy,y′\tilde{E}[A_x A_{x'}] = \delta_{x,x'}, \quad \tilde{E}[B_y B_{y'}] = S_{y,y'}

其中关联矩阵定义为： C=∑x,y⟨Ax,By⟩∣x⟩⟨y∣C = \sum_{x,y} \langle A_x, B_y \rangle |x\rangle\langle y|

3. 密码学SOS分解

对于XOR游戏，利用Theorem 1中的SOS分解：

ξq1−Bg=∑xλx2(Ax−∑yFxyBy)2+P({By}y)\xi_q 1 - B_g = \sum_x \frac{\lambda_x}{2}\left(A_x - \sum_y F_{xy}B_y\right)^2 + P(\{B_y\}_y)

应用伪期望映射： E~[ξq1−Bg]=∑xλx2E~[(Ax−∑yFxyBy)2]+E~[P({By}y)]\tilde{E}[\xi_q 1 - B_g] = \sum_x \frac{\lambda_x}{2}\tilde{E}\left[\left(A_x - \sum_y F_{xy}B_y\right)^2\right] + \tilde{E}[P(\{B_y\}_y)]

关键引理

Lemma 8：对于形如 Px=Ax−∑yFxyByP_x = A_x - \sum_y F_{xy}B_y 的多项式，存在可忽略函数 δQHE(⋅)\delta_{\text{QHE}}(\cdot) 使得： E~[Px†Px]≥−δQHE(κ)\tilde{E}[P_x^\dagger P_x] \geq -\delta_{\text{QHE}}(\kappa)

技术创新点

  1. SOS分解的特殊形式：证明了XOR游戏的SOS分解可以写成每项只包含一个Alice可观测量的形式
  2. 密码学安全性利用：巧妙利用QHE的IND-CPA安全性来界定伪期望值
  3. 高维推广：将方法扩展到d-结果测量的SATWAP不等式

实验设置

理论验证框架

本文主要是理论工作，通过数学证明验证结果：

  1. XOR游戏类：验证所有XOR游戏的量子界保持性质
  2. d-CHSH游戏：验证SATWAP不等式的量子界保持
  3. 自我测试协议：构造具体的编译游戏实现测量的自我测试

评价标准

  1. 量子界保持：编译后游戏的最优量子获胜概率与原游戏的差距仅为 negl(κ)\text{negl}(\kappa)
  2. 自我测试鲁棒性：在噪声和有限安全参数下的自我测试误差界
  3. 计算效率：证明者策略的量子多项式时间可实现性

主要结果

1. XOR游戏的量子界保持 (Theorem 3)

结果：给定最优量子偏差为 ξq\xi_q 的XOR游戏，编译后XOR游戏的最优量子偏差为 ξq+δQHE(κ)\xi_q + \delta_{\text{QHE}}(\kappa)，其中 δQHE(⋅)\delta_{\text{QHE}}(\cdot) 是可忽略函数。

2. d-维SATWAP不等式 (Theorem 4)

结果：对于d维SATWAP Bell不等式，如果d相对于安全参数κ是多项式的，则编译后SATWAP不等式的量子界为 (βdSATWAP)q+θ(κ)(\beta^{\text{SATWAP}}_d)_q + \theta(\kappa)，其中 θ(⋅)\theta(\cdot) 是可忽略函数。

3. 任意双量子比特测量的自我测试

结果：对于每对量子比特可观测量，存在一个XOR游戏G，使得在编译协议G'中以至少 ωq(G)−ϵ\omega_q(G) - \epsilon 概率获胜的任何多项式时间证明者必须实现在 O(ϵ,negl(κ))O(\sqrt{\epsilon}, \text{negl}(\kappa)) 范围内的测量算子，直到局部等距。

4. 三个反对易Pauli可观测量的自我测试

结果：基于elegant Bell不等式的编译协议可以自我测试三个反对易的Pauli测量 σx,σy,σz\sigma_x, \sigma_y, \sigma_z，误差为 O(δ,negl(κ))O(\delta, \text{negl}(\kappa))。

相关工作

非局域游戏编译

  1. Kalai等人(2023)：首次提出使用QHE编译非局域游戏，证明经典界保持
  2. Natarajan和Zhang(2023)：证明CHSH游戏的量子界保持
  3. Brakerski等人(2023)：针对特定CHSH游戏的量子界分析

Bell非局域性应用

  1. 设备无关量子密钥分发：基于Bell不等式违反的安全密钥分发
  2. 认证随机性：利用Bell非局域性认证真随机数
  3. 自我测试：通过Bell不等式违反认证量子设备

量子同态加密

  1. Mahadev(2018)：首次提出量子同态加密概念
  2. Brakerski(2018)：改进噪声容忍性的QHE方案

结论与讨论

主要结论

  1. 通用性扩展：成功将量子界保持结果从单一CHSH游戏扩展到整个XOR游戏类和d-结果CHSH游戏
  2. 自我测试实现：首次实现了单证明者设置下任意量子比特测量对的计算自我测试
  3. 理论工具：建立了分析编译游戏量子界的通用数学框架

局限性

  1. SOS分解形式限制：方法仅适用于具有特定形式SOS分解的游戏（每项只包含一个Alice可观测量）
  2. 安全参数依赖：结果的精确性依赖于QHE方案的安全参数
  3. 多方游戏：尚未扩展到超过两方的非局域游戏

未来方向

  1. 通用游戏类：研究编译程序是否对所有非局域游戏保持量子界
  2. 多方扩展：将方法推广到多方非局域游戏
  3. 实际应用：在真实量子计算平台上实现和测试编译协议

深度评价

优点

  1. 理论严谨性：数学证明完整，技术路线清晰
  2. 实用价值：解决了Bell非局域性应用中的重要实际问题
  3. 方法创新：巧妙结合密码学安全性和量子信息理论
  4. 结果完整性：不仅证明了量子界保持，还实现了自我测试功能

不足

  1. 适用范围：方法对SOS分解形式有特殊要求，限制了通用性
  2. 实验验证：缺乏实际量子设备上的实验验证
  3. 效率分析：对编译协议的计算复杂度分析不够深入

影响力

  1. 理论贡献：为量子密码学和复杂性理论的交叉研究提供了新工具
  2. 应用前景：为实际量子计算平台上的设备认证开辟了新途径
  3. 研究方向：推动了编译量子协议的理论研究

适用场景

  1. 量子设备认证：在集成量子计算平台上认证量子设备性能
  2. 量子密码协议：设计基于计算假设的量子密码方案
  3. 量子优势验证：在单设备环境下验证量子计算优势

参考文献

  1. Kalai et al. "Quantum advantage from any non-local game." STOC 2023
  2. Natarajan and Zhang. "Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification." FOCS 2023
  3. Mahadev. "Classical homomorphic encryption for quantum circuits." FOCS 2018
  4. Brakerski. "Quantum FHE (almost) as secure as classical." CRYPTO 2018

本论文在量子信息理论和密码学的交叉领域做出了重要贡献，通过巧妙的数学技巧将多方量子协议转换为单方协议，同时保持其量子优势，为实际量子计算应用提供了重要的理论基础。