⚛️ quantum physics

Function-like pseudorandom unitaries generate pseudorandom quantum processes

本文引入了伪随机函数型幺正算子（PRFU），这是一种密码学原语，能够通过单个短密钥高效地生成由公开标签索引的、可重用的、类随机的量子操作序列，从而将量子伪随机性从单个幺正算子扩展到针对自适应查询安全的复杂多时量子过程。

原作者： Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov

发布于 2026-10-02

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在量子世界中，随机性不仅仅是缺乏模式，它是一种基础资源。当物理学家需要模拟复杂量子系统的行为时，他们通常会设想一种“完美随机”的演化过程，这种过程极其混沌且不可预测，模拟了重复数十亿次的真正随机硬币投掷的行为。这种被称为哈尔随机幺正算符（Haar-random unitary）的理想随机状态，是理解从黑洞内部信息如何纠缠，到量子计算机最终如何破解加密等各种问题的金标准。然而，这里有一个问题：描述或构建这样一个完美的随机过程所需的信息量，会随着系统规模的增大而呈指数级增长。即使对于数量适中的粒子数，创建这种随机性所需的指令也会变得如此庞大，以至于没有任何计算机能够存储，更不用说运行它们了。

为了解决这个问题，科学家们长期以来一直依赖于“伪随机”替代方案。这些过程看起来对任何不持有秘密配方的观察者而言都是随机的，尽管它们是由一组简单、短小的指令生成的。直到现在，这些伪随机工具仍然受到限制。它们可以生成单个看似随机的事件，但如果科学家需要一整套不同的随机事件序列——例如，为了实验中的每一秒，或为了计算机中的每一个不同内存地址——他们必须为每一个事件生成一个新的、巨大的秘密密钥。管理成千上万个这样庞大的密钥库是不切实际的。问题在于：能否通过一个单一且微小的秘密密钥，生成一整个由简单公共标签访问的、各具特色的、看似随机的量子过程，而不泄露其中的秘密？

一支研究团队现在通过引入一种被称为“类伪随机函数幺正算符”（pseudorandom function-like unitary）的新数学对象，回答了这个问题。你可以将其想象成一把主密钥，当它与像名字或数字这样的公共标签相结合时，能立即产生一个独特的量子操作，且该操作看起来完全是随机的。如果你使用相同的标签两次，你会得到完全相同的操作，从而确保了一致性。如果你使用不同的标签，你会得到一个完全不同的操作，且该操作看起来与第一个一样随机。研究人员证明，该系统对于即使是最强大的量子计算机也是安全的，这意味着只要观察者不持有主密钥，就无法分辨这些生成的操作与理想的、完美随机的操作之间的区别。

该团队开发了两个不同版本的工具，以处理不同的交互方式。在第一种版本中，标签是标准的经典信息，例如输入到计算机中的数字。在这里，研究人员展示了通过结合一个安全的伪随机函数和一个伪随机幺正算符，他们可以创建一个系统，其中主密钥为每个标签派生出一个唯一的种子。这种构造足够强大，足以抵御这样一种对手：该对手可以按任何顺序请求任何标签的结果，甚至保留之前的答案作为量子记忆，以帮助其猜测下一个答案。

第二种版本更为复杂，它处理的是“相干”标签。在这种情况下，标签本身可以存在于量子叠加态中，这意味着系统可以被要求对一个同时既是“A”又是“B”的标签应用随机操作。这是一个更难的挑战，因为不同标签之间的量子干涉可能会泄露秘密。为了解决这个问题，研究人员使用了一种称为“索引路径记录”（indexed path recording）的技术。这种方法允许他们同时追踪跨所有可能标签的每一次查询的历史，从而证明即使面对这些复杂的量子查询，该系统仍然与真实的随机性无法区分。

这项工作的意义远不止于生成随机数。研究人员证明，这些新工具可以用于构建伪随机量子信道和“量子梳”（quantum combs）。量子梳是一种描述系统随时间与环境相互作用并在此过程中保持私有记忆的事件序列的方法。通过使用他们的这种新工具，团队展示了单个密钥可以生成一整套随时间演化的过程。这意味着量子系统可以模拟一个复杂的、多步骤的实验，其中规则在每一步都会发生变化，而这一切都由一个简短的秘密驱动。

这种能力为许多实际应用打开了大门。例如，它实现了一种形式的量子身份验证，其中一条消息受一个基于公共“随机数”（nonce）或数字而变化的唯一代码保护。如果攻击者试图重用一个旧的数字，系统可以检测到它并拒绝该消息，从而确保每一次通信都是新鲜且安全的。它还允许一种新型的量子内存访问方式，即数据可以从一个处于地址叠加态的数据库中检索，但检索到的信息被一个取决于地址的随机操作所掩盖。这使得即使是在进行量子查询时，也能向不持有主密钥的人隐藏数据库的内容。

此外，研究人员展示了这种单密钥方法可以为不同大小的寄存器生成随机幺正算符。在许多量子算法中，处理的数据规模可能会发生变化，但在以前，每种新规模都需要一个新的密钥。利用这种新方法，同一个主密钥可以通过改变公共标签，来生成针对小规模、中等规模或大规模寄存器的随机操作。这种灵活性对于构建需要适应不同任务且无需承担管理庞大密钥库开销的可扩展量子系统至关重要。

这项工作也阐明了不同类型量子随机性之间的关系。虽然人们已知如何创建单个随机幺正算符以及如何创建一族随机量子态，但创建一族随机幺正算符仍然是缺失的一环。研究人员填补了这一空白，证明了从单个随机操作向一族随机操作的转变是可能的，但这需要特定的密码学假设，且取决于标签是经典的还是量子的。他们不仅提出了一个理论构想，还提供了具体的数学构造和严密的证明，证明这些系统在最苛刻的条件下（包括对手通过每次交互进行学习的自适应攻击）依然有效。

最终，这项研究改变了我们思考如何在量子系统中生成随机性的范式。我们不再将每个随机事件视为一个独立的、昂贵的资源，而是将其视为一个可以随输入反复调用的函数。这种效率对于量子密码学和模拟的未来至关重要，因为在这些领域，能够从单个秘密生成大量可复现的、看似随机的动力学过程，是实现安全通信和复杂建模的前提条件。研究人员实际上制造了一台机器，能将一把钥匙转化为无穷无尽的、独特的、随机的量子行为，且其安全性足以迷惑最先进的量子观察者。

技术摘要：类函数伪随机幺正算符生成伪随机量子过程

问题陈述

Haar 随机幺正算符是通用随机量子演化的规范模型，为解耦（decoupling）、信息扰动（information scrambling）和量子密码学等现象提供了理论基础。然而，典型的 Haar 随机幺正算符具有指数级的描述长度和电路复杂度，导致其在实际应用中难以实现。虽然伪随机幺正算符（PRUs）为单个看似随机的演化提供了高效的替代方案，但许多加密和物理任务需要一个由公共上下文（例如：随机数/nonce、寄存器宽度或时间步）索引的、由一系列相互独立的、看似随机的操作组成的族。

现有的生成此类族的方法（例如，为每个上下文采样独立的 PRU 密钥）由于需要管理庞大且动态增长的秘密密钥集，在实际操作中并不可行。此外，标准的 PRUs 本身并不具备针对自适应量子查询（即对手与该族中的多个实例进行交互）提供安全性的能力。本文旨在解决这样一个需求：从一个短的母密钥（master key）生成一个整个可自适应寻址的伪随机幺正算符族，同时保持对可能自适应且相干地查询该族的对手的安全性。

方法论

作者引入了类函数伪随机幺正算符（PRFUs），这是一个由单个密钥 $k$ 和公共标签 $x$ 确定的键控族 $\{G_k(x)\}_{x \in \mathcal{X}_\lambda}$ ，其中每个元素都是一个可高效实现的幺正算符。安全目标是使其在计算上与类函数 Haar 随机族不可区分，其中每个标签 $x$ 映射到一个独立采样的 Haar 随机幺正算符 $H_x$ 。

论文区分了两种标签 $x$ 的访问模式：

经典标签访问（Classical-label access）： 标签以经典比特串的形式提供。数据寄存器和参考寄存器保持为量子态。
相干标签访问（Coherent-label access）： 标签由量子寄存器 $L$ 提供，该寄存器可能处于叠加态或与其它寄存器纠缠。算符执行受控幺正变换 $W_k = \sum_x |x\rangle\langle x|_L \otimes G_k(x)$ 。

构建方式

1. 经典标签构建：
作者提出了一种结合后量子伪随机函数（PRF） $F_k$ 和自适应前向 PRU 族 $\{V_a\}$ 的通用构建方法。该构建定义为：
$G_k(x) := V_{F_k(x)}$
此处，PRF 派生出内层 PRU 的种子 $a = F_k(x)$ 。安全证明利用了“延迟表（deferred table）”混合论证，按标签首次出现的顺序处理标签。一个关键组成部分是使用高效可实现的 Haar 近似（Haar proxy）（源自经过放大相对误差的置换-函数-Clifford (PFC) 设计），以模拟中间混合态。这使得通过归约来限制区分优势成为可能，而无需要求内层 PRU 对所有可能的查询都是完整的 Haar 近似，只需对对手进行的有限次查询有效即可。

2. 相干标签构建：
对于相干访问，作者直接使用**索引化 PFC 系综（indexed PFC ensemble）**构建 PRFU。该方法不再通过外部 PRF 派生密钥，而是将标签 $x$ 直接纳入相位和置换原语中。该构建使用：

一个用于相位层的量子安全伪随机函数（qPRF） $g_{k_\Phi}(x, z)$ 。
一个用于置换层的可调式原地伪随机置换（qPRP） $\Pi_{k_P}(x, z)$ 。
一个共享的幺正 2-设计 $C$ 。
生成的幺正算符为 $W_k^{coh} = \hat{P}_{\Pi} \hat{\Phi}_{g} (I_L \otimes C)$ 。
安全性通过**索引路径记录（indexed path-recording）**技术建立。该方法追踪涉及标签叠加的查询历史，以分析干涉现象。证明表明，理想的索引化 PFC 系综在统计上与独立的 Haar 幺正算符不可区分，其偏差界限为 $2q(q-1)/(N+1)$ ，其中 $q$ 是查询次数， $N=2^n$ 。通过将随机原语替换为对应的量子安全原语，可获得计算安全性。

向量子过程的扩展

论文将 PRFUs 扩展到生成伪随机量子信道和量子梳（quantum combs，具有内部记忆的过程）。

信道： 通过在 Stinespring 扩张内应用 PRFU 并丢弃环境，作者生成了伪随机函数型信道（PRFCs）。
梳：通过为连续的“齿”（操作）分配不同的 PRFU 标签，作者构建了伪随机梳。这使得能够模拟具有不可访问内存的多时序动力学，并能抵御自适应干预和并发会话。

核心贡献

定义 PRFUs： 正式定义了伪随机函数型幺正算符，这类算符可以从单个密钥生成由公共标签索引的一系列看似随机的幺正算符。
经典标签构建与安全性： 提出了一种基于后量子 PRF 和 PRU 的通用构建方法，并通过使用 Haar 近似和混合论证证明了其在自适应经典标签查询下的安全性。
相干标签构建与安全性： 一种基于索引化 PFC 系综（使用 qPRF 和可调式原地 qPRP）的特定构建方法。通过索引路径记录技术证明了其在处理标签叠加和干涉时的安全性。
过程提升（Process Lifting）： 展示了 PRFUs 可以被提升以生成伪随机信道和量子梳，从而保护具有私有内存的过程免受自适应和并发交互的影响。
可变宽度 PRUs： 一种结合 PRFUs 与幺正粘合（unitary gluing）的方法，用于创建一个可以在生成后自适应选择寄存器宽度的单密钥 PRU 族。
应用场景： 论文概述了特定的应用，包括：
- 基于随机数解析的量子认证。
- 相干掩码的 QRAM 查询（隐藏数据库内容，防止前向访问观察者获取）。
- 高效模拟随机多时序动力学。

结果

安全性界限： 对于经典标签，区分优势受限于 PRF 优势、PRU 优势以及依赖于 Haar 近似误差（ $2q\eta$ ）的项之和。对于相干标签，其与理想 Haar 族的统计距离被界定为 $2q(q-1)/(N+1)$ ，其计算安全性取决于底层 qPRF 和 qPRP 的硬度。
效率： 这些构建是高效的，相对于安全参数 $\lambda$ 和查询次数 $q$ ，其所需的时间和电路规模均为多项式级别。
可变宽度： 粘合构建成功生成了在生成后可选择多项式级寄存器宽度的伪随机幺正算符，且安全性在不同宽度下得以保持。

意义与主张

本文声称将量子伪随机性的概念从单个操作扩展到了高效生成的、看似随机的动力学族。通过引入 PRFUs，作者弥补了单实例 PRUs 与实现可重复、依赖上下文的随机演化（这在高级量子协议中是必需的）之间的差距。

研究强调了：

单密钥范式： 可以从一个短的母密钥派生出一个整个可自适应寻址的伪随机幺正算符族，从而避免了独立采样 PRU 带来的密钥管理问题。
相干安全性： 即使在标签以叠加态被查询时，也能保持安全性，这是一种比经典标签安全性更强的要求，是通过特定的索引路径记录技术实现的。
过程安全性： 该框架自然地扩展到具有内部记忆的复杂量子过程（信道和梳），为能够介入步骤间或运行并发会话的对手提供了安全性。

作者指出，虽然对于经典标签，通过 PRF 提升可以明确 PRUs 与 PRFUs 之间的关系，但对于相干标签，两者的关系仍是一个开放性问题，因为其构建依赖于特定的原语，而非通用的单实例 PRU 转换。此外，从标准假设中构建所需的调式原地 qPRP 仍然是一个具体的开放性问题。