可克隆的量子证明比经典证明更强吗？

不可克隆性并非量子证明优势的来源

近期 QMA 与 QCMA 的经典谕示分离把量子见证的不可克隆性当作关键机制：经典见证可以被复制并在多次执行中重复使用，最终泄露过多关于谕示的信息。这引出一个问题：不可克隆性是否真的是量子证明胜过经典证明的必要条件。

这篇论文给出的答案是否定的。它构造了一个经典谕示 O，使得 QCMA^O 严格包含于 ClonableQMA^O。该构造中的诚实见证能以保真度 1 - negl(lambda) 在多项式时间内被克隆，因此即使证明态可以被复制，量子优势依然存在。这一结果把 Nehoran 和 Zhandry 早先的量子谕示分离强化到纯经典谕示，解决了他们留下的开放问题。

ClonableQMA 在 QCMA 与 QMA 之间的位置

ClonableQMA 由 Nehoran 和 Zhandry 提出，用来刻画在计算约束下可被高效克隆的量子证明。它位于层级 QCMA subseteq ClonableQMA subseteq QMA 之中，把可克隆量子证明置于经典证明与不受限量子证明之间。

这一层级的两个端点 QCMA 与 QMA 长期是 Aharonov 和 Naveh 最早提出的问题核心：量子证明是否比经典证明更强。Bostanci、Haferkamp、Nirkhe 和 Zhandry，以及随后 Bostanci、Huang 和 Vaikuntanathan 的突破性工作，在经典谕示下建立了 QMA 与 QCMA 的无条件分离。这篇论文转而针对中间类，证明相对于经典谕示，ClonableQMA 本身严格强于 QCMA。

由码交集问题构造的建议态

该构造建立在 Yamakawa-Zhandry 码交集问题之上。给定 Sigma^n 上的线性码 C、把 Sigma 映射到 {0,1} 的哈希函数 H_i，以及目标 b 属于 {0,1}^n，任务是找出一个码字 c 属于 C，使得拼接后的哈希 H(c) 等于 b。对合适的码，Yamakawa-Zhandry 量子算法能高效求解，而多项式查询的经典算法会失败。论文采用 Bostanci、Huang 和 Vaikuntanathan 的偏置变体，目标为 b = z 拼接 0^(n-l)，哈希函数强烈偏向零。

核心量子态是 |adv_H>，它由每个坐标上哈希原像 |H_i^{-1}(0)> 与 |H_i^{-1}(1)> 的均匀叠加的张量积，以及 |phi_2>（C 中码字的均匀叠加）组成。在不同谕示接口下，同一个态承担三种角色：ClonableQMA 中的可克隆量子证明、BQP/clonableqpoly 中的可克隆量子建议，以及量子火中的火焰态。由于它源自 Yamakawa-Zhandry 搜索算法，作者始终称其为建议态。

锁定式哈希访问让该态能复制自身

关键技术装置是谕示 M[H, E]，它在 Bostanci、Huang 和 Vaikuntanathan 的验证谕示之上增加了对哈希值的锁定式访问。输入 (i, x, c) 时，若 c 是 C 中码字、其哈希等于 BinEnc(i, x) 拼接 0^(n-l)，且 (BinEnc(i, x), c) 属于 E，则返回 H_i(x)，否则返回底符号。当 E 为满集时，建议态可以解锁这一访问，从而复制自身。

克隆之所以可行，是因为相干地求解码交集问题能让算法在近似保持建议态的同时提取哈希值。固定坐标 i 并在 Sigma 上制备 x 的均匀叠加，算法在挑战 BinEnc(i, x) 上运行偏置 Yamakawa-Zhandry 算法的纯化版本，用得到的码字查询 M[H]，然后逆运算。成功输出时，无论产生哪个有效码字，谕示答案始终是 H_i(x)，因此答案可以被复制到单独寄存器。用同一份种子建议态重复多项式多次，并用混合论证界定累积扰动，就能以压倒性概率得到每个坐标的两个原像态。把这些寄存器组装起来，可在保持原态的同时得到一份新的建议态，保真度为 1 - negl(lambda)。

经典见证为何仍无法匹敌

下界沿用早先 QMA 与 QCMA 分离背后的查询提取思路。假设一个带经典见证的多项式查询验证者能区分满谕示 M[H] 与所有允许的限制谕示 M[H, E]。混合引理迫使其查询在 E 之外的有效对上具有不可忽略的权重，因此测量一个均匀选取的查询能以逆多项式概率提取出一个新的有效对。

关键一步是让提取在无需谕示访问的情况下可重复。提取一对之后，论证把它插入模拟集合 E，并用同一经典见证重启验证者。为维持论证，模拟器必须复现所有先前插入对上的完整谕示答案，而不同于早先的验证谕示，M 还会返回一个哈希比特。这正是挑战同时编码坐标 i 与符号 x 为 z = BinEnc(i, x) 的原因：每个存储的有效对只解锁一个哈希值 H_i(x)，无查询模拟器只需猜测并记录它，每轮代价仅为因子 1/2。如果挑战只编码 x，同一个存储码字就能解锁所有 j 的 H_j(x)，模拟后续执行可能需要猜测整个 n 比特哈希列，每轮损失过大，论证无法成立。

把见证猜测代价与 L 轮提取结合，得到一个无查询猜测器，其成功概率至少为 2^{-t(lambda)} 乘以 (1/poly(lambda))^L。另一方面，码的近似最优列表恢复迫使 L 个不同有效对在 Omega(nL) 个不同的坐标-符号位置规定哈希值，而在偏置哈希分布下，任何无查询猜测器的成功概率至多为 (1 - lambda^{-4})^{Omega(nL)} = exp(-Omega(lambda L))。选取足够大的 L 吸收见证猜测代价，两个界便无法相容，因此锁定式哈希访问在保持经典见证下界的同时实现了高效量子克隆。

同一技术分离可克隆建议并给出量子火

该技术从量子证明扩展到量子建议。论文证明了 BQP/clonableqpoly 与 BQP/poly 之间的经典谕示分离：相对于经典谕示，可被高效克隆的多项式规模建议严格比多项式规模经典建议更有用。在证明与建议两种情形下，高效可克隆性都没有消除量子信息的优势。

该构造还有密码学应用。基于 Yamakawa-Zhandry 算法与好码框架，作者在经典谕示下得到一个满足强可克隆性与不可电报安全性的量子火方案。这直接证明了 Cakan、Goyal 和 Shmueli 的经典谕示量子火存在性结果，但不主张他们更强的密钥火或交互安全性保证。量子火迷你方案把建议态用作火焰：Spark 采样序列号并制备 |adv_H>，Clone 应用克隆算法，Ver 运行放大验证者，均匀采样 (i, a)，在火焰上运行偏置 Yamakawa-Zhandry 算法，并恰在谕示响应不同于底符号时接受。

该分离成立与不成立的范围

该分离是相对化的：它相对于构造出的经典谕示 O 成立，而非无条件成立。论文自身的表述把结果置于相对化框架内，把 Nehoran 和 Zhandry 的量子谕示分离强化到经典谕示。作者还猜想 Bostanci、Huang 和 Vaikuntanathan 的码交集子集大小问题相对于经典谕示分离 QMA 与 ClonableQMA，但这只是猜想，并非已证明的结果。

量子火结果是一个具有非交互不可电报性的迷你方案；早先构造中更强的密钥火与交互安全性保证被明确不予主张。定理 7 中的不可电报性界针对的是分阶段之间不共享量子态、经典记录至多 t 比特的均匀查询有界对手，并依赖于对 H、P 以及目标锁定谕示的查询次数等参数。这些条件界定了该密码学主张适用的范围。

本文引用的文献