Cryptographic Conditions for Efficient Testing of Distributions and Quantum States

本文提出了一种用于分布和量子态测试的密码学框架，该框架通过证明多项式数量的样本足以验证可高效采样的分布（即使样本是敌手生成且相关的），从而克服了传统样本复杂性和独立性限制，并利用新颖的柯尔莫哥洛夫复杂度技术实现这些成果，进而支持无假设认证随机性和量子优势基准测试等应用。

要点

想象你是一名侦探，试图判断一堆文件是源自某个特定的、受信任的工厂（即“目标分布”），还是由一位聪明的伪造者（即“对手”）伪造的。

在计算机科学领域，这被称为身份测试。通常，为了确信文件是真实的，你需要检查海量的文件——对于大文件而言，其数量之多甚至会导致检查时间超过宇宙的年龄。本文提出：如果我们知道伪造者受限于其思考和工作的速度，我们能否做得更好？

作者的回答是肯定的，但这一答案取决于我们的宇宙中是否存在某些“数学锁”（密码学）。他们还将这一逻辑应用于量子态（文件的量子版本）和随机性。

以下是他们研究发现的分解，辅以日常类比：

1. 新的侦探游戏：“关联伪造”

传统上，侦探们假设如果伪造者制造假文件，每一份文件都是独立制作的（就像反复掷骰子）。但在现实世界中，伪造者可能会制造一整批文件，其中文件之间是相互关联或“关联”的（就像一副按特定顺序堆叠的扑克牌）。

作者制定了一套新规则：

• 承诺：未知来源必须是高效的（它不能花费一百万年时间来生成一个样本）。
• 威胁：我们看到的样本可能是由一个聪明的对手制造的杂乱、关联的堆栈。
• 目标：我们能否仅通过多项式（可管理）数量的样本，并在多项式（可管理）的时间内验证来源？

2. 密码学的“魔法钥匙”

该论文发现，验证这些分布的能力完全取决于单向函数（易于上锁但难以破解的数学锁）是否存在。

• 场景 A：锁不存在（简单模式）
  如果这些数学锁不存在，那么每一个高效生成的分布都可以被快速验证。

  • 类比：想象一个试图隐藏行踪的伪造者。如果宇宙中不存在“魔法锁”，那么伪造者隐藏的方法实际上是非常可预测的。侦探可以使用一种特殊的“复杂度计”（基于柯尔莫哥洛夫复杂度）来衡量文件看起来有多“随机”。如果文件过于“简单”或“可压缩”（低复杂度），它很可能是伪造的。如果它是真正随机的（高复杂度），则通过验证。
  • 难点：这种“复杂度计”通常无法被完美计算。但如果锁不存在，作者表明你可以构建一个“足够好”的该计量器版本，且运行速度很快。

• 场景 B：锁存在（困难模式）
  如果这些数学锁确实存在，那么有些分布是无法被高效验证的。

  • 类比：伪造者利用“锁”制造出一份在统计上与真文件完全相同、但实际上不同的假文件。由于锁无法被破解，无论侦探检查多少样本，都无法区分真伪。论文证明，如果这些锁存在，对于高熵（非常随机）的分布，验证将走入死胡同。

3. 量子转折：“幽灵”态

作者将这一逻辑扩展到量子世界，其中的“文件”是量子态（就像一枚既在正面又在反面的旋转硬币）。

• 挑战：在量子力学中，测量一个状态会改变它。你不能在不潜在破坏它的情况下“读取”文件。此外，伪造者可能会制造出一堆“幽灵”般的纠缠态，这些状态以经典计算机无法理解的方式相互关联。
• 结果：
  • 如果某些量子谜题（锁的量子版本）不存在，那么任何可以高效生成的量子态也可以被高效验证。
  • 如果这些谜题确实存在，那么验证量子态将变得困难。
  • 他们还发现了一种特定类型的“弱”量子谜题，它充当了转折点：如果这些谜题不存在，验证就很简单；如果存在，验证就很困难。

4. 两个酷酷的副项目

在解决主要谜团的同时，作者发现了另外两个有用的工具：

• 认证随机性（“真随机”印章）：
  他们表明，如果你愿意让验证者变慢（低效），你就可以证明一串数字是真正随机的，而无需任何未经验证的假设。

  • 类比：想象一台打印长串数字的机器。如果这串数字是真正随机的，它就具有高“复杂度”（难以描述）。如果是伪造的，则复杂度低。作者构建了一种协议，让一个缓慢的验证者可以检查这种复杂度，并将其盖章为“认证随机”。即使面对超级聪明的伪造者，只要伪造者遵循标准物理规则（均匀性），此方法依然有效。

• 通用量子优势检测器：
  他们创建了一个“基准”，用于判断计算机是否正在执行经典计算机无法完成的事情（量子优势）。

  • 类比：想象人类计算器（经典）与超快量子计算器之间的比赛。作者发明了一个“复杂度差距”分数。
    • 如果人类计算出结果，分数很低。
    • 如果量子计算机计算出人类无法模拟的结果，分数很高。
  • 这个分数充当了通用的“量子优势”徽章。如果一个样本具有高分数，你就可以确定它是由量子计算机生成的，没有任何经典计算机能够伪造它。

总结

这篇论文本质上指出：

1. 即使样本杂乱且关联，只要我们的宇宙中不存在某些密码学“锁”，就可以通过合理数量的样本进行验证。
2. 如果这些锁确实存在，那么有些事物在根本上是无法验证的。
3. 他们使用了一个名为柯尔莫哥洛夫复杂度（描述这些数据有多难？）的概念作为“测谎仪”，以区分真正的随机性和伪造品。
4. 这一逻辑既适用于经典数据，也适用于量子态，提供了一种无需信任量子机器即可验证“量子优势”的新方法。

技术摘要

技术摘要：分布与量子态高效测试的密码学条件

1. 问题陈述

本文探讨了分布测试（身份测试）和量子态验证领域中的基本局限性。传统上，区分目标分布 $D$ 与 $\{0, 1\}^n$ 上的未知分布需要 $\Omega(\sqrt{2^n})$ 个样本，这种复杂度是指数级的，对于较大的 $n$ 而言不切实际。此外，标准模型假设样本是独立同分布（i.i.d.）的。

作者指出了现实场景中的两个关键差距：

1. 高效可采样性：在许多应用（例如验证量子优势）中，未知分布被承诺是高效可采样的，但现有的测试器并未针对这一承诺进行优化。
2. 对抗性相关性：在现实世界场景中，特别是在量子设置中，样本可能由对抗者生成，该对抗者可以在样本之间引入任意相关性，从而违反 i.i.d. 假设。

核心问题是：在何种密码学假设下，即使样本是对抗性相关的，也能仅使用多项式数量的样本验证高效可采样的分布（经典或量子）以及高效可生成的量子态？

2. 方法论与技术框架

本文引入了一种新的分布验证和量子态验证模型，该模型放宽了 i.i.d. 假设，同时将对抗者限制为高效采样器。

2.1 定义

• 自适应安全性（Adaptive-Soundness）：如果对于任何生成相关样本 $x_1, \dots, x_s$ 的高效对抗者 $A$，当 $A$ 的边缘分布（从集合中均匀随机选择的单个样本的分布）在统计上远离目标 $D$ 时，验证者以高概率拒绝，则验证者 $Ver$ 被视为安全。
• 高效验证：要求样本复杂度为多项式级（$s = \text{poly}(n)$）且验证者的运行时间为多项式级。

2.2 核心技术

作者采用了来自**元复杂性（Meta-Complexity）和柯尔莫哥洛夫复杂度（Kolmogorov Complexity）**的技术，并结合现代量子密码学原语。

• **柯尔莫哥洛夫复杂度（$K(x)$ 和 $uKt(x)$）**：本文利用了字符串的柯尔莫哥洛夫复杂度与其被采样概率之间的关系。具体而言，它使用了时间有界通用柯尔莫哥洛夫复杂度（$uKt$）及其量子类比（$quKt$）。
  • 编码定理：$K(x) \approx -\log \Pr[x \leftarrow D]$。
  • 不可压缩性：从分布中采样的字符串通常具有相对于其概率较高的柯尔莫哥洛夫复杂度。
  • 作者改进了 Aaronson 的 [Aar14] 低效验证思想，该思想将样本的柯尔莫哥洛夫复杂度与其理论概率进行比较。
• 密码学假设：
  • 经典：单向函数（OWFs）的存在/不存在。
  • 量子：单向谜题（OWPuzzs）的存在/不存在、量子高效可采样不可区分分布（QEFID）的存在/不存在，以及纠缠远不可区分（EFI）对的存在/不存在。
• 通用区分器：在量子设置中，由于量子概率估计缺乏单侧误差，直接估计柯尔莫哥洛夫复杂度是不够的，因此作者构建了一个“通用区分器”，该区分器迭代所有可能的常数大小量子图灵机，以区分目标分布与对抗性边缘分布。

3. 主要贡献与结果

3.1 经典分布验证

本文建立了验证经典高效可采样分布复杂度的紧确刻画。

• 主要结果（定理 1.2）：如果无限次单向函数（OWFs）不存在，那么每个经典高效可采样分布都是高效可验证的。
  • 机制：OWFs 的不存在意味着存在用于概率估计和 $uKt$ 近似的高效算法。这使得构建一个 PPT 验证者成为可能，该验证者检查估计的柯尔莫哥洛夫复杂度是否与估计的概率相匹配。
• 困难性结果（命题 1.4）：如果 OWFs 存在，那么任何具有足够高熵（$H(D) = n^{\Omega(1)}$）的经典高效可采样分布都不是高效可验证的。
  • 机制：利用源自 OWFs 的伪随机生成器（PRG），可以构建一个对抗性分布，该分布在统计上远离目标但在计算上不可区分，从而欺骗任何高效验证者。

3.2 量子分布验证

作者将这些结果扩展到由量子算法（QPT）可采样的分布。

• 主要结果（定理 1.5）：验证量子高效可采样分布的困难性被夹在两个密码学原语之间：
  1. 如果OWPuzzs不存在，则可以实现高效验证。
  2. 如果QEFID（量子高效可采样不可区分分布）存在，则高效验证是困难的。
  • 注：本文指出，虽然 OWPuzzs 蕴含 QEFID 的非均匀变体，但反向构造目前仍是一个开放问题。因此，该刻画几乎完整，但依赖于这些原语之间的关系。
• 技术：与经典情况不同，作者不能仅依赖柯尔莫哥洛夫复杂度，因为量子概率估计缺乏必要的单侧误差属性。相反，他们构建了一个验证者，该验证者利用基于 OWPuzzs 不存在性的通用区分器来区分目标边缘分布与对抗性边缘分布。

3.3 量子态验证

结果被扩展到量子态的验证（身份测试的量子类比）。

• 主要结果（定理 1.7）：
  1. 如果弱非均匀 EFI对不存在，那么每个高效可生成的量子态都是高效可验证的。
  2. 如果EFI对存在，则验证量子态是困难的。
• 意义：这将量子态验证的可行性直接与最小量子密码学原语（EFI）的存在联系起来。

3.4 无条件结果与不可能性

• 小熵（命题 1.8）：无需任何密码学假设，小熵分布（$H(D) = O(\log n)$）是高效可验证的。这是通过枚举高概率结果实现的。
• 学习的不可能性（命题 1.10）：在非 i.i.d. 设置中，即使验证是可能的，也不可能用多项式样本学习未知采样器的边缘分布。
• 安全性界限（命题 1.9）：主要定理中实现的安全性界限本质上是紧确的。不可能构建一个验证者，使其对任何边缘距离为 $\epsilon$ 的对抗者以 $1 - \epsilon$ 的概率拒绝；可实现的最佳拒绝概率约为 $1 - \epsilon$。

4. 其他应用

4.1 认证随机性

本文构建了一个非交互式、无侧信息的认证随机性协议（定理 1.11），该协议是无条件的（无需计算假设）。

• 机制：证明者输出一条字符串，如果该字符串具有高柯尔莫哥洛夫复杂度（$quKt$），则低效验证者接受。
• 意义：之前的无条件协议需要多证明者设置或理想化模型。这一结果表明，对于均匀对抗者，即使没有假设，只要验证者是低效的，认证随机性就是可能的。

4.2 量子优势基准

作者提出了一种用于基于采样的量子优势的“通用验证者”（定理 1.12，推论 1.13）。

• 指标：他们定义了量子计算深度（$qcdt(x) = uKt(x) - quKt(x)$）。
• 结果：由展示强量子优势（在统计上远离任何经典 PPT 采样器）的量子算法生成的字符串将具有高 $qcdt(x)$，而经典采样器将具有低$qcdt(x)$。
• 意义：这提供了一个与模型无关的量子优势基准，不同于之前的基准（例如随机电路采样），后者是与模型相关的。如果 OWPuzzs 不存在，则该验证者可以高效实现。

5. 意义与主张

本文声称通过以下方式从根本上改变了对分布和态测试的理解：

1. 连接密码学与测试：它确立了验证高效可采样分布的可行性等同于特定密码学原语（OWFs、OWPuzzs、EFI）的不存在。
2. 克服 i.i.d. 局限性：它证明了即使样本是对抗性相关的，只要对抗者是计算受限的，就可以实现多项式样本复杂度。
3. 无条件认证随机性：它提供了首个针对均匀对抗者、具有经典证明者但验证者低效的无条件认证随机性构造。
4. 通用量子基准：它引入了一种基于柯尔莫哥洛夫复杂度的指标（$qcdt$），作为量子优势的与模型无关的见证。

作者强调，他们的结果是“紧确”的，因为它们根据密码学假设精确刻画了验证的困难性，并且他们强调在非 i.i.d. 设置中学习边缘分布的不可能性证明了关注验证而非学习的合理性。