技术摘要：无结构的无条件认证随机性

问题陈述

本文解决了在量子随机预言机模型（QROM）中生成认证随机性的挑战。具体而言，其寻求一种满足以下条件的协议：

1. 非交互式： 量子证明者向验证者发送单条消息。
2. 公开可验证： 任何能够访问随机预言机的第三方都可以进行验证。
3. 单证明者： 不依赖于多个设备之间的非通信假设。
4. 无条件安全性： 安全性不依赖于未经证实的复杂度理论假设。

此前，Yamakawa 和 Zhandry (YZ) [YZ24] 的工作展示了 QROM 中 NP 搜索问题的量子优势，这暗示了一个认证随机性协议的存在。然而，他们的协议依赖于 Aaronson–Ambainis 猜想来保证量子算法的输出具有高最小熵。如果没有该猜想，目前尚不清楚输出是否真正随机，或者经典对手是否可以预测它。之前的无条件结果（例如 [KRT26]）仅限于对手进行极少量自适应层（$o(\log n)$）的查询，无法覆盖一般的自适应对手。

方法论与核心技术

作者提出了一种被称为偏置 YZ 问题的 Yamakawa–Zhandry 问题的变体，并证明了该问题在面对最多进行 $2^{o(n^c)}$ 次自适应查询的对手时，能无条件地认证最小熵。其证明策略依赖于混合论证（hybrid arguments）和预言机重编程（oracle reprogramming），利用了三个主要的数学技术创新：

1. 查询范数与查询范数多面体

作者没有分析“查询权重”（查询特定输入的概率），而是分析了查询范数（查询权重的平方根）。他们定义了一个称为**查询范数多面体（query-norm polytope）**的几何结构，该结构代表了当预言机被重编程时，查询范数发生变化的线性约束。

• 局部稳定性： 他们建立了这样一个结论：如果预言机在具有小查询范数的输入上被重编程，那么其他输入的查询范数变化只会非常微小。
• 重坐标重编程（Heavy-Coordinate Reprogramming）： 一个关键引理（引理 4.3）表明，即使对手对大量坐标集合 ($M$) 进行重度查询，也存在指数级多的方式，可以在 $M$ 的一个子集上重编程预言机，使得对手仍然在 $M$ 的一个较小但仍然实质性的子集（具体为 $\Omega(\sqrt{n})$ 个坐标）上放置显著的查询范数。这克服了重编程“重”坐标时的困难，因为在这些坐标处，对手可能会检测到变化。

2. 修改后的纠错码

原始的 YZ 构造使用了一种具有特定列表恢复（list-recovery）性质的编码，但这种性质不足以满足新的重编程界限（即仅保留 $\Omega(\sqrt{n})$ 个已知符号，而非线性数量的符号）。

• 作者构造了一族折叠 Reed–Solomon (FRS) 码，其码率较低（$R \approx 1/\sqrt{n}$）。
• 这些码是 $(\zeta, \ell, L)$-列表可恢复的，这意味着如果一个码字与极小比例（$\approx 1/\sqrt{n}$）的坐标上的短列表一致，则满足条件的码字数量是有限且较小的。这与多面体论证所保证的 $\Omega(\sqrt{n})$ 个存活的重坐标相匹配。

3. 偏置随机预言机

为了在使用这种新的低码率编码时保持协议的完备性（确保诚实的量子证明者成功），作者引入了一个偏置随机预言机。

• 预言机 $H$ 以较小的概率 $p \approx 1/\sqrt{n}$ 输出 1，以概率 $1-p$ 输出 0。
• 这种偏置确保了对偶基底（经过傅里叶变换后）中的“误差”向量的汉明重量以高概率为 $O(\sqrt{n})$。这落在对偶码 $C^\perp$ 的唯一解码半径内，从而允许诚实的证明者成功解码并输出有效的解。
• 文中证明了这种偏置预言机可以在标准的 QROM 中通过均匀随机预言机高效地模拟。

主要贡献与结果

本文提出了一个具有以下保证的可认证最小熵协议（定理 1.1）：

• 无条件安全性： 该协议对于任何进行最多 $2^{o(n^c)}$ 次自适应量子查询的对手都是安全的，其中 $c$ 为任意常数 $c \in (0, 1/2)$。这消除了对 Aaronson–Ambambis 猜想的需求。
• 最小熵保证： 如果对手导致验证者以显著概率接受，则输出分布的最小熵至少为 $\Omega(n^c)$。
• 协议属性：
  • 非交互式： 证明者输出一个候选解 $x$。
  • 公开可验证： 验证者检查是否 $x \in C$ 且对于所有 $i$，都有 $H_i(x_i) = 0$。
  • 单证明者： 不需要设备之间的通信假设。

证明过程采用反证法：

1. 断言 A（低熵意味着重度查询）： 如果对手以高概率输出特定的正确答案（低熵），则它必须对该答案的大部分符号进行了重度查询。
2. 断言 B（查询受限无法进行重度查询）： 利用重坐标重编程引理和修改后编码的列表恢复性质，作者表明，对于几乎所有的预言机，没有任何正确的答案会被具有给定查询限制的对手进行重度查询。
3. 结论： 这两个断言是不相容的，这意味着对手无法以显著概率输出低熵分布。

意义与声明

本文声称提供了第一个在 QROM 中、非交互式、公开可验证且针对一般自适应对手（最高达亚指数查询界限）的无条件认证随机性协议。

• 结构性洞察： 作者强调，YZ 问题是一个“无结构”的量子优势来源。通过在不依赖猜想的情况下证明其解的固有随机性，这项工作为验证 Aaronson–Ambambis 猜想的真实性提供了证据（因为该结果意味着该猜想的一个推论在无条件下对该变体成立）。
• 技术进步： 该工作引入了查询范数多面体框架，为重编程论证提供了一个新的几何视角。该框架允许对如何在修改预言机时改变查询分布提供更紧致的界限，特别是处理了此前在无条件证明中难以处理的“重”坐标问题。
• 局限性与开放问题： 作者指出，其结果适用于 YZ 问题的的一个变体（偏置预言机、修改后的编码）。他们明确提出了一个开放性问题（问题 1），即能否改进重坐标重编程引理，使其能够保留线性数量的重输入，从而可能允许使用原始的 YZ 编码和预言机而无需偏置。他们还承认，目前的证明要求对手的查询界限为亚指数级（$2^{o(n^c)}$），这使得全多项式查询的情况仍是一个有待研究的领域。

本文并未提出具体的实验实现或特定的现实世界应用，其主要贡献在于量子随机性认证基础理论的突破。