技术摘要：更多即是更少：Haar 量子货币及相关领域的优化安全性

1. 问题陈述

本文探讨了量子货币和拷贝保护方案中一个基础性的安全漏洞：攻击者现有的持有量是否会促进伪造。在经典密码学中，拥有更多的资源（例如更多的钞票）通常不会降低破解系统的计算成本。然而，在量子设定下，拥有多个未知量子态的副本有时可以辅助状态估计或克隆。

具体而言，作者研究了 $k \to k+r$ 克隆问题：给定 $k$ 个未知量子态 $|\psi\rangle$ 的副本，并能访问反射算子 $C|\psi\rangle Z$，产生 $k+r$ 个有效副本所需的查询复杂度是多少？

现有的界限（如 Aaronson 和 Christiano [AC12] 的研究）表明，克隆的查询复杂度会随着 $k$ 的增加而下降（例如 $\Omega(\sqrt{N/k})$）。这意味着在密码学意义上，“富者更富”：拥有的钞票越多，伪造就越容易。本文旨在确定这种退化是本质存在的，还是存在某些构造，使得在 $k$ 低于全状态层析成像阈值（即 $k \ll N$，其中 $N=2^n$）的情况下，产生额外副本的成本保持独立于 $k$。

2. 研究方法

2.1 下界框架：用于量子任务的压缩算子

其核心技术贡献是将 Zhandry 的压缩算子技术 [Zha19] 创新性地应用于本质上属于量子任务的克隆问题。

• 算子纯化与离散化： 作者首先将连续的 Haar 随机分布还原为由随机函数 $f: [N] \to [M]$ 定义的相位态离散分布。这使得可以将算子纯化为一个量子寄存器。
• 傅里叶基与多重集： 通过在傅里叶基下观察算子寄存器，算子的状态被表示为一个“多重性记录表”（一个带符号整数的多重集）。
  • 平衡度（Balance）： 多重集中条目的总和（在反射查询下保持不变）。
  • 负规模（Negative-size）： 多重集中负条目的数量。
• 进度度量： 作者定义了一组投影算子 $\Gamma_\ell$，它们将状态投影到具有恰好 $\ell$ 个负元素的集合上。
  • 初始状态（带有 $k$ 个副本）的负规模为 0。
  • 获胜状态（带有 $k+r$ 个副本）要求状态支撑在负规模至少为 $r$ 的子空间上。
  • 单次反射查询最多只能增加 1 个负规模。
• 增量界定： 证明过程界定了从具有 $\ell-1$ 个负元素的子空间转移到 $\ell$ 个负元素的概率振幅。至关重要的是，作者证明了这种转移会产生一个与 $1/\sqrt{N}$ 相关的惩罚因子，并且累积 $r$ 个这样的步骤会导致成功概率呈指数级衰减，除非查询次数 $T$ 足够大。

2.2 上界：倍增算法

为了证明界限的紧致性，作者构建了一个匹配该下界的算法：

• 状态估计： 算法使用最优 POVM（对称纯态 POVM）从 $k$ 个副本中估计未知状态 $|\psi\rangle$，从而生成一个经典描述的状态 $|g\rangle$。
• 振幅放大： 利用估计的状态 $|g\rangle$，算法应用不动点振幅放大技术来生成一个新的 $|\psi\rangle$ 副本。
• 倍增策略： 算法采用“倍增”策略。从 $k$ 个副本开始，生成 $2k$ 个，然后是 $4k$，以此类推。研究表明，生成 $r$ 个额外副本的预期查询复杂度为 $O(\sqrt{rN})$，且与初始的 $k$ 无关（只要 $k+r = o(N)$）。

2.3 密码学归约

克隆界限被应用于两个密码学原语：

1. 公钥量子货币： 作者证明，对于基于 Haar 随机态和反射算子验证的量子货币方案，针对伪造 $r$ 个额外钞票的安全性仅取决于 $r$ 和 $N$，而与伪造者已持有的钞票数量 $k$ 无关。
2. 量子拷贝保护： 通过改编 [ALL+21] 的框架，作者构建了一个针对不可学习函数的拷贝保护方案。他们证明了一个安全二分性：攻击者要么学习了该函数（破坏了不可学习性假设），要么成功克隆了 Haar 随机程序态。无论海盗拥有多少个副本，克隆障碍始终保持在高位。

3. 主要结果

3.1 紧致克隆界限

本文确立了克隆查询复杂度的紧致界限。令 $N=2^n$。

• 定理 1.1 ($k \to k+1$)： 对于 Haar 随机态 $|\psi\rangle$，任何进行 $T$ 次查询 $C|\psi\rangle Z$ 并输出 $k+1$ 个寄存器的算法满足：
  $$\mathbb{E}_{|\psi\rangle} \text{Tr}[(|\psi\rangle\langle\psi|)^{\otimes(k+1)} \rho_\psi] \leq O\left(\frac{T^2}{N} + \frac{k+1}{N}\right)$$
  因此，若要实现常数成功概率，需要 $T = \Theta(\sqrt{N})$，前提是 $k = o(N)$。初始 $k$ 个副本的存在并不会渐近地降低查询成本。

• 定理 1.3 ($k \to k+r$)： 对于生成 $r$ 个额外副本：
  $$\mathbb{E}_{|\psi\rangle} \text{Tr}[(|\psi\rangle\langle\psi|)^{\otimes(k+r)} \rho_\psi] \leq \left( O\left(\frac{T^2}{rN} + \frac{k+r}{N}\right) \right)^r$$
  最优查询复杂度为 $\Theta(\sqrt{rN})$。值得注意的是，随着 $r$ 的增加，每个新副本的成本会降低（批量生成更高效），但拥有更多初始副本（$k$）并不会提供优势。

3.2 密码学意义

• 量子货币（定理 1.5）： 基于 Haar 随机态和反射算子的构造实现了最优查询安全性。伪造一个额外钞票需要 $\Theta(2^{n/2})$ 次查询，无论攻击者持有 1 个还是 $o(2^n)$ 个钞票。这解决了“更多即是更少”的悖论：财富的增长（更多的钞票）并不意味着伪造能力的增强。
• 拷贝保护（定理 1.6）： 所提议的拷贝保护方案的安全性受限于学习优势与克隆优势之和。克隆项 $HClone_{N,k}(T^*)$ 随 $T^2/N$ 缩放，且不随 $k$ 产生乘性损失。因此，拥有多个受保护程序的副本并不会降低盗版门槛。

4. 重要性与主张

本文声称解决了 Aaronson [Aar09] 提出的关于复杂度理论无克隆定理参数的开放问题。

• 最优性： 作者证明了对于 Haar 随机态，“更多即是更少”（即更多副本并无帮助）的特性是可以实现的，并且是优化的。此类系统的安全性不会随着攻击者积累更多副本而恶化，直到全状态层析成像变得可行（即 $k \approx N$）。
• 技术新颖性： 本工作是首次将压缩算子技术应用于纯粹量子任务（克隆）而非经典问题（如碰撞查找）的研究之一。通过开发多阶段进度度量（追踪多重集中的负元素），实现了对 $k \to k+r$ 转移的紧致界定。
• 密码学鲁棒性： 通过证明克隆障碍与 $k$ 无关，本文强化了量子货币和拷贝保护的理论基础，确保这些系统即使面对拥有大量初始持有量的攻击者时依然安全。

作者明确指出，其下界证明是在没有 AI 辅助的情况下开发的，而针对一般 $k \to k+r$ 情况的上界证明在初始草拟阶段使用了 AI，随后由作者进行了验证和重写。这些结果可推广到量子随机预言机（QROM）中的相位态，暗示了实现高效普通模型（plain-model）的潜在路径，尽管作者也指出，为这些实例化建立安全性仍然是一个开放的研究方向。