Linear gate bounds against natural functions for position-verification

技术摘要：针对自然函数位置验证的线性门复杂度下界

问题陈述
量子位置验证（PV）方案旨在通过具有特定时空约束的量子和经典输入，来验证证明者的空间位置。由于经典输入存在复制并转发攻击，而量子输入在无条件设置下存在基于纠缠的攻击，因此无条件安全性是不可能的；研究重点已转向有界资源模型。具体而言，像 $f$-routing 和 $f$-BB84 这样的协议要求诚实的证明者在仅操作 $O(1)$ 个量子系统的情况下，对长度为 $n$ 的输入计算一个经典的布尔函数 $f$。

前人的工作 [15] 已经确定，对于随机函数 $f$，不诚实的证明者需要规模与 $n$ 成线性关系（以量子比特计）的资源系统才能破解这些方案。然而，这一界限适用于纯化（幺正）视角下的资源系统维度，这混淆了经典处理与量子资源。此外，对于随机函数，诚实的证明者需要指数级的经典资源，使得该方案变得不切实际。本文解决的核心问题是：当 $f$ 是一个“自然”的低复杂度函数（特别是内积函数）时，建立不诚实证明者攻击这些方案所需的量子计算资源（门和测量）的下界，同时允许诚实的证明者以线性经典资源和常数量子资源进行操作。

方法论
作者将位置验证任务（$f$-routing 和 $f$-BB84）归约为带有共享纠缠的**同时消息传递（SMP）**通信复杂度模型（$SMP^*$）。

1. 策略模型：作者将不诚实的证明者建模为位于验证区域之外的两个代理（Alice 和 Bob），他们拦截输入并试图非局部地模拟所需的量子操作。他们分析了第一轮操作后系统的状态。
2. 状态分离：
   • 对于 $f$-BB84，他们证明了对于足够高的保真度（$\epsilon < 0.11$），允许在计算基下成功测量的状态集（$S^0_\epsilon$）与允许在 Hadamard 基下成功测量的状态集（$S^1_\epsilon$）是互斥的。这意味着第一轮操作后的状态有效地决定了 $f(x,y)$ 的值。
   • 对于 $f$-routing，他们利用纠缠单配性（monogamy of entanglement）和挤压纠缠（squashed entanglement）的性质，证明了允许在左侧恢复量子比特（$\tilde{S}^0_\epsilon$）或右侧恢复量子比特（$\tilde{S}^1_\epsilon$）的状态集在 $\epsilon < 0.027$ 时是互斥的。
3. 归约为 $SMP^*$：作者构建了一个 $SMP^*$ 协议，其中 Alice 和 Bob 向裁判发送他们局部量子操作（门和测量结果）的描述。裁判重建状态 $\rho_{RMM'}$ 并确定其属于哪一个集合（$0$或$1$），从而计算出$f(x,y)$。
   • 至关重要的是，作者是在非纯化模型中工作的。他们允许代理使用中途测量和经典处理来对后续门进行条件化。$SMP^*$ 协议中的消息大小对应于描述不诚实证明者所执行的量子门和测量序列所需的比特数。
4. 下界推导：通过将 $SMP^*$ 协议中的消息大小与证明者使用的门数（$C_G$）和测量数（$C_M$）联系起来，他们导出了不等式：
   $$(\log(q) + 1)(2C_G(f) + C_M(f)) \geq SMP^*_{\epsilon', \delta}(f)$$
   其中 $q$ 是代理持有的量子比特数。

主要贡献与结果

1. 内积函数的线性下界：通过应用已知于带有共享纠缠的 $SMP^*$ 模型中内积函数（$IP$）的线性下界 [24, 30]，作者证明了任何使用内积函数成功攻击$f$-routing 或 $f$-BB84 的行为，其所需的量子门和测量次数与输入规模 $n$ 成线性关系。
   $$(\log q + 1)(2C_G(IP) + C_M(IP)) \geq \Omega(n)$$
2. 鲁棒性：即使协议仅在常数比例的输入上成功（具体为 $1/2 + g(n)$，其中 $g(n)$ 的衰减速度慢于 $2^{-n/4}$），该界限依然成立。
3. 对容损方案的适用性：该结果适用于 $f$-BB84 的容损变体 [22]，解决了先前证明中的实际局限性。
4. 上界的紧致性：作者展示了对于内积函数，一种“花园水管”（garden-hose）攻击策略 [17] 可以使用 $O(n)$ 个 EPR 对和 $O(n)$ 次测量来完成任务。这表明关于操作次数的下界在对数因子范围内是紧致的。

意义与主张
本文声称在理解针对具有有界量子资源的不诚实证明者的位置验证方案的安全性方面取得了显著进展：

• 从系统规模转向计算复杂度：不同于以往关注共享纠缠态维度的界限（该维度可能会因纯化经典操作而膨胀），这项工作限制了实际的量子门和测量次数。这为攻击者提供了一个更直接的计算难度度量。
• 诚实证明者的可行性：结果适用于内积函数，对于使用经典资源的诚实证明者而言，该函数在计算上是可行的（线性复杂度），这与之前工作中使用的随机函数不同。
• 难度的分离：假设实现量子门比实现经典门更难，作者建立了这种分离：诚实证明者仅需线性经典资源和 $O(1)$ 量子资源，而不诚实证明者则需要线性量子资源（门/测量）来破解该方案。
• 精细化的系统规模界限：通过将不诚实证明者的电路深度限制在与诚实证明者相当的水平（例如 $d = O(\log n)$），作者导出了一个改进的攻击者所需量子比特数下界（$q \gtrsim n/\log n$），这比 [15] 中的 $q \gtrsim \log n$ 更强，并避免了纯化视角的缺陷。

作者得出结论，只要诚实的证明者能够高效计算该函数，这些方案对于具有亚线性量子资源的攻击者是安全的。