哪些函数在布尔隐藏划分中具有多项式量子优势？

符号次数决定经典与量子的分界

论文研究 f-布尔隐藏划分（f-BHP）的单向通信复杂度。Alice 持有一个 n 位字符串 x；Bob 持有其索引的 Ω(n) 个不相交块，以及一个标签字符串 y。承诺条件是：在每个块上对 f 求值，要么与所有标签一致，要么与所有标签都不一致，Bob 必须借助 Alice 的一条消息判断属于哪种情况。

决定答案的参数是 f 的符号次数，记作 deg±(f)。当多项式 p 对每个输入 z 都满足 p(z)f(z) > 0 时，称 p 符号表示 f，符号次数就是这种多项式的最小次数。论文确认，正是这个量——而非早期下界所用的纯高次数——决定了整个 f-BHP 族的经典与量子复杂度。

经典复杂度紧确为 Θ(n^(1−1/d))

对每个符号次数 d ≥ 2 的 f，f-BHP 的随机经典通信复杂度为 Θ(n^(1−1/d))。下界 Ω(n^(1−1/d)) 解决了 Doriguello 与 Montanaro 的一个猜想，他们此前只证明了以纯高次数表示的这种界，而纯高次数至多等于符号次数，却可能小得多。

匹配的上界 O(n^(1−1/d)) 表明经典复杂度在常数因子范围内已被确定。这是关于发送比特的随机经典协议的结论；它本身并不说明以量子比特计量的量子消息。

偶数符号次数下量子界紧确

f-BHP 的量子通信复杂度介于 Ω(n^(1−2/d)) 与 O(n^(1−1/⌈d/2⌉) log n) 之间。当 d 为偶数时，这两个表达式在对数因子范围内一致，因此量子复杂度为 Θ̃(n^(1−2/d))。当 d 为奇数时，下界 Ω(n^(1−2/d)) 与上界 O(n^(1−1/⌈d/2⌉) log n) 之间仍存在差距。

下界 Ω(n^(1−2/d)) 适用于符号次数 d ≥ 3，而上界 O(n^(1−1/⌈d/2⌉) log n) 适用于每个 d ≥ 2。论文明确指出奇数 d 的情形尚未完全解决，因此那里的量子复杂度只能刻画到所述区间。

符号次数的三个区间

将新界与 Doriguello 和 Montanaro 的早期结果结合，把 f-BHP 族划分为三个区间。当 deg±(f) ≤ 1 时，对数级经典通信已经足够。当 deg±(f) = 2 时，经典复杂度为 Θ(√n)，而量子协议只需 O(log n) 个量子比特，形成指数级分离。当 deg±(f) ≥ 3 时，量子通信本身也随 n 呈多项式增长，但始终比经典通信多项式级地更小。

因此，符号次数为 2 的函数恰好是那些在经典与量子单向通信复杂度之间产生指数级分离的函数，而每个至少为 2 的符号次数都至少带来多项式量子优势。d = 2 的情形提供了一族新的无限指数级分离。

输入相关时标准工具为何失效

下界使用布尔傅里叶分析与超压缩性，这是单向通信下界的标准工具箱。障碍在于 f-BHP 的困难分布要求 Alice 在某个块上的输入取自与 f 相关的分布 q，这使得块置换 σ 与 Alice 的输入相关。论文指出，消息-置换对的概率可能比其边缘概率之积大 2^Θ(n) 倍，而许多对同时出现的概率为零。

标准论证假设 Bob 关心的奇偶性与 Alice 的消息独立，一旦失去独立性便失效。论文的技术贡献是一套能容忍 Alice 与 Bob 之间显著相关性的工具，作者预期它们对其它在独立输入下过于简单的单向问题也有用。

逐块揭示块值

证明不是去界定块输出 f(x_i) 的每个奇偶性，而是逐块揭示 f(x_1)、f(x_2)、……，并询问在给定先前块的条件下、在 Bob 查看 y_i 之前，他对 f(x_i) 能学到多少。如果 Bob 对块值向量学到了任何东西，那么即使他对任何单个块无条件地一无所知，他也必然对这些条件单块值学到了东西。

符号次数的对偶刻画提供了起点：若 f 的符号次数为 d，则存在 {±1}^k 上的分布 q，使得对每个 |S| < d 都有 E_{z∼q}[f(z)χ_S(z)] = 0。因此从 q 采样一个块，会使少于 d 位的任何子集对该块上的 f 不提供信息。论文还致谢 GPT-6 Astra 贡献了两个关键想法：在给定先前块的条件下分析单个块，以及经典情形中用于处理对 Q/N 二次依赖的递归论证。

量子协议如何达到其界

上界来自一个协议：Alice 发送指纹态 |ψ_x⟩ 的副本，每个副本携带 O(log n) 个量子比特。Bob 在与他的块以及大小为 r 的采样傅里叶单项式 S 相适应的基下测量每个副本，每次有效结果学到一个随机对乘积 u_{i,ℓ}。广义生日论证表明，在 O((k/α)^{1/r} n^{1−1/r}) 个副本之后，某个块 J 以至少 2/3 的概率收到 r 个不同的对标签，使 Bob 能将这些对乘积相乘重构出 χ_S(x_J)。

随后 Bob 构造 Z = ‖p̂‖_1 sgn(p̂(S)) y_J χ_S(x_J)，在承诺条件下其期望至少为 2β/3，其中 β 是符号表示多项式的间隔。将试验重复 R = ⌈9‖p̂‖_1^2 / (2β^2) ln(1/ε)⌉ 次并取和式的符号，由 Hoeffding 不等式可将误差压到 ε 以下。总通信量为 O((‖p̂‖_1^2/β^2)(k/α)^{1/⌈d/2⌉} n^{1−1/⌈d/2⌉} log n log(1/ε)) 个量子比特。

该刻画尚未确定的部分

经典一侧已完全确定：对每个 d ≥ 2 都是 Θ(n^(1−1/d))。量子一侧仅在 d 为偶数时紧确；当 d 为奇数时，复杂度只知道介于 Ω(n^(1−2/d)) 与 O(n^(1−1/⌈d/2⌉) log n) 之间，因此精确指数仍未解决。这些界针对 α ∈ (0,1) 且 k | αn 的 f-BHP 承诺问题，上界带有对数因子以及依赖符号表示多项式间隔 β 和 ℓ_1 范数的常数。

最具决策意义的阈值是符号次数为 2。这是经典通信为 Θ(√n) 而量子通信为 O(log n) 的唯一区间，因此 d = 2 正是指数级分离所在之处；d ≥ 3 仍给出多项式量子优势，但不再是指数级的。因此，比较候选函数 f 的读者应首先检查 deg±(f)，因为仅凭它就能区分对数级、指数级与多项式级三个区间。

本文引用的文献